2

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?

TheBlue22
  • 39
  • 2
  • The set needs the sorted order to function properly. You need to use something like `std::vector`, along with a set to avoid adding duplicate elements to it. – HolyBlackCat Apr 15 '21 at 17:59
  • 1
    What operations on the set do you want? For example, will you need deletion of some element? – MikeCAT Apr 15 '21 at 18:02
  • 2
    Why do you need to know the order of insertion? How often are you going to make use of the insertion order in your program? Once? on occasion? Many times? If you want some sort of information tied to the inserted item, maybe something more robust than a simple `int` would be better? Maybe a `std::set>` that has the `int`, and the insertion number? – PaulMcKenzie Apr 15 '21 at 18:08
  • 1
    https://stackoverflow.com/questions/46511614/preserving-insertion-order-on-a-stdset-or-stdunordered-set –  Apr 15 '21 at 18:31

2 Answers2

2

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.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
0

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.

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226