容器种类
- 序列容器(数组，链表)
- Vector, deque, list, forward list, array
- 关联容器(二叉树)，总是有序的
- set, multiset根据值排序，元素值不能修改
- map, multimap根据key排序，键值不能修改
- 无序容器(hash 表)
- 无序set/multiset
- 无序map/multimap
序列容器
Vector
vector<int> vec; // vec.size() == 0
vec.push_back(4);
vec.push_back(1);
vec.push_back(8); // vec: {4, 1, 8}; vec.size() == 3
// Vector特定的操作:
cout << vec[2]; // 8 (没有范围检查)
cout << vec.at(2); // 8 (超出范围会抛range_error exception异常)
for (int i; i < vec.size(); i++) {
cout << vec[i] << " ";
for (list<int>::iterator itr = vec.begin(); itr!= vec.end(); ++itr)
cout << *itr << " ";
for (it: vec) // C++ 11
cout << it << " ";
// Vector是内存中一个动态分配的连续的数组
int* p = &vec[0]; p[2] = 6;
// 所有容器共有的一些成员函数
// vec: {4, 1, 8}
if (vec.empty()) { cout << "Not possible.\n"; }
cout << vec.size(); // 3
vector<int> vec2(vec); // 拷贝构造, vec2: {4, 1, 8}
vec.clear(); // 删除所有元素; vec.size() == 0
vec2.swap(vec); // 交换，vec2变成空的，vec有3个元素
// 注：没有抽象带来的开销，非常高效
/* Vector的特性:
* 1. 在末尾插入/删除很快: O(1)
* 2. 在其他地方插入/删除s慢: O(n)
* 3. 搜索慢: O(n)
*/
Deque
deque<int> deq = { 4, 6, 7 };
deq.push_front(2); // deq: {2, 4, 6, 7}
deq.push_back(3); // deq: {2, 4, 6, 7, 3}
// Deque接口跟vector类似
cout << deq[1]; // 4
/* 特性:
* 1. 在首尾插入/删除快
* 2. 中间插入/删除慢: O(n)
* 3. 搜索慢: O(n)
*/
List
* -- 双向链表
* 元素储存在内存不同的地方，cache会经常miss。很多STL实现会将其元素放到一起，但即使如此因为包含了太多指针，会消耗更多的内存(意味着更多的cache miss和page fault)
*/
list<int> mylist = {5, 2, 9 };
mylist.push_back(6); // mylist: { 5, 2, 9, 6}
mylist.push_front(4); // mylist: { 4, 5, 2, 9, 6}
list<int>::iterator itr = find(mylist.begin(), mylist.end(), 2); // itr -> 2
mylist.insert(itr, 8); // mylist: {4, 5, 8, 2, 9, 6}
// O(1), 比vector/deque更快
itr++; // itr -> 9
mylist.erase(itr); // mylist: {4, 8, 5, 2, 6} O(1)
/* 特性:
* 1. 任何地方插入/删除快: O(1)
* 2. 搜索慢: O(n)
* 3. 没有随机访问，即没有 [] 运算符
*/
// 拼接速度快
mylist1.splice(itr, mylist2, itr_a, itr_b ); // O(1)
Array
// 不能改变大小，不能元素个数的Array是不同类型
int a[3] = {3, 4, 5};
array<int, 3> a = {3, 4, 5};
a.begin();
a.end();
a.size();
a.swap();
array<int, 4> b = {3, 4, 5};
关联容器
- 基于二叉树，总是排序的，默认基于 < 排序
- 没有push_back(), push_front()
set和multiset
// 元素不能重复
set<int> myset;
myset.insert(3); // myset: {3}
myset.insert(1); // myset: {1, 3}
myset.insert(7); // myset: {1, 3, 7}, O(log(n))
set<int>::iterator it;
it = myset.find(7); // O(log(n)), it指向7
// 序列容器没有find函数
pair<set<int>::iterator, bool> ret;
ret = myset.insert(3); // 不插入新元素
if (ret.second==false)
it=ret.first; // "it"当前指向元素3
myset.insert(it, 9); // myset: {1, 3, 7, 9} O(log(n)) => O(1)，it作为插入元素位置的一个提示，并不是实际插入位置
// it 指向3
myset.erase(it); // myset: {1, 7, 9}
myset.erase(7); // myset: {1, 9}
// 注：序列容器没有这种根据元素值删除元素的erase
// multiset允许元素重复的set
multiset<int> myset;
// set/multiset: 元素值都是不能修改的
*it = 10; // *it只读
/* 特性:
* 1. 搜索快: O(log(n))
* 2. 因为也是通过指针联系(cache miss和page fault的问题)，遍历慢 (相比vector & deque)
* 3. 没有随机访问，即没有 [] 运算符
*/
map和multimap
/*
* map
* - key值不能重复
*/
map<char,int> mymap;
mymap.insert ( pair<char,int>('a',100) );
mymap.insert ( make_pair('z',200) );
map<char,int>::iterator it = mymap.begin();
mymap.insert(it, pair<char,int>('b',300)); // "it"只是一个提示
it = mymap.find('z'); // O(log(n))
// showing contents:
for ( it=mymap.begin() ; it != mymap.end(); it++ )
cout << (*it).first << " => " << (*it).second << endl;
// multimap允许键值重复
multimap<char,int> mymap;
// map/multimap:
// -- 键值不能修改
// type of *it: pair<const char, int>
(*it).first = 'd'; // Error
// 为何叫“关联”容器
// 因为value和key是关联的，set是特殊的map，value等于key
无序容器(C++ 11)
- 无序的set/multiset
- 无序的map/multimap
- 顺序是未定义的，可能随时间改变
/*
* 基本类型和string都定义了默认的hash函数
*
* 没有下标操作[]和at()
* 没有push_back()和push_front()
*/
unordered_set<string> myset = { "red","green","blue" };
unordered_set<string>::const_iterator itr = myset.find ("green"); // O(1)
if (itr != myset.end()) // 重要的检查
cout << *itr << endl;
myset.insert("yellow"); // O(1)
vector<string> vec = {"purple", "pink"};
myset.insert(vec.begin(), vec.end());
// Hash表特定的APIs:
cout << "load_factor = " << myset.load_factor() << endl; // 负载因子：总元素和总桶数的比值
string x = "red";
cout << x << " is in bucket #" << myset.bucket(x) << endl; // x位于哪个桶
cout << "Total bucket #" << myset.bucket_count() << endl; // 总的桶数
// 无序multiset，无序map和multimap也是类似
// hash冲撞 => 性能退化
/* 无序容器的特性:
* 1. 在任何位置搜索/插入都最快: O(1)
* 关联容器O(log(n))
* vector, deque O(n)
* list插入O(1) , 搜索O(n)
* 2. Unorderd set/multiset: 元素值不能改变
* Unorderd map/multimap: key不能改变
*/
Associative Array
/*
* 一般指的是map和unordered map
*/
unordered_map<char, string> day = {{'S',"Sunday"}, {'M',"Monday"}};
cout << day['S'] << endl; // 没有范围检查
cout << day.at('S') << endl; // 有范围检查
vector<int> vec = {1, 2, 3};
vec[5] = 5; // Compile Error
day['W'] = "Wednesday"; // Inserting {'W', "Wednesday}
day.insert(make_pair('F', "Friday")); // Inserting {'F', "Friday"}
day.insert(make_pair('M', "MONDAY")); // key已经存在，插入失败
day['M'] = "MONDAY"; // 可以通过下标修改值
void foo(const unordered_map<char, string>& m) {
//m['S'] = "SUNDAY";
//cout << m['S'] << endl; //编译出错，下标操作有写权限，编译器看到以为要对const变量进行写操作
auto itr = m.find('S'); //使用find替代
if (itr != m.end())
cout << *itr << endl;
}
foo(day);
//关于Associative Array:
//1. 搜索时间: unordered_map, O(1); map, O(log(n));
//2. 但是Unordered_map可能退化为O(n);
//3. 不能使用multimap和unordered_multimap, 它们的key不唯一，也没有下标操作[]
容器适配器
- 为了满足某种特殊需要，提供受限制的接口
- 通过基本的容器类实现
*
* 1. 栈 stack: LIFO, push(), pop(), top()
*
* 2. 队列 queue: FIFO, push(), pop(), front(), back()
*
* 3. 优先级队列 priority queue: 第一个元素总是具有最高优先级
* push(), pop(), top()
*/
另一种容器分类的方法
*
* 1. 基于数组的容器: vector, deque
*
* 2. 基于结点的容器: list + associative containers + unordered containers
*
* 基于数组的容器会使指针失效:
* - 原生指针，迭代器，引用
*/
vector<int> vec = {1,2,3,4};
int* p = &vec[2]; // p points to 3
vec.insert(vec.begin(), 0);
cout << *p << endl; // 2, or ?
// 运气好，打印2；运气不好，未定义