How is the STL set/map internally sorted?

user_6134218 0
Viewed 801

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. :)

sorting stl c++
1 Answers

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 map are 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.

user_24113200
Related