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

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. ;)

Answer 2

Here's how I do it:

template <class T>
class VectorSet
{
public:
  using iterator                     = typename vector<T>::iterator;
  using const_iterator               = typename vector<T>::const_iterator;
  iterator begin()                   { return theVector.begin(); }
  iterator end()                     { return theVector.end(); }
  const_iterator begin() const       { return theVector.begin(); }
  const_iterator end() const         { return theVector.end(); }
  const T& front() const             { return theVector.front(); }
  const T& back() const              { return theVector.back(); }
  void insert(const T& item)         { if (theSet.insert(item).second) theVector.push_back(item); }
  size_t count(const T& item) const  { return theSet.count(item); }
  bool empty() const                 { return theSet.empty(); }
  size_t size() const                { return theSet.size(); }
private:
  vector<T> theVector;
  set<T>    theSet;
};

Of course, new forwarding functions can be added as needed, and can be forwarded to whichever of the two data structures implements them most efficiently. If you are going to make heavy use of STL algorithms on this (I haven't needed to so far) you may also want to define member types that the STL expects to find, like value_type and so forth.

Answer 3

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 4

If you can use Boost, a very straightforward solution is to use the header-only library Boost.Bimap (bidirectional maps).

Consider the following sample program that will display your dummy entries in insertion order (try out here):

#include <iostream>
#include <string>
#include <type_traits>
#include <boost/bimap.hpp>

using namespace std::string_literals;

template <typename T>
void insertCallOrdered(boost::bimap<T, size_t>& mymap, const T& element) {
  // We use size() as index, therefore indexing with 0, 1, ... 
  // as we add elements to the bimap.
  mymap.insert({ element, mymap.size() });
}

int main() {
  boost::bimap<std::string, size_t> mymap;

  insertCallOrdered(mymap, "stack"s);
  insertCallOrdered(mymap, "overflow"s);

  // Iterate over right map view (integers) in sorted order
  for (const auto& rit : mymap.right) {
    std::cout << rit.first << " -> " << rit.second << std::endl;
  }
}