How to know, the exact data structures and algorithms used to implement a standard piece of code, like in C++ STL?

Question

I wanted to know how the stack is implemented in C++ STL, using array or linked-list, or something even more sophisticated. Also How do i know, how any standard piece of any code is implemented? I have already tried googling and writing custom code to get an idea, but it is very time consuming and sometimes 3rd party websites do not reveal any useful information.

Answer 1

I wanted to know how the stack is implemented in C++ STL, using array or linked-list, or something even more sophisticated.

std::stack is a container adaptor. It uses the container type that you provided as a template argument. By default, it uses std::deque.

How to know, the exact data structures and algorithms used to implement a standard piece of code, like in C++ STL?

By reading the source code, or documentation if available. If neither is available, then you can ask the vendor who sold you the implementation. If that is not an option either, you could try reverse-engineering (assuming that is legal for you to do), but this option is neither easy nor fast.

Although the standard doesn't explicitly specify the data structures that are to be used to implement the standard containers, their requirements are so strict that there is very little freedom for the implementation to choose. In practice:

• std::list is implemented with a double linked list
• std::forward_list .. with a singly linked list
• std::vector .. with exponentially growing dynamic array
• std::array .. with, not surprisingly, an array
• std::deque .. with a segmented array
• ordered associative containers are balanced search trees
• unordered associative containers are hash tables with chained buckets.
• std::queue and std::stack are container adaptors that use the underlying sequence container as-is.
• std::priority_queue is a container adaptor that builds an implicit binary heap on top of the argument sequence container.
• std::basic_string is similar to vector, except it is null-terminted, and has less strict requirements for invalidation of iterators, which allows the implementation to use an optimisation for small containers where the elements are stored within the container memory without dynamic allocation.

Answer 2

There is no way that is guaranteed to tell you this information. #include <stack> might trigger a magic compiler setting that implements std::stack for you.

In practise though, #include <stack> will include a file called stack from somewhere, and you can go and look at this file, and read the implementation for your particular standard library.

Be warned, this file will be hard to read - the code is optimized for correctness first, performance second, and ease of readability third. It also has to contend with the fact that user code may #define many symbols, so all the variables will probably be called things like _This