need STL set in insertion order

Question

How to store elements in set in insertion order. for example.

set<string>myset;

myset.insert("stack");
myset.insert("overflow");

If you print, the output is

overflow
stack

needed output :

stack
overflow

Answer 1

One way is to use two containers, a std::deque to store the elements in insertion order, and another std::set to make sure there are no duplicates.

When inserting an element, check if it's in the set first, if yes, throw it out; if it's not there, insert it both in the deque and the set.

One common scenario is to insert all elements first, then process(no more inserting), if this is the case, the set can be freed after the insertion process.

Answer 2

A set is the wrong container for keeping insertion order, it will sort its element according to the sorting criterion and forget the insertion order. You have to use a sequenced container like vector, deque or list for that. If you additionally need the associative access set provides you would have to store your elements in multiple containers simultaneously or use a non-STL container like boost::multi_index which can maintain multiple element orders at the same time.

PS: If you sort the elements before inserting them in a set, the set will keep them in insertion order but I think that will not address your problem.

If you don't need any order besides the insertion order, you could also store the insert number in the stored element and make that the sorting criterion. However, why one would use a set in this case at all escapes me. ;)