Preserving insertion order on a std::set or std::unordered_set

Question

Before marking this as duplicate, I have been here, here, and here, a duplicate of the first.

I'm aware of boost::multi_index, and use an environment where I lack it, and that a std::unordered_set is not bound to store elements in a deterministic insertion order.

I find the concept of using two containers, say an additional std::vector as uncouth.

What I would love is a solution involving a comparator that I can use in a std::set's template parameters (clarification, this could be a trivial functor struct, containing a bool operator()() overload, a regular function, or a lambda). Is it possible?

Addenda

1. Initialization must occur through a std:: container's begin iterator/end iterator constructor, such as in this snippet.

   std::string str; cin >> str;
   std::set<char>(str.begin(), str.end());
   

2. Also, another interesting use-case would be to create a dumb hash wrapping functor that allows insertion order to be pushed in to a std::unordered_set's template parameter.

Answer 1

You cannot directly have a lambda expression as the set's template parameter, because a lambda expression is a value, and the set's template parameter is a type. The obvious correction of the question, whether a construction using a lambda and decltype can work, leads to the interesting problem that a lambda expression denotes a unique type (a "closure type"), so you can never make two separate lambda expressions of the same closure type.*

However, in a more abstract sense what you want can be achieved in a local context using template argument deduction, for example:

template <typename F>
int f(int* first, int* last, F comp)
{
    std::set<int, F> s(comp);
    while (first != last) s.insert(*first++);
    ...
}

Now you can call f with a lambda expression as the argument, thus effectively "using a lambda as the set's comparator". Or, for a simpler example, you could just have a named variable for the lambda (putting all the template deduction into a single auto:

auto comp = [](...) { ... };
std::set<int, decltype(comp)> s(comp);

_{*) There is a proposal to allow lambdas in unevaluated contexts to address this point, but its outlook is uncertain. It has interesting side effects like making closure types affect name mangling.}

Answer 2

An adt that preserves the order of insertion is an std::vector. You can just as easily wrap it like this to get an std::set-like behavior:

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

template < typename T >
class VectorSet : public vector<T> {
public:
    using iterator = typename vector<T>::iterator;
    using value_type = typename vector<T>::value_type;

    pair<iterator, bool> insert (const value_type& val) {
        auto it = ::find(this->begin(), this->end(), val);
        if (it == this->end())
            it = ::vector<T>::insert(this->end(), val);

        return pair<iterator, bool>(it, true);
    }
};

int main()
{
    VectorSet<int> my;
    my.insert(1);
    my.insert(4);
    my.insert(3);
    my.insert(4);

    for (auto & v : my) {
        cout << v << endl;
    }

    return 0;
}

Answer 3

You cannot, unless you use additional indexes. Two approaches:

1. using an explicit index

Live On Coliru

#include <set>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

#include <iostream>

string read_word() {
    string str;
    cin >> str;
    return str;
}

int main() {
    using Ref = std::reference_wrapper<char const>;

    auto const str = read_word();
    std::cout << "Word: "   << str << "\n";

    auto v = [&]() -> vector<Ref> {
        set<Ref> u(str.begin(), str.end());
        return {u.begin(), u.end()};
    }();

    std::cout << "Unique: " << string(v.begin(), v.end()) << "\n";

    auto pos = [str](char ch) { return str.find(ch); };
    std::sort(v.begin(), v.end(), [pos](auto& a, auto& b) { return pos(a) < pos(b); });

    std::cout << "Insertion: " << string(v.begin(), v.end()) << "\n";
}

Prints e.g.

Word: pineapple
Unique: aeilnp
Insertion: pineal

2. using Boost Multi-Index

Same deal

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>

namespace bmi = boost::multi_index; 

using Index = bmi::multi_index_container<char, 
      bmi::indexed_by<
          bmi::sequenced<>,
          bmi::ordered_unique<bmi::tag<struct unique>, bmi::identity<char> >
      > > ;

#include <iostream>

std::string read_word() {
    std::string str;
    std::cin >> str;
    return str;
}

int main() {

    auto const str = read_word();
    std::cout << "Word: "   << str << "\n";

    Index idx(str.begin(), str.end());

    std::cout << "Insertion: " << std::string(idx.begin(), idx.end()) << "\n";

    auto& u = idx.get<unique>();
    std::cout << "Unique: " << std::string(u.begin(), u.end()) << "\n";
}

Prints

Word: pineapple
Insertion: pineal
Unique: aeilnp

Answer 4

I thought a weird solution (though not one involving any sets) could be to use a std::map of the element type and std::time_point as the key type. That will ensure insertion order if not anything at all.