The C++ Standard Library has a rich collection of containers. We have sequence and associative containers. Associative containers can be classified as ordered or unordered associative containers.
1 序列容器（sequence container）
Each of the sequence containers has a unique domain. Still, in 95 % of the use cases, std::vector is the right choice. std::vector can dynamically adjust its size, automatically manages its memory, and provides you with outstanding performance. In contrast, std::array is the only sequence container that cannot adjust its size at runtime. It is optimized for minimal memory and performance overhead. While std::vector is good at putting new elements at its end, you should use std::deque to put an element also at the beginning. With std::list being a doubly-linked list and std::forward_list as a singly linked list, we have two additional containers optimized for operations at arbitrary positions in the container, with high performance.
1.1 std::array
The std::array combines the memory and runtime characteristic of a C array with the interface of std::vector. std::array is a homogeneous container of fixed length.
// array.cpp
...
include
...
std::array arr{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto a: arr)
std::cout << a << " " ; // 1 2 3 4 5 6 7 8 9 10
double sum= std::accumulate(arr.begin(), arr.end(), 0);
std::cout << sum << '\n'; // 55
double mean= sum / arr.size();
std::cout << mean << '\n'; // 5.5
std::cout << (arr[0] == std::get<0>(arr)); // true
1.2 std::vector
std::vector is a homogeneous container, which length is automatically adjusted at runtime.
// vector.cpp
...
include
...
std::vector intVec1(5, 2011);
intVec1.reserve(10);
std::cout << intVec1.size() << '\n'; // 5
std::cout << intVec1.capacity() << '\n'; // 10
intVec1.shrink_to_fit();
std::cout << intVec1.capacity() << '\n'; // 5
std::vector intVec2(10);
std::cout << intVec2.size() << '\n'; // 10
std::vector intVec3{10};
std::cout << intVec3.size() << '\n'; // 1
std::vector intVec4{5, 2011};
std::cout << intVec4.size() << '\n'; // 2
1.3 std::deque
std::deque, which typically consists of a sequence of fixed-sized arrays, is quite similar to std::vector.
// deque.cpp
...
include
...
struct MyInt{
MyInt(int i): myInt(i){};
int myInt;
};
std::deque myIntDeq;
myIntDeq.push_back(MyInt(5));
myIntDeq.emplace_back(1);
std::cout << myIntDeq.size() << '\n'; // 2
std::deque intDeq;
intDeq.assign({1, 2, 3});
for(auto v: intDeq)
std::cout << v << " "; // 1 2 3
intDeq.insert(intDeq.begin(), 0);
for(auto v: intDeq)
std::cout << v << " "; // 0 1 2 3
intDeq.insert(intDeq.begin()+4, 4);
for(auto v: intDeq)
std::cout << v << " "; // 0 1 2 3 4
intDeq.insert(intDeq.end(), {5, 6, 7, 8, 9, 10, 11});
for(auto v: intDeq)
std::cout << v << " "; // 0 1 2 3 4 5 6 7 8 9 10 11
for(auto revIt= intDeq.rbegin(); revIt != intDeq.rend(); ++revIt)
std::cout << *revIt << " "; // 11 10 9 8 7 6 5 4 3 2 1 0
intDeq.pop_back();
for(auto v: intDeq)
std::cout << v << " "; // 0 1 2 3 4 5 6 7 8 9 10
intDeq.push_front(-1);
for(auto v: intDeq)
std::cout << v << " "; // -1 0 1 2 3 4 5 6 7 8 9 10
1.4 std::list
std::list is a doubly linked list.
// list.cpp
...
include
...
std::list list1{15, 2, 18, 19, 4, 15, 1, 3, 18, 5,
4, 7, 17, 9, 16, 8, 6, 6, 17, 1, 2};
list1.sort();
for(auto l: list1)
std::cout << l << " ";
// 1 1 2 2 3 4 4 5 6 6 7 8 9 15 15 16 17 17 18 18 19
list1.unique();
for(auto l: list1)
std::cout << l << " ";
// 1 2 3 4 5 6 7 8 9 15 16 17 18 19
std::list list2{10, 11, 12, 13, 14};
list1.splice(std::find(list1.begin(), list1.end(), 15), list2);
for(auto l: list1)
std::cout << l << " ";
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1.5 std::forward_list
std::forward_list is a singly linked list.
// forwardList.cpp
...
include
...
using std::cout;
std::forward_list forw;
std::cout << forw.empty() << '\n'; // true
forw.push_front(7);
forw.push_front(6);
forw.push_front(5);
forw.push_front(4);
forw.push_front(3);
forw.push_front(2);
forw.push_front(1);
for(auto i: forw)
cout << i << " "; // 1 2 3 4 5 6 7
forw.erase_after(forw.before_begin());
cout<< forw.front(); // 2
std::forward_list forw2;
forw2.insert_after(forw2.before_begin(), 1);
forw2.insert_after(++forw2.before_begin(), 2);
forw2.insert_after(++(++forw2.before_begin()), 3);
forw2.push_front(1000);
for(auto i= forw2.cbegin();i != forw2.cend(); ++i)
cout << i << " ";
// 1000 1 2 3
auto IteratorTo5= std::find(forw.begin(), forw.end(), 5);
forw.splice_after(IteratorTo5, std::move(for2));
for(auto i= forw.cbegin(); i != forw.cend(); ++i)
cout << i << " ";
// 2 3 4 5 1000 1 2 3 6 7
forw.sort();
for(auto i= forw.cbegin(); i != forw.cend(); ++i)
cout << i << " ";
// 1 2 2 3 3 4 5 6 7 1000
forw.reverse();
for(auto i= forw.cbegin(); i != forw.cend(); ++i)
cout << i << " ";
// 1000 7 6 5 4 3 3 2 2 1
forw.unique();
for(auto i= forw.cbegin(); i != forw.cend(); ++i)
cout << *i << " ";
// 1000 7 6 5 4 3 2 1
2 associative container
All eight ordered and unordered containers have in common that they associate a key with a value. You can use the key to get the value. To classify the associative containers, you have to answer three simple questions:
• Are the keys sorted?
• Does the key have an associated value?
• Can a key appear more than once?
The following table with 2^3= 8 rows gives the answers to the three questions.
There are special rules for the key and the value of an associative container.
Ordered
associative container
Unordered
associative container
The key has to be
sortable (by default <),
equal comparable,
available as hash value,
copyable and moveable.
copyable or moveable.
The value has to be
default constructible,
default constructible,
copyable and moveable.
copyable or moveable.
Associative containers are containers of key-value pairs. They provide their values by their respective key. A typical use case for an associative container is a phone book, where you use the key family name to retrieve the value phone number. C++ has eight different associative containers. On one side are the associative containers with ordered keys: std::set, std::map, std::multiset and std::multimap. On the other side, there are the unordered associative containers: std::unorderedset, std::unordered- map, std::unordered_multiset, and std::unordered_multimap.
2.1 std::map
Often, std::map is called an associative array, because std::map supports the index operator like a sequence container. The subtle difference is that its index is not restricted to a number like in the case of std::vector. Its index can be almost any arbitrary type.
/
template < class key, class val, class Comp= less,
class Alloc= allocator >
class map; /
include
...
std::map> int2Str{
{5, "five"}, {1, "one"}, {4, "four"}, {3, "three"},
{2, "two"}, {7, "seven"}, {6, "six"} };
for (auto p: int2Str)
std::cout << "{" << p.first << "," << p.second << "} ";
// {7,seven} {6,six} {5,five} {4,four} {3,three} {2,two} {1,one}
2.2 std::unordered_map
std::unordered_map's keys are not sorted, but the key is hashed to an array's index.
template< class key, class val, class Hash= std::hash,
class KeyEqual= std::equal_to,
class Alloc= std::allocator>>
class unordered_map;
For user-defined types used as a key for an unordered associative container, you must keep two requirements in mind. They need a hash function and have to be comparable to equal.
// unorderedMapHash.cpp
...
include
...
struct MyInt{
MyInt(int v):val(v){}
bool operator== (const MyInt& other) const {
return val == other.val;
}
int val;
};
struct MyHash{
std::size_t operator()(MyInt m) const {
std::hash hashVal;
return hashVal(m.val);
}
};
std::ostream& operator << (std::ostream& st, const MyInt& myIn){
st << myIn.val ;
return st;
}
typedef std::unordered_map MyIntMap;
MyIntMap myMap{
{MyInt(-2), -2}, {MyInt(-1), -1}, {MyInt(0), 0}, {MyInt(1), 1}};
for(auto m : myMap)
std::cout << "{" << m.first << "," << m.second << "} ";
// {MyInt(1),1} {MyInt(0),0} {MyInt(-1),-1} {MyInt(-2),-2}
std::cout << myMap[MyInt(-2)] << '\n'; // -2
Since C++98, C++ has ordered associative containers; with C++11, C++ has, in addition, unordered associative containers. Both classes have a very similar interface.
// orderedUnorderedComparison.cpp
/
template < class key, class val, class Comp= less,
class Alloc= allocator >
class map;
template < class T, class Comp = less,
class Alloc = allocator >
class set; /
...
include
include
// std::map
std::map m {
{"Dijkstra", 1972}, {"Scott", 1976}};
m["Ritchie"]= 1983;
std::cout << m["Ritchie"]; // 1983
for(auto p : m)
std::cout << "{" << p.first << "," << p.second << "}";
// {Dijkstra,1972},{Ritchie,1983},{Scott,1976}
m.erase("Scott");
for(auto p : m)
std::cout << "{" << p.first << "," << p.second << "}";
// {Dijkstra,1972},{Ritchie,1983}
m.clear();
std::cout << m.size() << '\n'; // 0
// std::unordered_map
std::unordered_map um {
{"Dijkstra", 1972}, {"Scott", 1976}};
um["Ritchie"]= 1983;
std::cout << um["Ritchie"]; // 1983
for(auto p : um)
std::cout << "{" << p.first << "," << p.second << "}";
// {Ritchie,1983},{Scott,1976},{Dijkstra,1972}
um.erase("Scott");
for(auto p : um)
std::cout << "{" << p.first << "," << p.second << "}";
// {Ritchie,1983},{Dijkstra,1972}
um.clear();
std::cout << um.size() << '\n'; // 0
3 Container adapter
Container adapters provide a simplified interface to the sequence containers. C++ has std::stack, std::queue, and std::priority_queue.
3.1 std:stack
The std::stack follows the LIFO principle (Last In First Out).
/
template >
class stack; /
// stack.cpp
...
include
...
std::stack myStack;
std::cout << myStack.empty() << '\n'; // true
std::cout << myStack.size() << '\n'; // 0
myStack.push(1);
myStack.push(2);
myStack.push(3);
std::cout << myStack.top() << '\n'; // 3
while(!myStack.empty()){
std::cout << myStack.top() << " ";
myStack.pop();
} // 3 2 1
std::cout << myStack.empty() << '\n'; // true
std::cout << myStack.size() << '\n'; // 0
3.2 std::Queue
//代码效果参考：http://www.zidongmutanji.com/bxxx/164948.html
The std::queue follows the FIFO principle (First In First Out).
// queue.cpp
...
include
...
std::queue myQueue;
std::cout << myQueue.empty() << '\n'; // true
std::cout << myQueue.size() << '\n'; // 0
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
std::cout << myQueue.back() << '\n'; // 3
std::cout << myQueue.front() << '\n'; // 1
while(!myQueue.empty()){
std::cout << myQueue.back() << " ";
std::cout << myQueue.front() << " : ";
myQueue.pop();
} // 3 1 : 3 2 : 3 3
std::cout << myQueue.empty() << '\n'; // true
std::cout << myQueue.size() << '\n'; // 0
3.3 std::priority_queque
The std::priority_queue is a reduced std::queue. The difference to the std::queue is that their greatest element is always at the top of the priority queue.
