- 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 |
A variable-size vector (§12.2) |
list |
A doubly-linked list (§12.3) |
forward_list |
A singly-linked list |
deque |
A double-ended queue |
map |
An associative array (§12.5) |
multimap |
A map in which a key can occur many times |
unordered_map |
A map using a hashed lookup (§12.6) |
unordered_multimap |
A multimap using a hashed lookup |
set |
A set (a map with just a key and no value) |
multiset |
A set in which a value can occur many times |
unordered_set |
A set using a hashed lookup |
unordered_multiset |
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 namespacestdand presented in headers,, etc. (§9.3.4). In addition, the standard library provides container adaptorsqueue
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() |
ppoints to first element ofc; alsocbegin()for an iterator toconst |
p=c.end() |
ppoints to one-past-the-last element ofc; alsocend()for an iterator toconst |
k=c.size() |
kis the number of elements inc |
c.empty() |
Iscempty? |
k=c.capacity() |
kis the number of elements thatccan hold without a new allocation |
c.reserve(k) |
Increase the capacity tok; ifk<=c.capacity(),c.reserve(k)does nothing |
c.resize(k) |
Make the number of elementsk; 添加元素的默认值value_type{} |
c[k] |
Thekth element ofc; zero-based; no range guaranteed checking |
c.at(k) |
Thekth element ofc; if out of range, throwout_of_range |
c.push_back(x) |
Addxat the end ofc; increase the size ofcby one |
c.emplace_back(a) |
Addvalue_type{a}at the end ofc; increase the size ofcby one |
q=c.insert(p,x) |
Addxbeforepinc |
q=c.erase(p) |
Remove element atpfromc |
c=c2 |
Assignment: copy all elements fromc2to getc==c2 |
b=(c==c2) |
Equality of all elements ofcandc2;b==trueif equal |
x=(c<=>c2) |
Lexicographical order ofcandc2: x<0ifcis less thanc2,x==0if equal, and0 !=,<,<=,>, 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 avectoris cheap and easy. On the other hand,vectorelements are moved to different locations when we insert or remove elements;listhas exactly the opposite properties. Please note that avectoris usually more efficient than alist(即使是短序列的小元素insert()anderase()). I recommend the standard-libraryvectoras 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 emptyforward_listoccupies just one word, whereas an emptyvectoroccupies three. Empty sequences, and sequences with only an element or two, are surprisingly common and useful.
An emplace operation, such asemplace_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 avector
v.push_back(pair{1,"copy or move"}); //make a pair and move it into vv.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.