16

Possible Duplicate:
A std::map that keep track of the order of insertion?

I am looking for an STL container that preserves order of insertion ( no sorting ) but does not allow duplicates. Is there one? if not any tricks I can use to customize one?

Community
  • 1
  • 1
krisostofa
  • 163
  • 1
  • 4
  • Will this container only take in new elements or does it need to allow elements to be deleted also? – sep Jun 08 '11 at 12:30
  • When you say that it preserves the order of insertion, you probably want to iterate over it. Do you want to iterate from first to last or the reverse? – sep Jun 08 '11 at 12:35
  • I will insert once ( no deletes ) and read ( iterate over elements) many times – krisostofa Jun 08 '11 at 13:03
  • I think this is a so common pattern, that it confuses me why didn't the languages' makers implemented such a feature yet. Another very common pattern I cross also, is a dictionary that allows no duplicates of key, but is also iterable by the order of insertion. If someone knows about something like I described please let me know. – sergiol Oct 30 '15 at 19:04

4 Answers4

8

There is no such a container at the moment, but you can create your own one in a cheap way by holding a std::vector and a std::set in a class together.

Vlad
  • 35,022
  • 6
  • 77
  • 199
  • 1
    If your objects are large, consider storing pointers within the containers and provide your own sort function to the set ctr. – RC. Jun 08 '11 at 12:28
  • 1
    Good suggestion. If the objects are large enough that you don't want two copies of them, then you could keep objects in the set, and pointers or iterators to the set elements in the vector. – Mike Seymour Jun 08 '11 at 12:29
  • @RC: well, my proposal is not ideal, because the objects are actually stored twice. A much better solution would be to create the container with the needed properties from scratch. However, writing a new container requires much more effort. – Vlad Jun 08 '11 at 12:30
  • @Mike: the solution with pointers would be less efficient if the container is to store _small_ objects, e.g., chars or bools (for bools std::vector uses bit packing). And there's a disadvantage for twice so big memory overhead (again, for small contained objects). So the only true solution would be making a new container. – Vlad Jun 08 '11 at 12:33
  • @Vlad - My suggestion was to use your solution, but offer the advice of storing pointers to the objects (when they are large) instead of storing them twice in the two containers. Wrapping the two std containers within an object to do this is IMO almost necessary as you want to keep this all abstracted from the user and to also guarantee proper de-allocation for the objects if using pointers for storage. – RC. Jun 08 '11 at 12:37
  • 1
    @Vlad: yes, that's why I qualified my suggestion with "if the objects are large". Objects smaller than pointers would certainly be more efficiently stored by value in both containers. – Mike Seymour Jun 08 '11 at 13:03
6

I know you have specifically asked for an STL container however boost already provides a multindex container which does what you want with its ordered_unique index. I definitely worths looking at instead of reinventing the wheel.

I just wanted to point a good alternative.

Good luck.

O.C.
  • 6,711
  • 1
  • 25
  • 26
2

No need to re-invent the wheel, consider using a boost::multi_index container. You can then define various indexes to your heart's content. The performance difference (if you are worried) should be minimal.

Nim
  • 33,299
  • 2
  • 62
  • 101
1

There isn't one. Detecting duplicates without sorting or hashing is a pretty expensive operation.

Nemanja Trifunovic
  • 24,346
  • 3
  • 50
  • 88