Menu
Does the C++ standard library have an "ordered set" datastructure? By ordered set, I mean something that is exactly the same as the ordinary std::set but that remembers the order in which you added the items to it.
If not, what is the best way to simulate one? I know you could do something like have a set of pairs with each pair storing the number it was added in and the actual value, but I dont want to jump through hoops if there is a simpler solution.
925
Per the C++ standard, iteration over the elements in an std::set proceeds in sorted order as determined by std::less or by the optional comparison predicate template argument.
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.
By default, values of the set are sorted in ascending order.
std::set is an associative container that contains a sorted set of unique objects of type Key . Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as red-black trees.
No single, homogeneous data structure will have this property, since it is either sequential (i.e. elements are arranged in insertion order) or associative (elements are arranged in some order depending on value).
The best, clean approach would perhaps be something like Boost.MultiIndex, which allows you to add multiple indexes, or "views", on a container, so you can have a sequential and an ordered index.
138
Instead of making a std::set of whatever type you're using, why not pass it a std::pair of the object and an index that gets incremented at each insertion?
20
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
