目录
1. 容器的分类与基本函数
顺序容器
关联容器
容器适配器
成员函数
2. 容器定义的类型与构造函数参数
interator、const_iterator
reverse_interator、const_reverse_interator
begin()、end()、cbegin()、cend()
rbegin()、rend()、crbegin()、crend()
reference, const_reference
引用（Reference）
常引用（Const Reference）
3. 容器内的函数
通用容器函数
顺序容器特有函数
关联容器特有函数
4. 容器内的常规操作
插入删除元素
反向迭代器
二、容器
定义：容器（container）用于存放数据的类模板。可变长数组、链表、平衡二叉树等数据结构在 STL 中都被实现为容器。
程序员使用容器时，即将容器类模板实例化为容器类时，会指明容器中存放的元素是什么类型的。
容器中可以存放基本类型的变量，也可以存放对象。对象或基本类型的变量被插入容器中时，实际插入的是对象或变量的一个复制品。
STL 中的许多算法（即函数模板），如排序、查找等算法，在执行过程中会对容器中的元素进行比较。这些算法在比较元素是否相等时通常用运算符进行，比较大小通常用<运算符进行，因此，被放入容器的对象所属的类最好重载==和<运算符，以使得两个对象用==和<进行比较是有定义的。
1. 容器的分类与基本函数
STL 对定义的通用容器分三类：顺序性容器、关联式容器和容器适配器。
顺序容器
顺序容器有以下三种：可变长动态数组 vector、双端队列 deque、双向链表 list。
它们之所以被称为顺序容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置（尾部、头部或中间某处）插入，元素就会位于什么位置。
关联容器
关联容器有以下四种：set、multiset、map、multimap。关联容器内的元素是排序的。插入元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插入元素时不能指定位置。
默认情况下，关联容器中的元素是从小到大排序（或按关键字从小到大排序）的，而且用<运算符比较元素或关键字大小。因为是排好序的，所以关联容器在查找时具有非常好的性能。
容器适配器
除了以上两类容器外，STL 还在两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能，实现了三种容器适配器：栈 stack、队列 queue、优先级队列 priority_queue。
容器都是类模板。它们实例化后就成为容器类。用容器类定义的对象称为容器对象。
例如，vector
任何两个容器对象，只要它们的类型相同，就可以用 <、<=、>、>=、==、!= 进行词典式的比较运算。假设 a、b 是两个类型相同的容器对象，这些运算符的运算规则如下。
- a == b：若 a 和 b 中的元素个数相同，且对应元素均相等，则a == b的值为 true，否则值为 false。元素是否相等是用==运算符进行判断的。
- a
- a != b：等价于 !(a == b)。
- a > b：等价于 b < a。
- a <= b：等价于 !(b < a)。
- a >= b：等价于 !(a < b)。
成员函数
所有容器都有以下两个成员函数：
- int size()：返回容器对象中元素的个数。
- bool empty()：判断容器对象是否为空。
顺序容器和关联容器还有以下成员函数：
- begin()：返回指向容器中第一个元素的迭代器。
- end()：返回指向容器中最后一个元素后面的位置的迭代器。
- rbegin()：返回指向容器中最后一个元素的反向迭代器。
- rend()：返回指向容器中第一个元素前面的位置的反向迭代器。
- erase(...)：从容器中删除一个或几个元素。该函数参数较复杂，此处省略。
- clear()：从容器中删除所有元素。
如果一个容器是空的，则 begin() 和 end() 的返回值相等，rbegin() 和 rend() 的返回值也相等。
顺序容器还有以下常用成员函数：
- front()：返回容器中第一个元素的引用。
- back()：返回容器中最后一个元素的引用。
- push_back()：在容器末尾增加新元素。
- pop_back()：删除容器末尾的元素。
- insert(...)：插入一个或多个元素。该函数参数较复杂，此处省略。
2. 容器定义的类型与构造函数参数
interator、const_iterator
- interator：当我们需要对容器元素进行修改、删除等操作时或者对象是非常量时使用
- const_iterator：当我们只是遍历容器元素，而不更改容器元素时或者对象是常量时使用
- interator：当我们需要对容器元素进行修改、删除等操作时或者对象是非常量时使用
- const_iterator：当我们只是遍历容器元素，而不更改容器元素时或者对象是常量时使用
注意：上面所说的常量是指常量容器，而不是容器内的元素为常量
建议：如果我们只是简单的遍历容器元素或者对象是常量时，一般使用const_iterator比较合适
C++11引进了两个新函数，分别为cbegin()、cend()，其两者的功能类似于begin()、end()
C++11标准之前，iterator与const_iterator都使用begin()、end()两个辅助函数遍历容器。
C++11标准之后，const_iterator既可以使用可以使用begin()、end()，也可以使用cbegin()、cend()。但是iterator还是只能使用begin()、end()
| 1 2 3 4 | vector const vector auto it1=v.begin(); //v1是vector auto it2=v2.cbegin();//v2是vector |
reverse_interator、const_reverse_interator
功能与interator、const_iterator均相同，但是用法不一样
- reverse_interator：与interator相同，改变容器内部元素时使用。只能使用rbegin()、rend()
- const_reverse_interator：与const_iterator相同，只是单纯遍历容器内部元素时使用。能使用rbegin()、rend()、crbegin()、crend()
用法的原理与interator、const_iterator是相同的
但是rbegin()、rend()分别指向容器元素的最后一个位置与第一个元素的前一个位置
| 1 2 3 4 5 6 7 8 9 | //for循环打印的是3、2、1
vector vector v.push_back(1); v.push_back(2); v.push_back(3); for (iter = v.rbegin(); iter != v.rend(); iter++) printf("%dt", *iter); |
begin()、end()、cbegin()、cend()
4者都是容器的成员函数
begin()、end()代表容器的特殊位置，分别为元素的第一个位置与最后一个元素的下一个位置
下面比如是vector的一个模型，则begin()、end()分别代表一下位置
- begin()：我们在遍历容器的元素的时候，一般要获取该元素的首元素，因此设计bengin()
- end()：当我们用迭代器遍历容器的时候，一般需要结束条件(如遍历到最后一个元素)，但是遍历到最后一个元素时又不能舍弃它，因此将最后一个元素的下一位置作为结束标志
rbegin()、rend()、crbegin()、crend()
这四者的原理与begin()、end()、cbegin()、cend()是相同的，也都是容器的成员函数
- cbegin();cend()分别返回const类型的指向容器头的迭代器、指向容器尾的迭代器。
但是rbegin()、rend()分别代表最后一个元素与第一个元素的前一个位置
reference, const_reference
引用（Reference）
C语言中，使用指针（Pointer）可以间接获取、修改某个变量的值，C++中，使用引用可以起到跟指针类似的功能。
引用相当于是变量的别名（基本数据类型、枚举、结构体、类、指针、数组等，都可以有引用）。
在定义的时候就必须初始化，一旦指向了某个变量，就不可以再改变。
对引用做计算相当于对引用所指向的变量做计算。
可以利用引用初始化另一个引用，相当于某个变量的多个别名。
引用的价值：比指针更安全、函数返回值可以被赋值。
不存在：引用的引用、指向引用的指针、引用数组
引用的本质就是指针，只是编译器削弱了它的功能，所以引用就是弱化了的指针；一个引用占一个指针的大小。
int main() {
int age = 10;
int height = 20;
int &ref = age;//引用在定义的时候就必须初始化
//int &ref = height;//错误 一旦指向某个变量就不可以改变
int &ref1 = ref;
cout <<"ref1="<常引用（Const Reference）
引用被const修饰，这样就无法通过引用修改数据了，被称为常引用。
const必须写在&符号的左边，才能算是常引用。
const引用的特点：
可以指向临时数据（常量、表达式、函数返回值等）。
可以指向不同类型的数据。
作为函数参数时（此规则也是用于comst指针）：可以接受const和非const实参（非const引用，只能接受非const实参）；可以跟非const引用构成重载。
当常引用指向了不同类型的数据时，会产生临时变量，即引用指向的并不是初始化时的那个变量。
int fun() {
return 6;
}
int sum( int& v1, int& v2) {
cout << " sum( int& v1, int& v2)" << endl;
return v1 + v2;
}
int sum(const int &v1,const int &v2) {
cout << " sum(const int &v1,const int &v2)" << endl;
return v1 + v2;
}//与上面的sum构成重载
int main() {
int a = 1;
int b = 2;
//int &ref = a;
//const int &ref = 10;//const引用指向临时数据 不用const修饰就报错
//const int &ref = a + b;//const引用指向表达式
const int &ref = fun();//const引用指向函数返回值
sum(a, b);//非const实参 也是可以被const引用接受；
const int c = 3;
const int d = 4;
sum(c, d);//const实参
sum(10, 20);//常量也是const类型的实参
const int& aref = a;
a = 30;
cout << " aref= " << aref << endl;//打印出等于30
const long& bref = b;
b = 20;
cout << " bref= " << bref << endl;//打印出等于2 当常引用指向了不同类型的数据时，会 产生临时变量，即引用指向的并不是初始化时的那个变量。
}
pointer, const_pointer
size_type
value_type
key_type pair
mapped_type
key_compare
value_compare
конструктор без параметров
(n
x = T())
vector a{1, 2, 4};
vector a = {1, 2, 4};
3. 容器内的函数
-
通用容器函数
operator=
(other)
iterator
begin
()
void
clear
()
bool
empty
() const
iterator
end
()
size_type
max_size
() const
reverse_iterator
rbegin
()
reverse_iterator
rend
()
size_type
size
() const
void
swap
(other)
-
顺序容器特有函数
void
assign
(n, x)
void
assign
(InIterFirst, InIterLast)
void
assign
(init_list)
STL中不同容器之间是不能直接赋值的，assign（）可以实现不同容器但相容的类型赋值，如:
list names;
vector oldstyle = { "I","love","you" };
//names = oldstyle;错误！不同的类型不能执行"="操作
names.assign(oldstyle.cbegin(), oldstyle.cend());
list::iterator it;
for (auto it = names.begin(); names.begin() != names.end(); it++)
cout << *it << " ";
reference
operator[](n) {vector, deque, string}
reference
at(n) {vector, deque, string}
reference
back() {vector, deque, list, string}
reference
front
() {
vector, deque, list, string(C++11)}
size_type
capacity
() const {
vector, string}
T* data() {vector(C++11), string}
iterator
emplace(pos, arg1, arg2, …) {vector(C++11), deque(C++11), list(C++11)}
void
emplace_back(arg1, arg2, …) {vector(C++11), deque(C++11), list(C++11)}
void
emplace_front(arg1, arg2, …) {deque(C++11), list(C++11)}
iterator
erase
(pos)
iterator
erase
(first, last)
iterator
insert
(pos, x)
void
insert
(pos, n, x)
void
insert
(pos, InIterFirst, InIterLast)
iterator
insert
(pos, InIterFirst, InIterLast)
iterator
insert
(pos, init_list)
void
pop_back() {vector, deque, list, string(C++11) }
void
pop_front() {deque, list}
void
push_back
(x)
void
push_front(x) {deque, list}
void
reserve(n) {vector, string}
void
resize
(n, x = T())
void
shrink_to_fit() {vector(C++11), deque(C++11), string(C++11)}
List特有函数
void
merge
(lst
[
, comp
]
)
void
remove
(x)
void
remove_if
(pred)
void
reverse
()
void
sort
(
[
comp
]
)
void
splice
(pos, lst)
void
splice
(pos, lst, pos_lst)
void
splice
(pos, lst, first_lst, last_lst)
void
unique
(
[
pred
]
)
-
关联容器特有函数
T&
operator[](k) {map}
T&
at(k) {map}
size_type
count
(k) const
pair
emplace(arg1, arg2, …) {set(С++11), map(С++11)}
iterator
emplace(arg1, arg2, …) {multiset(С++11), multimap(С++11)}
iterator
emplace_hint
(hintpos, arg1, arg2, …)
pair
equal_range
(k)
size_type
erase
(k)
void
erase
(pos)
void
erase
(first, last)
iterator
erase
(pos)
iterator
erase
(first, last)
iterator
find
(k)
pair insert(x) {set, map}
iterator insert(x) {multiset, multimap}
iterator
insert(hintpos, x) {set, map, multiset, multimap}
void
insert
(InIterFirst, InIterLast)
void
insert
(init_list)
key_compare
key_comp
() const
iterator
lower_bound
(k)
iterator
upper_bound
(k)
value_compare
value_comp
() const
4. 容器内的常规操作
-
插入删除元素
4.1 顺序（序列）容器
顺序容器插入操作：
最重要的函数是insert，有下面三种重载形式：
iterator insert(iterator here,value_type const& item)
//在指定位置前插入item，并返回新插入项目的迭代器。
void insert(iterator here,size_type n,value_type const& item)
//在指定位置前插入n个item副本
template
void insert(iterator here,inputIterator first,inputIterator last)
//将范围[first,last)的值直接复制到容器中here之前。
还有两个函数：push_front：在容器头部插入项目，push_back在容器尾部插入项目。
容器类型只会提供能用常数复杂度实现的函数，因此，vector提供push_back但没有push_front，而list和deque同时提供push_front和push_back。
顺序容器的清除操作：
erase：两种erase形式：
iterator erase(iterator pos)
//清楚pos所指向的项目，并返回其后继项目的迭代器。
iterator erase（iterator first，iterator last）
//清楚范围[first,last)的全部项目，并返回指向最后一个删除项目的后一项目的迭代器。
clear：会清除容器内所有项目。
除了这两个基本的清除函数外，顺序容器还使用pop_front来清除容器头部的项目，pop_back清除尾部的项目。
类似push函数，vector提供了pop_back,而list和deque均提供pop_back和pop_front。
（1）vector
典型的顺序容器，任意元素的读取、修改具有O(1)，在序列尾部进行插入、删除是O(1)，但在序列的头部插入、删除的时间复杂度是O(n)，可以在任何位置插入新元素，有随机访问功能，插入删除操作需要考虑。
（2）deque
序列容器，内存也是连续的，和vector相似，区别在于在序列的头部插入和删除操作也是O(1), 可以 在任何位置插入新元素，有随机访问功能。
（3）list
序列容器，内存是不连续的，任意元素的访问、修改时间复杂度是O(n)，插入、删除操作是O(1), 可以在任何位置插入新元素。
4.2 关联容器
插入操作：
关联容器的插入操作函数insert存在几种形式，和顺序容器的主要区别在于，它不需要提供一个位置(有一种形式需要提供一个提示性的位置)。
insert的行为与容器是否允许重复项目有关。类型set、map、unordered_set、unordered_map要求唯一键，而multiset、multimap、unordered_multiset和unordered_multiset允许重复键。
interator insert(value_type const& iterm)
std::pairinsert(value_type const& item)
它会试图把item插入到容器中。如果容器允许重复键，则insert一定成功，并返回指向新插入项目的迭代器；而如果容器要求唯一键，则仅当该项目不在容器中时才插入成功。它返回包含一个迭代器和一个bool类型的pair，item被插入是bool为真。
iterator insert（iterator hint,value_type const& item）
它会尝试把item插入到容器中，如果容器允许重复键，则insert一定会成功；否则仅当该项不在容器中时insert才会插入该项。在两种情况下insert均会返回指向新插入项目或已存在的项目的迭代器。
template
void insert(inputIterator first,inputIterator last)
它会把范围[first,last)的值复制到容器中，对于有序容器，如果范围[first,last)有序，则性能有所提高。
清除操作：
erase:
void erase(iterator pos)
iterator erase(iterator pos)
清楚pos指向的项目。有序容器没有返回值，无序容器返回后继迭代器（或者为end()）。
void erase（iterator first，iterator last）
iterator erase（iterator first，iterator last）
清楚范围[first，last)的全部项目。有序容器没有返回值，无序容器返回指向最后一个删除项目的后一项目的迭代器。
（1）set
关联容器，元素不允许有重复，数据被组织成一棵红黑树，查找的速度非常快，时间复杂度是O(logN)
（2）multiset
关联容器，和set一样，是允许有重复的元素，具备时间复杂度O(logN)查找功能。
（3）map
关联容器，按照{键，值}方式组成集合，按照键组织成一棵红黑树，查找的时间复杂度O(logN)，其中键不允许重复。
（4）multimap
和map一样，区别是键可以重复
4.3 容器适配器
使用中需要考虑的一些因素
1、需要添加大量元素
不适合用vector，因为vector底层是数组，当前容量不足时就要扩容，将所有旧元素全部拷贝到新内存中，开销太大
适合用list
deque是vector和list的折中，内存不够时需要申请新内存但不用拷贝旧数据
2、查找速度
对于序列容器需要分两种情况，区分依据是元素是否排序
1)对于已经排序的序列容器，使用binary_search可以获得对数时间复杂度的查找速度(O(logN));
2)而未排序的序列容器二分查找肯定是用不了，能达到的最好的时间复杂度是线性的(O(n))。
对于关联容器，存储的时候存储的是一棵红黑树，总是能达到对数时间复杂度(O(logN))的效率，因为关联容器是按照键值排好序的。
3、内存是否连续
vector、deque是连续内存的，其中vector是完全连续内存，而deque是vector和list的折中实现，是多个内存块组成的，每个块中存放的元素连续内存，而内存块又像链表一样连接起来。所以需要考虑在操作的过程中是否有在任意位置插入元素的需求，有这种需求的话尽量避免使用连续内存的vector、deque
4、元素的排序
序列容器是不会自动排序的，而关联容器通过键值对根据某种关系进行排序；所以默认情况下序列容器中的元素是无序的，而关联容器中的元素是有序的。
具体使用
在实际使用过程中，到底选择这几种容器中的哪一个，可以根据以下原则：
1、如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；
2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；
3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；
4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；
5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset
反向迭代器
反向迭代器是一种反向遍历容器的迭代器。也就是，从最后一个元素到第一个元素遍历容器。反向迭代器将自增（和自减）的含义反过来了：对于反向迭代
器，++ 运算将访问前一个元素，而 -- 运算则访问下一个元素。
回想一下，所有容器都定义了 begin 和 end 成员，分别返回指向容器首元素和尾元素下一位置的迭代器。容器还定义了 rbegin 和 rend 成员，分别返回指向容器尾元素和首元素前一位置的反向迭代器。与普通迭代器一样，反向迭代器也有常量（const）和非常量（nonconst）类型。图 11.1 使用一个假设名为 vec 的 vector 类型对象阐明了这四种迭代器之间的关系。
图 1 比较 begin/end 和 rbegin/rend 迭代器
假设有一个 vector 容器对象，存储 0-9 这 10 个以升序排列的数字：
vector vec;
for (vector::size_type i = 0; i != 10; ++i)
vec.push_back(i); // elements are 0,1,2,...9
下面的 for 循环将以逆序输出这些元素：
// reverse iterator of vector from back to front
vector::reverse_iterator r_iter;
for (r_iter = vec.rbegin(); // binds r_iter to last element
r_iter != vec.rend(); // rend refers 1 before 1st element
++r_iter) // decrements iterator one element
cout << *r_iter << endl; // prints 9,8,7,...0
虽然颠倒自增和自减这两个操作符的意义似乎容易使人迷惑，但是它让程序员可以透明地向前或向后处理容器。例如，为了以降序排列 vector，只需向 sort传递一对反向迭代器：
// sorts vec in "normal" order
sort(vec.begin(), vec.end());
// sorts in reverse: puts smallest element at the end of vec
sort(vec.rbegin(), vec.rend());
1.反向迭代器需要使用自减操作符
从一个既支持 -- 也支持 ++ 的迭代器就可以定义反向迭代器，这不用感到吃惊。毕竟，反向迭代器的目的是移动迭代器反向遍历序列。标准容器上的迭代器既支持自增运算，也支持自减运算。但是，流迭代器却不然，由于不能反向遍历流，因此流迭代器不能创建反向迭代器。
2.反向迭代器与其他迭代器之间的关系
假设有一个名为 line 的 string 对象，存储以逗号分隔的单词列表。我们希望输出 line 中的第一个单词。使用 find 可很简单地实现这个任务：
// find first element in a comma-separated list
string::iterator comma = find(line.begin(), line.end(), ',');
cout << string(line.begin(), comma) << endl;
如果在 line 中有一个逗号，则 comma 指向这个逗号；否则，comma 的值为 line.end()。在输出 string 对象中从 line.begin() 到 comma 的内容时，从头开始输出字符直到遇到逗号为止。如果该 string 对象中没有逗号，则输出整个 string 字符串。
如果要输出列表中最后一个单词，可使用反向迭代器：
// find last element in a comma-separated list
string::reverse_iterator rcomma = find(line.rbegin(), line.rend(), ',');
因为此时传递的是 rbegin() 和 rend()，这个函数调用从 line 的最后一个字符开始往回搜索。当 find 完成时，如果列表中有逗号，那么 rcomma 指向其最后一个逗号，即指向反向搜索找到的第一个逗号。如果没有逗号，则 rcomma 的值为 line.rend()。
在尝试输出所找到的单词时，有趣的事情发生了。直接尝试：
// wrong: will generate the word in reverse order
cout << string(line.rbegin(), rcomma) << endl;
会产生假的输出。例如，如果输入是：
FIRST,MIDDLE,LAST
则将输出 TSAL！
图 2 阐明了这个问题：使用反向迭代器时，以逆序从后向前处理 string对象。为了得到正确的输出，必须将反向迭代器 line.rbegin() 和 rcomma 转换为从前向后移动的普通迭代器。其实没必要转换 line.rbegin()，因为我们知道转换的结果必定是 line.end()。只需调用所有反向迭代器类型都提供的成员
函数 base 转换 rcomma 即可：
// ok: get a forward iterator and read to end of line
cout << string(rcomma.base(), line.end()) << endl;
假设还是前面给出的输入，该语句将如愿输出 LAST。
图 2. 反向迭代器与普通迭代器之间的区别
图 2 显示的对象直观地解释了普通迭代器与反向迭代器之间的关系。例如，正如 line_rbegin() 和 line.end() 一样，rcomma 和 rcomma.base() 也指向不同的元素。为了确保正向和反向处理元素的范围相同，这些区别必要的。从技术上来说，设计普通迭代器与反向迭代器之间的关系是为了适应左闭合范围
（第 9.2.1 节）这个性质的，所以，[line.rbegin(), rcomma) 和[rcomma.base(), line.end()) 标记的是 line 中的相同元素。
反向迭代器用于表示范围，而所表示的范围是不对称的，这个事实可推导出一个重要的结论：使用普通的迭代器对反向迭代器进行初始化或赋值时，所得到的迭代器并不是指向原迭代器所指向的元素。
