Menu
Here http://www.cplusplus.com/reference/stl/set/ I read that std::set in C++ is "typically" implemented as a tree (red-black one?) and it is sorted.
I could not understand, does it mean that by specification iteration order of set is always ascending? Or is it only "usual implementation detail" and sometimes, some library/compiler may violate this convention?
724
What is Set in C++? As mentioned above, sets in C++ are the type of STL containers that are used for storing elements in a sorted way. The operations allowed to be performed on sets are insertion and deletion. The elements are internally sorted according to a strict weak ordering in a set type container.
What is a Set? In programming, a Set is used to store unique values of a list and also automatically providing an ordering to its elements. By default, the ordering is in ascending order.
std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare . Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.
No, it does not.
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.
(Also per the C++ standard, insertion, lookup and deletion take at most O(lg n) time, so balanced search trees are currently the only viable implementation choice for std::set, even though the use of red-black trees is not mandated by the standard.)
141
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
