CODEWITHSUNDEEP
c++boostdata-structuresset
Lahiru
Lahiru

Reputation: 2664

c++ set data structure which keeps inserted order

Is there any C++ built-in set data structure which keeps the inserted order? It doesn't a problem whether the set is a hash set or a set implemented by a balanced binary tree.

Upvotes: 6

Views: 2122

Answers (3)

jakirkham
jakirkham

Reputation: 715

Boost guarantees that all associative containers preserve insertion ordering.

a_eq.insert(t): If a range containing elements equivalent to t exists in a_eq, t is inserted at the end of that range.

ref: https://www.boost.org/doc/libs/1_68_0/doc/html/container/cpp_conformance.html#container.cpp_conformance.insertion_hints

Upvotes: 1

Minkus CNB
Minkus CNB

Reputation: 67

I am not 100% sure if I understand what you are asking, but it sounds to me like a linked list would sufficiently suit your needs. You can just push and pop to keep the list in the order you placed it in. You can look here for a reference: http://www.cplusplus.com/reference/list/list/

Furthermore, you can use the unique method to remove duplicates making it emulate a set data structure.

Upvotes: 1

Mark Garcia
Mark Garcia

Reputation: 17708

In C++11, both std::multiset and std::multimap are guaranteed to preserve the insertion order of same-valued/same-keyed elements.

Quoting from the C++11 standard,

23.2.4 Associative containers

4 An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. The set and map classes support unique keys; the multiset and multimap classes support equivalent keys. For multiset and multimap, insert, emplace, and erase preserve the relative ordering of equivalent elements.

It must be explicitly stated that their unordered (hash) variants, std::unordered_multiset and std::unordered_multimap does not guarantee (it is unspecified) the relative order of insertion of elements.

Upvotes: 5

Related Questions