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.

Vichyssoise

... Did the name not give it away? – Asphaltite

Yeah, I know. I was hoping it only referred to the key values, however. Just wanted to see if anyone here knew a method that could get what I was looking for. – Vichyssoise

So if I insert 420 69 1 2 420 then should the position of occurrence of 420 be 1 or 5? – Dwinnell

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.

Tibbitts

I was afraid of such, but just wanted to double check to see if there might be some work-around. Thank you, I appreciate your advice. – Vichyssoise

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 :))

Prepositor

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;
}

Antennule