Special container
in [C++]
|
Prev: Exceptions
Next: Pet peeves (lighthearted)
From: Ithier on 5 Jul 2005 07:01 Hi, I need a special container which does not exist, I think. It's a kind of list and set. It's a set because each included object has to be unique and it's a kind of list because the order has to be kept as is. For example, if I insert objects A, Z, B, Z, A and C, I need to store only A, Z, B, C, in that order. To achieve this I have three solutions: 1ý) Create a new container type, with all the caracteristic needed. The objects will be stored inside my mew container in a vector or list. 2ý) Write a special inserter to achieve the desired goal (an inserter function object) which will check that an entry doesn't exist before inserting it really. 3ý) Write an algorithm that will remove the duplicate entries (as the std::unique function do, unfortunatly it works only on sorted containers). 4ý) ??? Performances is not a big issue as the number of objects will always be small (less than 20) and the objects are quite small (contains 6 strings) So, what is the best solution to my problem. What would you recommend, knowing that I always prefer to use what already exists ? Thanks Ithier [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Maxim Yegorushkin on 5 Jul 2005 09:05 On Tue, 05 Jul 2005 15:01:16 +0400, Ithier <nospam(a)nospam.com> wrote: > I need a special container which does not exist, I think. It's a kind of > list and set. It's a set because each included object has to be unique > and it's a kind of list because the order has to be kept as is. > For example, if I insert objects A, Z, B, Z, A and C, I need to store > only A, Z, B, C, in that order. http://boost.org/libs/multi_index/doc/index.html -- Maxim Yegorushkin <firstname.lastname(a)gmail.com> [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Mirek Fidler on 5 Jul 2005 09:05 Ithier wrote: > Hi, > > I need a special container which does not exist, I think. It's a kind of > list and set. It's a set because each included object has to be unique > and it's a kind of list because the order has to be kept as is. > For example, if I insert objects A, Z, B, Z, A and C, I need to store > only A, Z, B, C, in that order. I have one nice container called Index that can easily be used in this scenario (and many others as well...) Look for Index in these docs: http://upp.sourceforge.net/srcdoc$Tutorial$en-us.html http://upp.sourceforge.net/src$Indext$en-us.html http://upp.sourceforge.net/srcdoc$NTL$en-us.html Of course, I am not sure what exactly "unique" means in your description, anyway if you are talking about "unique" in sense of value comparison, you would create your desired sequence using code like this: Index<T> list; //T is type of your values while( ThereAreValuesToProcess() ) // iterate input values list.FindAdd(NextValue()); Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Richard Corden on 5 Jul 2005 09:04 Ithier wrote: > Hi, > > I need a special container which does not exist, I think. It's a kind of > list and set. It's a set because each included object has to be unique > and it's a kind of list because the order has to be kept as is. > For example, if I insert objects A, Z, B, Z, A and C, I need to store > only A, Z, B, C, in that order. We had a similar problem and we solved it using a set and a vector of that set's iterators to keep the insertion order: #include <set> #include <vector> typedef std :: set < T > Cont1; typedef Cont1 :: iterator Iter1; typedef std :: vector < Iter1 > Cont2; When you insert into a set you get a pair back with the iterator inserted and a boolean flag to say if the element is new to the set. If the element was new you can then push the iterator onto the vector. Cont1 c1; Cont2 c2; std::pair <Iter1, bool> insert_result = c1.insert ( T () ); if (insert_result.second) { c2.push_back (insert_result.first); } Regards, Richard -- Richard Corden [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Maciej Sobczak on 5 Jul 2005 09:03
Ithier wrote: > I need a special container which does not exist, I think. I think that you need a special semantics of insertion to the container, not necessarily a separate container. > For example, if I insert objects A, Z, B, Z, A and C, I need to store > only A, Z, B, C, in that order. > Performances is not a big issue as the number of objects will always be > small (less than 20) and the objects are quite small (contains 6 strings) With these assumptions, you might try the following: #include <vector> #include <algorithm> template <class Container, typename Value> void add_unique(Container &c, Value const &v) { if (std::find(c.begin(), c.end(), v) == c.end()) c.push_back(v); } int main() { std::vector<char> c; add_unique(c, 'A'); add_unique(c, 'Z'); add_unique(c, 'B'); add_unique(c, 'Z'); add_unique(c, 'A'); add_unique(c, 'C'); assert(c.size() == 4); assert(c[0] == 'A'); assert(c[1] == 'Z'); assert(c[2] == 'B'); assert(c[3] == 'C'); } add_unique function will also work with std::list and any other sequence. -- Maciej Sobczak : http://www.msobczak.com/ Programming : http://www.msobczak.com/prog/ [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |