Search code examples
c++insertc++14unordered-set

Maintaining order in an unordered set after using insert C++

How can I preserve the order of elements within an unordered set after using insert (or emplace) without allocating during construction?

For details into this problem, here's an example:

  • An unordered set S of integers is constructed
  • 480 is inserted into S: S = { 480 }
  • 32 is inserted into S: S = { 32 480 }
  • 23 is inserted into S: S = { 23 32 480 }
  • 16 is inserted into S: S = { 16 23 32 480 }
  • 19 is inserted into S: S = { 19 480 32 23 16 }

You can see how the last insertion destroys the sequence order (I assume by reconstructing a larger set and moving the elements over). I'm looking for a way to preserve the previous order after inserting an element without the need for specifically allocating in the constructor.

Solution

  • An unordered set is, by definition, unordered. There's no defined order, and the iteration order of elements in the set can change at any time.

    And allocating something in the constructor is not going to make any difference, either.

    If you want a set with a specific iteration order, that's what std::set is for. However, std::set always orders by key value, not insertion order.

    You may need to combine several containers together, in order to achieve your desired access semantics.