Special container
in [C++]
|
Prev: Exceptions
Next: Pet peeves (lighthearted)
From: Ithier on 5 Jul 2005 13:49 > 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: > Thanks for the solution, I didn't know that the insert function was returning a boolean flag. Unfortunatly, I need something with a "standard" interface to be easily integrated, so I don't need to modify all my objects. To achieve this goal, the functions that fill my containers doesn't take a container as a parameter but an OutputIterator (like the last parameter of the std::copy function). So the container is not hardcoded in the function so I can switch from one type of container to another. Thats how I understand STL ;-) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Ithier on 5 Jul 2005 13:50 Maciej Sobczak wrote: > I think that you need a special semantics of insertion to the container, > not necessarily a separate container. > Yes, I think also. > 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); > } > Thanks, I will try to integrate your algorithm in a function object like back_inserter so I can use the vector with the special inserter like a normal container (the function that fill my container just take an OutputIterator as parameter, like std::copy). Ex: std::vector<char> c; object.fill (unique_back_inserter(c)); [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Mark Van Peteghem on 5 Jul 2005 13:54 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. > >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). > > Why do you still need this if step 2 already checks if the element is already in the container? Steps 1 and 2 seem sufficient for what you want to do. I don't know a container that does this. What you suggest seems good if performance is not important. Otherwise I think the best solution is to make a class that has a list and a set inside. If you add an object, check if it is in the set, which is faster than checking if it is in a list, and if not, add it to both the list and the set. If fast random access is important, replace the list with a vector. If the objects are big, having duplicates might be costly, but in that case you could make a set with list iterators that refer to the elements in the list, and a special predicate for the set that sorts on what the list iterators point to (this doesn't work with vectors, of course). -- Mark dot Van dot Peteghem at q-mentum dot com http://www.q-mentum.com -- easier and more powerful unit testing [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Carlos Moreno on 6 Jul 2005 05:38 Maciej Sobczak wrote: > template <class Container, typename Value> > void add_unique(Container &c, Value const &v) Was that intentional? If so, may I ask why the choice of "class" for the first type parameter and typename for the second? It's been a while that I -- for a simple matter of style and personal taste -- discontinued the use of the keyword "class" in that context (I prefer class to mean only what it means in the OO context) Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Dave Harris on 6 Jul 2005 06:01
no.spam(a)no.spam.com (Maciej Sobczak) wrote (abridged): > > 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. It seems to me he needs a container with a special class invariant. The trouble with providing only the insertion function is that nothing prevents other insertion functions from being used. I'd write a thin wrapper class around a vector. And having written the class, I'd make it do as much of the work as it reasonably can - there are probably functions which take advantage of the invariant as well as functions to ensure it, and these can be member functions too. -- Dave Harris, Nottingham, UK. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |