- 12.1 Introduction
- 12.2 vector
- 12.3 list
- 12.4 forward_list
- 12.5 map
- 12.6 unordered_map
- 12.7 Allocators
- 12.8 Container Overview
- 12.9 Advice
This chapter is from the book
This chapter is from the book
This chapter is from the book
12.8 Container Overview
The standard library provides some of the most general and useful container types to allow the programmer to select a container that best serves the needs of an application:
Standard Container Summary |
|
|---|---|
vector<T> |
A variable-size vector (§12.2) |
list<T> |
A doubly-linked list (§12.3) |
forward_list<T> |
A singly-linked list |
deque<T> |
A double-ended queue |
map<K,V> |
An associative array (§12.5) |
multimap<K,V> |
A map in which a key can occur many times |
unordered_map<K,V> |
A map using a hashed lookup (§12.6) |
unordered_multimap<K,V> |
A multimap using a hashed lookup |
set<T> |
A set (a map with just a key and no value) |
multiset<T> |
A set in which a value can occur many times |
unordered_set<T> |
A set using a hashed lookup |
unordered_multiset<T> |
A multiset using a hashed lookup |
The unordered containers are optimized for lookup with a key (often a string); in other words, they are hash tables.
The containers are defined in namespace std and presented in headers <vector>, <list>, <map>, etc. (§9.3.4). In addition, the standard library provides container adaptors queue<T>, stack<T>, and priority_queue<T>. Look them up if you need them. The standard library also provides more specialized container-like types, such as array<T,N> (§15.3.1) and bitset<N> (§15.3.2).
The standard containers and their basic operations are designed to be similar from a notational point of view. Furthermore, the meanings of the operations are equivalent for the various containers. Basic operations apply to every kind of container for which they make sense and can be efficiently implemented:
Standard Container Operations (partial) |
|
|---|---|
value_type |
The type of an element |
p=c.begin() |
p points to first element of c; also cbegin() for an iterator to const |
p=c.end() |
p points to one-past-the-last element of c; also cend() for an iterator to const |
k=c.size() |
k is the number of elements in c |
c.empty() |
Is c empty? |
k=c.capacity() |
k is the number of elements that c can hold without a new allocation |
c.reserve(k) |
Increase the capacity to k; if k<=c.capacity(), c.reserve(k) does nothing |
c.resize(k) |
Make the number of elements k; added elements have the default value value_type{} |
c[k] |
The kth element of c; zero-based; no range guaranteed checking |
c.at(k) |
The kth element of c; if out of range, throw out_of_range |
c.push_back(x) |
Add x at the end of c; increase the size of c by one |
c.emplace_back(a) |
Add value_type{a} at the end of c; increase the size of c by one |
q=c.insert(p,x) |
Add x before p in c |
q=c.erase(p) |
Remove element at p from c |
c=c2 |
Assignment: copy all elements from c2 to get c==c2 |
b=(c==c2) |
Equality of all elements of c and c2; b==true if equal |
x=(c<=>c2) |
Lexicographical order of c and c2: x<0 if c is less than c2, x==0 if equal, and 0<x if greater than. !=, <, <=, >, and >= are generated from <=> |
This notational and semantic uniformity enables programmers to provide new container types that can be used in a very similar manner to the standard ones. The range-checked vector, Vector (§4.3, Chapter 5), is an example of that. The uniformity of container interfaces allows us to specify algorithms independently of individual container types. However, each has strengths and weaknesses. For example, subscripting and traversing a vector is cheap and easy. On the other hand, vector elements are moved to different locations when we insert or remove elements; list has exactly the opposite properties. Please note that a vector is usually more efficient than a list for short sequences of small elements (even for insert() and erase()). I recommend the standard-library vector as the default type for sequences of elements: you need a reason to choose another.
Consider the singly-linked list, forward_list, a container optimized for the empty sequence (§12.3). An empty forward_list occupies just one word, whereas an empty vector occupies three. Empty sequences, and sequences with only an element or two, are surprisingly common and useful.
An emplace operation, such as emplace_back() takes arguments for an element’s constructor and builds the object in a newly allocated space in the container, rather than copying an object into the container. For example, for a vector<pair<int,string>> we could write:
v.push_back(pair{1,"copy or move"}); // make a pair and move it into v
v.emplace_back(1,"build in place"); // build a pair in v
For simple examples like this, optimizations can result in equivalent performance for both calls.