首页 > 代码库 > C++笔记(6)：标准模板库STL:容器、迭代器和算法
C++笔记(6)：标准模板库STL:容器、迭代器和算法
STL（Standard Template Library）是C++标准库的一部分。
STL的代码从广义上讲分为三类：容器、迭代器和算法。
1.容器
2.迭代器
3.算法
--------------------------------------------------------------------------------------------------------------------------
1.容器
顺序容器
容器是特定类型对象的集合。顺序容器为程序员提供控制元素存储和访问顺序的能力。元素顺序由加入容器的顺序决定。
顺序容器包括：vector、list、deque。
vector
vector将元素保存在连续的存储空间，相当于数组，因此可以通过下标随机的访问，速度很快。但是在容器的中间位置添加和删除元素会非常耗时。
因为一次插入和删除操作都需要移动插入和删除位置之后的所有元素，来保持连续存储。而且添加元素有时还需要分配额外的存储空间，拷贝数据到新空间，并释放老的空间。
在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity （）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作：
首先，vector 会申请一块更大的内存块,然后将原来的数据拷贝到新的内存块中,，接着销毁掉原内存块中的对象，最后将原来的内存空间释放掉。
如果vector 保存的数据量很大时，这样的操作一定会导致糟糕的性能所以说vector 不是在什么情况下性能都好，只有在预先知道它大小的情况下vector 的性能才是最优的。
list
是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。
容器使用链表在任何位置添加和删除都很快。但代价是不支持随机的访问。为了访问一个元素，需要遍历整个容器。不支持下标运算符。
虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector无法比拟的。
deque
是一种优化了的、对两端元素进行添加和删除操作的顺序容器。允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向d两端添加或删除元素的开销很小。
它不需要重新分配空间，所以向末端增加元素比vector 更有效。
实际上，deque 是对vector 和list 优缺点的结合，它是处于两者之间的一种容器。
vector 、list 、deque 在内存结构上的特点：
确定选择哪种顺序容器：
根据需要确定使用哪种顺序容器，下面是一些准则：
如果程序要求随机访问元素，应该使用vector或deque。
如果程序要求在容器的中间插入和删除元素，应该使用list。
如果程序需要在头尾插入和删除元素，但不会再中间位置进行插入和删除操作，应使用deque.如果元素个数不定，且只需从末尾插入，并需要随机访问，可以使用deque。
如果既需要随机访问元素，又需要在容器中间位置插入元素，此时就要取决于插入或删除元素的相对性能。可以分别对它们进行测试，可以根据测试结果决定使用何种容器
容器的方法
STL中的容器类型对外提供了统一的公共接口。这些接口的差别在于它们提供哪些操作，但是如果两个容器提供了相同的操作，则它们的接口（函数名字和参数个数）应该相同。
? 一些操作适用于所有容器类型。
? 另外一些操作则只适用于顺序或关联容器类型。
? 还有一些操作只适用于顺序或关联容器类型的一个子集。
顺序容器提供的操作
下面我们分别来介绍这些操作，如果某个操作只适用于某个容器类型，我们会专门指出。
为了定义一个容器类型的对象，必须先包含相关的头文件：
#include <vector>
#include <list>
#include <deque>
它们都定义在std名字空间中。
所有的容器都是类模板，要定义某种特殊的容器，必须在容器名后加一对尖括号，尖括号里面提供容器中存放的元素的类型：
vector<string> svec;
list<int> ilist;
deque<int> items;
所有容器类型都定义了默认构造函数，用于创建指定类型的空容器对象。默认构造函数不带参数。
容器初始化：
C<T> c; 创建一个名为c的容器，容器类型为C，如vector或list，T为容器内元素类型。适用于所有容器；
C c1(c); 创建容器c的副本，c1和c必须具有相同的容器类型和元素类型，适用于所有容器；
C c(b,e); 创建容器c,元素是迭代器b,e标示范围内的副本，适用于所有容器；
C c(n,t); 创建容器c，元素为n个值为t的值，t的类型必须是容器C的元素类型或者可以转换为该类型，只适用于顺序容器；
C c(n); 创建具有n个值初始化元素的容器c,元素类型为值n的类型，只适用于顺序容器；
顺序容器的方法
a）begin和end
返回容器的迭代器，通过迭代器我们可以访问容器内的元素。
std::vector<int>::iterator iter = c.begin();
c.begin()
c.end()
c.rbegin()
c.rend();
b）添加元素：
c.push_back();在容器尾部添加值为t的元素，返回void;
c.push_front();在容器头部添加值为t的元素，返回void，只适用于list和deque；
c.insert(p,t);在迭代器p所指向的元素前面插入值为t的元素，返回指向t的迭代器；
c.insert(p,n,t);在迭代器p所指向的元素前面插入n个值为t的元素，返回void；
c.insert(p,b,e);在迭代器p所指向的元素前面插入由迭代器b和e标记的范围内的元素，返回void；
c）获得容器大小：
c.size();返回容器内元素个数，返回类型为c::size_type;
c.max_size();返回容器内最多可容纳的元素个数，返回类型为c::size_type;
c.empty();测试容器内是否有元素；
c.resize(n);调整容器大小，使其能容纳n个元素；
c.resize(n,t);调整容器大小，使其能容纳n个元素，新添加元素以t初始化；
d）访问容器元素：
c.front();返回容器内第一个元素的引用，如果c为空，该操作未定义；
c.back();返回容器内最后一个元素的引用，如果c为空，该操作未定义；
c[n] at方法;返回下标为n的元素的引用，n越界时，该操作未定义，只用于vector和deque；
e）删除元素：
c.erase(p);删除迭代器p指向的元素，返回一个指向被删除元素后面的元素的迭代器；
c.erase(b,e);删除迭代器b和e标记范围内的所有元素，返回一个指向被删除元素段后面的元素的迭代器
c.clear();删除容器内的所有元素，返回void；
c.pop_back();删除容器的最后一个元素，返回void；
c.pop_front();删除容器的第一个元素，返回void，只适用于list和deque；
特别注意：删除元素可能会使迭代器失效，所以每次操作之后都应该及时更新迭代器；
f）赋值操作：
cl = c2;删除cl的所有元素，将c2的所有元素复制给c1，c1和c2的容器类型及元素类型必须相同；
cl.swap(c2);交换c1和c2中的所有元素，c1和c2的容器类型及元素类型必须相同；
c.assign(b,e);重新给c赋值，内容为b和e所标记范围内的元素，b和e必须不是指向c中的元素的迭代器
c.assign(n,t);将c中的元素重新设置为n个值为t的元素；
--------------------------------------------------------------------------------------------------------------------------
关联容器
map、set, multiset, multimap 是一种非线性的树结构，具体的说采用的是一种比较高效的特殊的平衡检索二叉树—— 红黑树。
1.map ，提供一种“键- 值”关系的一对一的数据存储能力。其“键”在容器中不可重复，且按一定顺序排列（其实我们可以将set 也看成是一种键- 值关系的存储，只是它只有键没有值。它是map 的一种特殊形式）。由于其是按链表的方式存储，它也继承了链表的优缺点。
2.set ，又称集合，实际上就是一组元素的集合，但其中所包含的元素的值是唯一的，且是按一定顺序排列的，集合中的每个元素被称作集合中的实例。因为其内部是通过链表的方式来组织，所以在插入的时候比vector 快，但在查找和末尾添加上被vector 慢。
3.multiset ，是多重集合，其实现方式和set 是相似的，只是它不要求集合中的元素是唯一的，也就是说集合中的同一个元素可以出现多次。
4.multimap ， 和map 的原理基本相似，它允许“键”在容器中可以不唯一。
相对于顺序容器，有以下几个主要特点：
1， 其内部实现是采用非线性的二叉树结构，具体的说是红黑树的结构原理实现的；
2， set 和map 保证了元素的唯一性，mulset 和mulmap 扩展了这一属性，可以允许元素不唯一；
3， 元素是有序的集合，默认在插入的时候按升序排列。
map
map类型可理解为关联数组，关联的本质在于元素的值与某个特定的键相关联，而与元素的位置无关。
pair类型
为了讲map，得先将pair类型：pair就是一个两个类型的组合，比如一个人的学号就可以是pair<int,string>，其中的int是学号，string是名字。
map就是一个容器，里面装的就是若干个pair。每个pair的第一个元素，称为键第二个元素，称为值。对于普通的map，每个键都对应一个值。
map类定义了3种类型，分别为key_type、mapped_type、以及vaule_type。分别表示了键的类型、值的类型，以及一个pair类型，pair的第一个元素是键，第二个元素是值。
定义pair对象
pair<T1,T2> p1;创建一个空的pair对象，两个元素类型分别是T1和T2，值初始化；
pair<T1,T2> p1(v1,v2);创建一个pair对象，具有两个元素v1和v2，类型分别是T1和T2；
make_pair(v1,v2);以v1和v2作为值创建一个pair对象，元素类型分别是v1和v2的类型；
p1.first;返回键值；
p1.second;返回值；
p1 < p2;小于运算遵循字典次序；
p1 == p2;如果两个pair对象的first成员和second成员依次相等，则两个pair对象相等；
map对象的定义：
map<k,v> m;创建一个空的map对象m，其键和值的类型分别为k，v；
map<k,v> m(m2);创建m2的副本m，m必须具有和m2相同的键类型和值类型；
map<k,v> m(b,e);创建一个map对象m，存储迭代器[b,e)标记范围内的所有元素的副本
map定义的类型：
map<k,v>::key_type;键的类型
map<k,v>::mapped_type;元素的类型
map<k,v>::value_type;
pair<const map<k,v>::key_type,map<k,v>::mapped_type>
a）添加元素：
m.insert(e);//e为map的value_type类型的值。如果键e.first不存在，则添加一个值为e.second的值，如果存在，则m不变。该操作返回一个pair类型的对象，包含一个指向新添加元素的map迭代器，以及一个bool值，表示插入是否成功；
m.insert(b,e);将迭代器b和e标示区间内的所有元素插入到m中，所插入的元素必须为m.value_typpe类型，返回void；
m.insert(iter,e);如果m中不存在键e.first，则在m中以iter为起点搜索新元素的位置并插入，返回一个指向新添加元素的迭代器。
m[1000] = "张三";在map中查找键为1000的元素，如果没有，则插入一个新的键值对，键为1000，值为张三。
b）查询元素：
m.count(k);返回m中k键出现的次数，返回值只能是0或1；
m.find(k);如果m中存在键为k的元素，则返回指向该元素的迭代器，否则，返回m.end()；
c）删除元素：
m.erase(k);删除m中键为k的元素，返回值为所删除元素的个数，只能是0或1，类型为size_type；
m.erase(p);删除m中迭代器p所指向的元素，p所指向的元素必须存在，返回void；
m.erase(b,e);删除m中由迭代器[b,e)标示范围内的元素，[b,e)必须是有效范围，返回void。
set类型
set容器单单存储键的集合。
set容器支持map的大部分的操作，以下为set容器不支持的操作：
set不支持下标操作；
没有定义mapped_type，value_type对应的是key_type，即元素的类型；
与map一样，set容器中的键也必须唯一，而且不能修改。
multimap和multiset
元素的添加删除：
insert 操作每次都会添加一个元素；
erase 带有一个键参数的该操作将删除拥有该键的所有元素，返回删除的元素个数，而带有一个或一对迭代器参数，则只删除指定的元素，返回void。
查找元素：
m.count，m.find()
m.lower_bound(k) 返回一个指向键不小于k的元素的迭代器；
m.upper_bound(k) 返回一个指向键大于k的第一个元素的迭代器；
m.equal_range(k) 返回一个pair对象，first成员等价于m.lower_bound(k);second成员等价于m.upper_bound(k)
--------------------------------------------------------------------------------------------------------------------------
容器适配器
适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现。
STL 中包含三种适配器：栈stack 、队列queue 和优先级priority_queue 。
STL 中提供的三种适配器可以由某一种顺序容器去实现。
默认下stack 和queue 基于deque 容器实现，priority_queue 则基于vector 容器实现。
在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。
栈stack 的特点是后进先出，所以它关联的基本容器可以是任意一种顺序容器，因为这些容器类型结构都可以提供栈的操作有求，它们都提供了push_back 、pop_back 和back 操作；
队列queue 的特点是先进先出，适配器要求其关联的基础容器必须提供pop_front 操作，因此其不能建立在vector 容器上；
优先级队列priority_queue 适配器要求提供随机访问功能，因此不能建立在list 容器上。
a）容器适配器通用的操作和类型：
size_type 一种类型，存储此适配器类型最大对象的长度；
value_type 元素类型；
container_type 基础容器的类型；
A a;创建一个新的容器适配器；
A a(c);创建一个新的容器适配器a,初始化为c的副本；
关系操作符：==，!=，<,<=,>,>=。
b）适配器的初始化：
stack<int> stk();
stack<int> stk2(stk);
c）覆盖基础容器类型
stack<int,vector<int> > stk;
d）栈适配器的操作：
s.empty();返回栈是否为空；
s.size();返回栈中的元素个数；
s.pop();删除栈顶元素，返回void；
s.top();返回栈顶元素，但不删除该元素；
s.push(item);在栈顶压入新元素；
e）队列和优先级队列的操作：
q.empty();返回队列是否为空；
q.size();返回队列中的元素个数；
q.pop();删除队首元素，返回void；
q.front();返回队首元素，但不删除元素，只适用于队列；
q.back();返回队尾元素，但不删除元素，只适用于队列；
q.top();返回具有最高优先级的元素，但不删除该元素，只适用于优先级队列；
q.push(item);对于queue，在队尾压入一个元素；对于priority_queue，在基于优先级的适当位置插入一个元素。
--------------------------------------------------------------------------------------------------------------------------
2.迭代器
迭代器提供对一个容器中的对象的访问方法。迭代器就如同一个指针。
事实上，C++的指针也是一种迭代器。但是迭代器不仅仅是指针。
除了使用下标来访问 vector 对象的元素外，标准库还提供了另一种访问元素的方法：使用迭代器。
迭代器是一种检查容器内元素并遍历元素的数据类型。
标准库为每一种标准容器（包括 vector）定义了一种迭代器类型。迭代器类型提供了比下标操作更通用化的方法：所有的标准库容器都定义了相应的迭代器类型，而只有少数的容器支持下标操作。因为迭代器对所有的容器都适用，现代 C++ 程序更倾向于使用迭代器而不是下标操作访问容器元素，即使对支持下标操作的 vector 类型也是这样。
iterator 类型
每个标准库容器类型都定义了一个名为 iterator 的成员,用来定义自己的迭代器。如：
vector<int>::iterator iter;
list<string>::iterator iter2;
begin 和 end 操作
每种容器都定义了一对命名为 begin 和 end 的函数，用于返回迭代器。如果容器中有元素的话，由 begin 返回的迭代器指向第一个元素：
vector<int>::iterator iter = ivec.begin();
把 iter 初始化为由名为 vector 操作返回的值。假设 vector 不空，初始化后，iter 即指该元素为 ivec[0]。
vector<int>::iterator iter2 = ivec.end()
由 end 操作返回的迭代器指向 vector 的末端元素的下一个,被称为超出末端迭代器。
迭代器的自增和解引用运算
迭代器类型定义了一些操作来获取迭代器所指向的元素，迭代器类型可使用解引用操作符（*）来访问迭代器所指向的元素：
*iter = 0;
迭代器支持的其他方法
比较：用 == 或 != 操作符来比较两个迭代器，如果两个迭代器对象指向同一个元素，则它们相等，否则就不相等。
使用迭代器遍历容器：
for (vector<string>::iterator iter = ivec.begin(); iter != ivec.end(); ++iter)
{
std::cout<<*iter<<std::endl;
}
const_iterator
每种容器类型还定义了一种名为 const_iterator 的类型，该类型只能用于读取容器内元素，但不能改变其值。
当我们对普通 iterator 类型解引用时，得到对某个元素的非 const。而如果我们对 const_iterator 类型解引用时，则可以得到一个指向 const 对象的引用，如同任何常量一样，该对象不能进行重写。
除了是从迭代器读取元素值而不是对它进行赋值之外，这个循环与前一个相似。由于这里只需要借助迭代器进行读，不需要写，这里把 iter 定义为 const_iterator 类型。当对 const_iterator 类型解引用时，返回的是一个 const 值。不允许用 const_iterator: 进行赋值
使用 const_iterator 类型时，我们可以得到一个迭代器，它自身的值可以改变，但不能用来改变其所指向的元素的值。可以对迭代器进行自增以及使用解引用操作符来读取值，但不能对该元素赋值。
区分const_iterator 与const的iterator
不要把 const_iterator 对象与 const 的 iterator 对象混淆起来。声明一个 const 迭代器时，必须初始化迭代器。一旦被初始化后，就不能改变它的值：
vector<int> nums(10);
const vector<int>::iterator cit = nums.begin();
*cit = 1;
++cit;
因为不能改写元素值。const 迭代器这种类型几乎没什么用处：一旦它被初始化后，只能用它来改写其指向的元素，但不能使它指向任何其他元素。
迭代器的算术操作
除了一次移动迭代器的一个元素的增量操作符外，vector 迭代器（list不支持随机访问所以不支持这些算数操作）也支持其他的算术操作。，包括：
iter + n
iter - n
iter1 - iter2
vector<int>::iterator mid = vi.begin() + vi.size() / 2;
迭代器失效
任何改变 vector 长度的操作都会使已存在的迭代器失效。
例如，在调用 push_back 之后，就不能再信赖指向 vector 的迭代器的值了。因为它们可能已经失效了，这时候我们需要重新为迭代器赋值。
for(iter = v.begin(); iter != v.end(); iter++)
{
if(*iter == 20)
{
v.push_back(30);
iter = v.begin();
}
}
--------------------------------------------------------------------------------------------------------------------------
3.算法
容器中提供的方法是有限的，因此STL提供了算法来对容器进行各种操作。
这些算法是独立于任何容器的，可以适用于不同类型的容器和不同类型的元素。
顺序容器只提供了很少的操作，比如增加删除、访问元素，获得第一个元素或结束为止之后的迭代器。
但是不支持比如查找特定元素、替换和删除一个特定值，排序等。
为此STL中定义了一组泛型算法。
所谓泛型就是指他们可以用于不同类型的元素和多种容器类型。他们实现了一些经典算法的公共接口，比如排序和搜索。
大部分的算法都定义在algorithm头文件中，numeric文件中定义了一组处理数值的泛型算法。
这些算法并不直接操作容器，而是通过迭代器来进行操作。
所以前面我们说迭代器是算法和容器的桥梁。
通常情况下算法会遍历迭代器范围内的元素，对每个元素进行处理。
假如有个int的vector，需要知道vector是否包含一个特定的值。这时可以调用标准库算法find。
vector<int>::iterator iter = find(vec.begin(), vec.end(), 20);
if(iter != vec.end())
{
//搜索成功！
}
传递给find的前两个参数表示元素范围的迭代器，第三个参数是用来搜索的值。
如果不存在这个值find会返回第二个迭代器。[)
可以使用find在任何容器中查找。因为指针是一种特殊的迭代器，所以也可以在find上使用指针。
int array[6]={20,339,398,0, 92,930};
int* p = find(array, array + 6, 0);
if(p != array + 6)
{
//搜索成功
}
由于find不依赖于容器，仅仅通过迭代器访问容器中的元素，所以才会如此通用。
但是算法依赖于元素提供的一些操作。比如find，他需要依赖于元素提供的==运算符，完成每个元素与指定值的比较。其他算法可能需要元素类型支持<运算符。
标准库提供了超过100个算法。这些算法有一致的结构，这可以帮助我们更容易的学习和使用这些算法。这些算法都对一个迭代器范围内的元素进行操作。这个范围是一个左闭右开的区间。
只读算法
一些算法只会读取某个范围的元素，不会改变元素。find就是这样的算法。
另一个是accumulate算法，用于对迭代器范围求和。第三个参数是和的初值。
int sum = accumulate(vec.begin(), vec.end(), 0);
第三个参数作为初始值，这里有一个假设：元素类型必须与第三个参数匹配，必须支持元素类型与第三个参数类型相加。
比如string类型支持+运算。可以使用accumulate将容器中的string元素连接起来：
string sum = accumulate(vec.begin(), vec.end(), string(""));
需要注意第三个参数不能写成“”,因为const char*上没有定义+运算符。
修改容器元素的算法
一些算法会修改容器中元素的值。但算法永远不会修改容器的长度。
比如fill算法用来填充迭代器指定的范围的值。
fill(vec.begin(), vec.end(), 0);
将所有元素置0,。
重排容器元素的算法
某些算法会改变容器中元素的顺序。比如sort，它会重新排序容器中的元素，使用<运算符来实现的。
sort接收两个迭代器，表示要排序的元素范围。
sort(vec.begin(), vec.end());
向算法传递函数
谓词
谓词是一个可调用的表达式，它返回的结果是可以被用作条件的值。标准库使用谓词分为两类：一元谓词和二元谓词。
一元谓词只接受一个参数，二元谓词接收两个参数。
接收谓词参数的算法会对容器中的元素调用谓词，元素类型必须能够转换为谓词参数的类型。
还继续看sort方法的特殊版本，该版本接收一个二元谓词，用这个谓词代替<来对元素进行比较。
下面是一个二元谓词：
bool isShorter(int a, int b)
{
return a < b;
}
sort(vec.begin(), vec.end(), isShorter);
count_if用来统计满足谓词的元素个数：
bool operate(int a)
{
return a < 60;
}
int nCount = count_if(vec.begin(), vec.end(), operate);
算法的一般形式
除了参数之外，算法还有自己的一套命名和重载规范。
一些算法使用重载形式来传递一个谓词, unique用来重新整理给定的序列，将相邻重复元素删除。：
如
unique（vec.begin(), vec.end();//使用==比较元素。
unique(vec.begin(), vec.end(), compare);//使用compare比较元素
*_if版本算法
接受一个值的算法通常有另一个不同名的版本，该版本接受一个谓词代替元素的值。
find(beg, end, val);
find_if(beg, end, 谓词)
--------------------------------------------------------------------------------------------------------------------------
C++笔记(6)：标准模板库STL:容器、迭代器和算法