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

Question

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.

Answer 1

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.

Answer 2

Unordered sets are normally based on hash function allocations and have O(1) access time.

Ordered sets are normally based on AVL trees, and access is based on comparison functions between keys. They have O(log(n)) access time in general, but conserver key order.

You need to think twice if you want a quick access or an almost as quick access with sorted keys in your map. But there's no possibility of having both (like indetermination problem in quantum phisics :))

Answer 3

One way is to use "std::vector".

#include <iostream>
#include <vector>
#include <algorithm>

void insertIntoVector(std::vector<int> &vec, int const value) {
    if (std::find(vec.cbegin(), vec.cend(), value) == vec.cend()) {
        vec.push_back(value);
    }
}

int main() {
    std::vector<int> vec;

    insertIntoVector(vec, 1);
    insertIntoVector(vec, 2);
    insertIntoVector(vec, 3);
    insertIntoVector(vec, 3);
    insertIntoVector(vec, 4);

    for (int const value : vec) {
        std::cout << value << std::endl;
    }

    return 0;
}