0

I have read many things about STL containers (Sequence Containers, Associative Container, Container adapters) but I still don't understand the internal form for each of them.

I want a visualization form supported with pictures to every container in STL, (ex: what is the form of data inside the container) if possible.

I hope that my question is clear.

Lion King
  • 32,851
  • 25
  • 81
  • 143
  • 1
    pretty print containers, http://stackoverflow.com/questions/4850473/pretty-print-c-stl-containers – aaronman Jul 15 '14 at 16:36
  • 4
    While the behavior of the containers is specified, the implementation and internal workings and structures is not specified in any way, so two different libraries will most likely be different, even two versions of the same library may be different. – Some programmer dude Jul 15 '14 at 16:38

2 Answers2

0

The internal working of the containers is implementation independent, if the performance (Big-O) is correct and the preconditions and post-conditions of the container and his methods (ex: default constructed = empty container) are meet, the implementation is standard.

Example in VS:
1-vector of T - buffer (T[], T*). Normal internal representation is 3 pointer, begin and end of the buffer and current element.
2-deque of T - implemented in similar way to vector, but inserted element not need to be one after the other, because the container support inserting before and after with O(1) normally if you create deque it begin empty as all container, suppose a value is inserted from back, in this case is inserted in position 0, if a value is inserted from front is inserted in position capacity of deque (until the two index begin and end encounter, in this case grow is needed, and copy, like vector, and order of the value updated). Normal internal representation is pointer to begin and end of the buffer, first and last element of the deque.
3-list of T - double linked list (node with next, previous and T)
4-asociative of T (set, multiset, map, multimap) - Red Black Tree with value T or pair in case of maps like. Normal internal representation is left and right Node and value (used for sort)
5-unordered asociative of T (unordered_set, multiset ...): hash map implementation new in C++11. 6-Adaptor - the underlying representation is one of the previous containers (ex: stack is an adapter that is implemented by default with deque), in instantiation time one can change the underlying representation to tweak performance Big-O according to constrain (it may require Random Access, Forward, etc...).

This specifics can change in any version of the libraries, when any optimization is founded, and in any other case. For example some implementation of vector have pointer to begin, capacity (instead of end), and current element.

NetVipeC
  • 4,402
  • 1
  • 17
  • 19
0

http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

This will help a little bit, although the underlying data structure can be vary upon implementation

David Carpenter
  • 1,389
  • 2
  • 16
  • 29
  • Very good data structure visualizations, but unfortunately a little you can be find here from `STL containers`, but thanks a lot. – Lion King Jul 15 '14 at 20:34
  • that's about the best I can find, although for example if you look at http://www.cplusplus.com/reference/map/map/ You can see that they are *usually* implemented as binary search trees. This usually means a balanced binary search tree like an AVL or Red-Black tree and then you can just look at the corresponding entry: http://www.cs.usfca.edu/~galles/visualization/AVLtree.html – David Carpenter Jul 15 '14 at 20:40