C++笔记——容器、迭代器和算法

容器、迭代器和算法

容器是一种数据结构，算法通过迭代器对容器中数据进行访问，形成数据结构+算法的程序结构。

容器

通过模板可以将类型提炼出来实现泛型，用以储存不同类型对象的类成为了容器。同一容器储存同一类型的对象，当容器被销毁时，容器中的对象也会被销毁。

STL库提供了一些常用的容器类型，顺序容器：vector、list、deque；关联容器：set、map。

vector

vector是数组的一种类表示，提供了自动内存管理功能，可以动态的改变vector对象的长度，vector的长度随着元素的添加和删除而增大和缩小。vector提供了对元素的随机访问。

vector的基本函数：

1、构造

• vector():创建一个空vector

• vector(int size):创建一个vector,元素个数为size

• vector(int size,const t& x):创建一个vector，元素个数为size，值均为x

• vector(const vector&):复制构造函数

• vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

2、增加

• void push_back(const T& x):向量尾部增加一个元素X

• void push_front(const T& x):向量头部增加一个元素X

• iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x

• iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x

• iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

3、删除

• iterator erase(iterator it):删除向量中迭代器指向元素

• iterator erase(iterator first,iterator last):删除向量中[first,last)中元素

• void pop_back():删除向量中最后一个元素

• void clear():清空向量中所有元素

4、遍历

• reference at(int pos):返回pos位置元素的引用

• reference front():返回首元素的引用

• reference back():返回尾元素的引用

• iterator begin():返回向量头指针，指向第一个元素

• iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置

• reverse_iterator rbegin():反向迭代器，指向最后一个元素

• reverse_iterator rend():反向迭代器，指向第一个元素之前的位置

5、长度

• bool empty() const:判断向量是否为空，若为空，则向量中无元素

• int size() const:返回向量中元素的个数

• int capacity() const:返回当前向量所能容纳的最大元素值

• int max_size() const:返回最大可允许的vector元素数量值

6、赋值

• void swap(vector&):交换两个同类型向量的数据

• void assign(int n,const T& x):设置向量中第n个元素的值为x

• void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

vector还是可反转容器

• iterator rbegin() :返回一个指向反转序列的第一个元素的迭代器

• iterator rend() ：返回反转序列的超尾迭代器

list

list ：双向链表。除头尾元素外的元素与前后元素相连，可以双向遍历链表。在链表中插入新元素并不会移动已有的元素，而只是修改连接信息，指向某个元素的迭代器依旧指向该元素，但它的链接元素可能与以前不同。

list的基本函数：

1、构造

• list()：创建一个空列表；

• list(int n)： 创建一个列表，元素个数为n

• list(int n, const t& x): 创建一个列表，元素个数为n，元素均x

• list(int n, const list & ) : 复制构造

• list(first,last)： (begin,end):复制[begin,end)区间内的元素到list中

2、其他

增加、删除、遍历、长度等基本与vector一致，list也是可反转容器

• reverse()：list的逆置。

• void merge(lIst& l，greater<int>())：合并两个链表并使之默认升序(也可改)。调用结束后l变为空，list中元素包含原来list 和 l中的元素，并且排好序，升序。默认升序，greater<int>()可以省略，greater<int>()是可以变的，也可以不按升序排列。

• void remove(const T& val)：删除val的所有实例

• void sort()：使用<对list进行排序

• void splice(iterator pos, list& x): 将链表x的内容插到pos前面，x为空

• void unique(): 将连续的相同元素压缩为单个元素

deque

deque：双端队列，类似于vector，支持随机访问，从两端插入元素的时间固定。

基本函数

1、构造

• deque():创建一个空deque

• deque(int size):创建一个deque,元素个数为size

• deque(int size,const t& x):创建一个deque，元素个数为size，值均为x

• deque(const deque&):复制构造函数

• deque(begin,end):复制[begin,end)区间内另一个数组的元素到deque中

2、增加、删除、遍历、长度等基本与vector一致

3、可使用sort()进行排序

set

set是最简单的关联容器。

关联容器：将值与键关联在一起，依靠键来查找值。通常是使用某种树实现。

set的值类型与键相同，键是唯一的。对于set而言，值就是键。

基本函数

1、支持基本容器的操作函数

2、数学操作

• set_union(begin1, end1, begin2, end2, ostream_iterator<T, TT> out (cout, "...")) : 求集合并集

• set_intersection() ： 求集合交集

• set_difference(): 求集合的差

map

map中的键唯一，主要用于一一映射的模型，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能，在map内部所有的数据都是有序的。

基本函数

1、支持基本容器的操作函数

2、

• find(key) : 返回迭代器指向当前查找元素的位置否则返回map::end()位置

• erase(key): 用关键字刪除

• lower_bound() 返回键值>=给定元素的第一个位置

• upper_bound() 返回键值>给定元素的第一个位置

迭代器

访问容器中的元素需要通过迭代器进行，迭代器是算法与容器交流的桥梁。迭代器指向容器中元素，可以通过它来进行读写操作。指针就是一类迭代器。

迭代器按照定义方式分成以下四种。

// 正向迭代器
容器类名::iterator 迭代器名;
​
// 常量正向迭代器
容器类名::const_iterator 迭代器名;
​
// 反向迭代器
容器类名::reverse_iterator 迭代器名;
​
// 常量反向迭代器
容器类名::const_reverse_iterator 迭代器名;

用法

*迭代器名：指向的元素，非常量类型可以写入

迭代器名++ /++迭代器名：迭代器会指向容器中的前或后一个元素，前后取决于迭代器类型。

正向迭代器支持++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。

双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则--p和p--都是有定义的。--p使得 p 朝和++p相反的方向移动。

随机访问迭代器具有双向迭代器的全部功能, 还支持以下操作：

• p+=i：使得 p 往后移动 i 个元素。

• p-=i：使得 p 往前移动 i 个元素。

• p+i：返回 p 后面第 i 个元素的迭代器。

• p-i：返回 p 前面第 i 个元素的迭代器。

• p[i]：返回 p 后面第 i 个元素的引用。

• 两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。

• p2-p1: 返回值是 p2 所指向元素和 p1 所指向元素的序号之差

迭代器的函数模板（algorithm头文件）

• advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。

• distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。

• iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

算法

算法即对容器进行操作的非成员函数，算法函数使用模板来提供泛型，使用迭代器来访问容器中的数据，

STL算法库包含了非修改式序列操作、修改式序列操作和排序和相关操作的算法函数，位于头文件algorithm中，还包含通用数字运算，在头文件numeric中。