Most elegant way to make an Ordered Set?

[LB]

Using only the C++ Standard Library (e.g. without Boost), what is the simplest, most elegant way to have an Ordered Set container? That is, a container which does not allow duplicate elements (like std::set) but also preserves the exact order of elements (like std::vector, no sorting involved)?

I actually do need this for a project - I want to have an ordered set of parameter names - the specific order I define is important as well as that no two names are the same. The container containing all this will then be used as the key to a map, so no multi-container solutions are allowed.

Example program:

template<typename... T>
using ordered_set = /*container*/<T...>;

                    /*name*/                 /*param*/
std::map<std::pair<std::string, ordered_set<std::string>>, std::function</**/>> funcs
{
    {{"f", {"a", "b"}}, [](/**/) -> /**/ { /**/ }}, //valid
    {{"f", {"a", "b"}}, [](/**/) -> /**/ { /**/ }}, //duplicate
    {{"f", {"b", "a"}}, [](/**/) -> /**/ { /**/ }}, //valid, not a duplicate
    {{"f", {"a", "a"}}, [](/**/) -> /**/ { /**/ }}  //invalid
};

Effectively, the map key is the function signature and the map value is the function that will process the given values for the parameters. (Don't worry about the signature of the functions for this - they will just take a map of parameters to their values)

[TwilightSpectre]

Do you just want a std::unordered_set? That appears to me to be what you want, though I could be wrong.

[LB]

The precise order of the elements in the set is important to me, such that {"a", "b"} does not equal {"b", "a"}

http://ideone.com/6kl3bH

With an ordered set, the test would compare false.

[MiiNiPaa]

Ok, so you want Ordered set which does not have special ordering? It is like cooking scrambled eggs without eggs. Ordering is a needed property for logarithmic access times in a set.

I could suggest to create new container inherited from std::vector, add input validation to push_back() method and forbid some other access methods.

[TwilightSpectre]

Well, as far as I can find, there are no std containers that operate like you want. You can probably inherit something like a vector to do it for you, but apart from that I honestly don't know.

[LB]

Of course I am willing to sacrifice logarithmic access times - the number of parameters will generally be so low that it will not make a difference.

I'm working on using std::vector as a base, if you come up with your own version that works well let me know.

[LB]

What do you think of this implementation?

http://ideone.com/iyq6la
http://ideone.com/F0V42m (fixed a bug)

[Cubbi]

the decision to avoid boost usually means you're going to rewrite a part of it (in this case, a part of boost.multi_index)

[LB]

I'm well aware of boost::multi_index, and I don't want to introduce boost as a dependency.

[MiiNiPaa]

1) Go to the boost sorce code
2) Copy multi_index implementation
3) Past into your project

[LB]

And copy every one of its dependencies as well?

[Cubbi]

they have a tool for that ( http://www.boost.org/doc/libs/release/tools/bcp/doc/html/index.html ), but really, I can't imagine being serious about C++ and not using boost.

[LB]

For all other things I would use boost, but not here.

[tntxtnt]

what about using both std::set and std::vector in OrderedSet? std::set to check for duplicates, std::vector to preserve order.

[LB]

Check line 54; that's what I did ;)

It turns out I don't need to modify the container after constructing it, plus since it's the key to the map it can't be modified in the first place, so I have settled with the solution shown on ideone, which can be optimized if needed too.

So, Boost MultiIndex would really have been overkill.