What are Containers/Adapters? C++

A container is a specific data structure that contains data, usually in an unbounded amount. Each container type has limitations on how to access, add, or remove data efficiently.

Below are a few examples of containers using STL classes.

Sequence Containers

Here are the sequence containers, meaning the data is reliably ordered (that is, there is a front and a back to them. I do NOT mean that they automatically sort themselves!).

• A vector is a bit like a flexibly-sized array. Vectors are random-access, meaning you can access any element with integer index in constant time (just like an array). You can add or remove from the back of the vector in amortized constant time as well. Anywhere else, though, and you're probably looking at having to recopy potentially all of the elements.
• A deque, or double-ended queue, is like a vector but you can add to the front or the back in amortized constant time. You can still access elements in constant time, but deque elements are not guaranteed to be contiguous in memory like vectors or arrays.
• A list is a linked list, meaning data which are linked together by pointers. You have constant-time access to the beginning and the end, but in order to get anywhere in the middle you need to iterate through the list. You can add elements anywhere in the list in constant time, though, if you already have a pointer to one of the nearby nodes.

Associative Containers

These are associative containers, meaning that elements are no longer ordered but instead have associations with each other used for determining uniqueness or mappings:

• A set is a container with unique elements. You can only add one of each element to a set; any other additions are ignored.
• A multiset is like a set, but you can put more than one of an element in. The multiset keeps track of how many of each kind of element are in the structure.
• A map, also known as an associative array, is a structure in which you insert key-value pairs; then you can look up any value by supplying the key. So it's a bit like an array that you can access with a string index (key), or any other kind of index. (If you insert another key-value pair and the key already exists, then you just overwrite the value for the original key.)
• A multimap is a map that allows for insertion of multiple values for the same key. When you do a key lookup, you get back a container with all the values in it.

Container Adapters

Container adapters, on the other hand, are interfaces created by limiting functionality in a pre-existing container and providing a different set of functionality. When you declare the container adapters, you have an option of specifying which sequence containers form the underlying container. These are:

• A stack is a container providing Last-In, First-Out (LIFO) access. Basically, you remove elements in the reverse order you insert them. It's difficult to get to any elements in the middle. Usually this goes on top of a deque.
• A queue is a container providing First-In, First-Out (FIFO) access. You remove elements in the same order you insert them. It's difficult to get to any elements in the middle. Usually this goes on top of a deque.
• A priority_queue is a container providing sorted-order access to elements. You can insert elements in any order, and then retrieve the "lowest" of these values at any time. Priority queues in C++ STL use a heap structure internally, which in turn is basically array-backed; thus, usually this goes on top of a vector.

See this reference page for more information, including time complexity for each of the operations and links to detailed pages for each of the container types.

<joke>C++ is technical and hard to understand :-D</joke>

Containers are data types from STL that can contain data.

Example: vector as a dynamic array

Adapters are data types from STL that adapt a container to provide specific interface.

Example: stack providing stack interface on top of the chosen container

(side note: both are actually templates not data types, but the definition looks better this way)

The technical definition of "container" from The SGI STL documentation is pretty good:

A Container is an object that stores other objects (its elements), and that has methods for accessing its elements. In particular, every type that is a model of Container has an associated iterator type that can be used to iterate through the Container's elements.

So, a container is a data structure that holds ("contains") a collection of objects of some type. The key idea is that there are different types of containers, each of which stores objects in a different way and provides different performance characteristics, but all of them have a standard interface so that you can swap one out for another easily and without modifying too much of the code that uses the container. The idea is that the containers are designed to be interchangeable as much as possible.

The container adapters are classes that provide a subset of a container's functionality but may provide additional functionality that makes it easier to use containers for certain scenarios. For example, you could easily use std::vector or std::deque for a stack data structure and call push_back, back, and pop_back as the stack interface; std::stack provides an interface that can use a std::vector or std::deque or other sequence container but provides the more standard push, top, and pop member functions for accessing members.