Use std::set with input order preserved

user_12038287 0
Viewed 162

I would love to use std::set to store integers that have to be unique, but I don't want them to be sorted (e.g. I need the order of input to the set preserved)

For example:

set<int> exampleSet;
exampleSet.insert(5);
exampleSet.insert(2);
exampleSet.insert(10);
exampleSet.insert(0);

The set will now contain

{0,2,5,10}

I would like it to be in original order so

{5,2,10,0}

How do I achieve this?

c++11 c++
2 Answers

Probably the easiest and most obvious way to do this is to use a set in conjunction with a vector:

// We'll use this solely to keep track of whether we've already seen a number
std::set<int> seen;

// and this to store numbers that weren't repeats in order
std::vector<int> result;

// some inputs to work with
std::vector<int> inputs{ 1, 10, 1, 19, 10, 5, 2, 1, 19, 5, 1};

for (int i : inputs)
    if (seen.insert(i).second) // check if it's a duplicate
        result.push_back(i);   // if not, save it

// show the results:
std::copy(result.begin(), result.end(), std::ostream_iterator<int>(std::cout, "\t"));

Result:

1   10  19  5   2

If you might have a lot of unique numbers, an std::unordered_set may have better performance than an std::set.

user_1799100

You need an ordered set -- you can find one here. This is more or less a "drop in" replacement for std::set that maintains the insertion order.

user_164060
Related