I know that the STL containers like set and map are sorted but how are they actually sorted? What is the underlying structure?
I couldn't find any books about it.
I'm a C++ beginner please don't judge me. :)
Asked
Active
Viewed 724 times
4
-
5`std::map` is usually built on top of a [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree). – r3mus n0x Nov 13 '18 at 12:41
-
2@CoryKramer, the linked questions all presume that `std::map` is implemented using a red-black tree. The question "how is std::map implemented?" is a better fit. – Peter Ruderman Nov 13 '18 at 12:44
-
So both are using the red-black tree? I heard something about the strict weak ordering criterion – Shalomi90 Nov 13 '18 at 12:45
-
1I took it like the OP asking by how they are sorted ? The answer is by default they use the operator ` – darune Nov 13 '18 at 12:47
-
1@r3musn0x Why are you answering in the comments section? – Lightness Races in Orbit Nov 13 '18 at 16:44
-
@LightnessRacesinOrbit I thought the same :) – Shalomi90 Nov 13 '18 at 20:11
1 Answers
4
For both std::map and std::set, it is implementation defined how the sorting is being done. The underlying data structure should sort the elements somehow:
Internally, the elements in a
mapare always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).
(same holds for set.)
A typical data structure for these containers is red black tree or a binary search tree.
gsamaras
- 69,751
- 39
- 173
- 279