The containers library is a collection of templates and algorithms that implement the common data structures that we work with as programmers. A container is an object that stores a collection of elements (i.e. other objects). Each of these containers manages the storage space for their elements and provides access to each element through iterators and/or member functions. The standard containers implement structures that are commonly used in our programs, such as:
- Dynamic arrays
- Queues
- Stacks
- Linked lists
- Trees
- Associative sets
The C++ container library categorizes containers into four types:
- Sequence containers
- Sequence container adapters
- Associative containers
- Unordered associative containers
Sequence containers
Sequence containers are used for data structures that store objects of the same type in a linear manner. The STL Sequence Container types are:
- array : represents a static contiguous array
- vector : represents a dynamic contiguous array
- forward_list : represents a singly-linked list
- list : represents a doubly-linked list
- deque : represents a double-ended queue, where elements can be added to the front or back of the queue.
Sequence container adapters
Container adapters are a special type of container class. They are not full container classes on their own, but wrappers around other container types (such as a vector, deque, or list). These container adapters encapsulate the underlying container type and limit the user interfaces accordingly. The standard container adapters are:
- stack : provides an LIFO data structure
- queue : provides a FIFO data structure
- priority_queue : provides a priority queue, which allows for constant-time lookup of the largest element (by default)
Associative Container
Associative containers provide sorted data structures that provide a fast lookup using keys. The STL Associative Container types are can be divided in two ways: containers which require unique keys, and those which allow multiple entries using the same key.
- Keys are unique
- set : Collection of unique keys, sorted by keys
- map : Collection of key-value pairs, sorted by keys
- Multiple entries for the same key are permitted
- multiset : Collection of keys, sorted by keys
- multimap : Collection of key-value pairs, sorted by keys
set and map are typically implemented using red-black trees.
Unordered Associative Container
Unordered associative containers provide unsorted data structures that can be accessed using a hash. For all STL Unordered Associative Container types, a hashed key is used to access the data. The standard types are split between those that require unique keys, and those that do not:
- Keys are unique
- unordered set : Collection of keys, hashed by keys
- unordered_map : Collection of key-value pairs, hashed by keys
- Multiple entires for the same key are permitted
- unordered_multiset : Collection of keys, hashed by keys
- unordered_multimap : Collection of key-value pairs, hashed by keys