stl
stl简介
1. 什么是STL?
- STL(Standard Template Library)，封装基本数据结构和算法。
- STL从根本上讲是容器的集合，也是组件的集合。
- STL的组件中最主要的是容器、迭代器、算法、仿函数、适配器和内存配置器。
-
容器：用来管理某类对象的集合。主要用类模板实现。
七种基本容器包括：序列型容器（list、vector、deque);
关联型容器（set、multiset、map、multimap等等）；
容器适配器（对前面的某些容器的再包装，如stack, 队列queue等）。 - 迭代器：用来遍历容器中元素位置的数据类型。
- 算法：用来操控各种容器中的元素。如比较、交换、查找 、遍历、复制、修改、移除、反转、排序、合并等等，约70种标准算法。
-
容器：用来管理某类对象的集合。主要用类模板实现。
- STL的核心思想就是将数据和操作分离。数据由容器进行管理，操作则由算法进行，而迭代器在两者之间充当粘合剂，使任何算法都可以和任何容器交互运作。
2. STL容器
container.png
1. 序列式容器：vector，deque，list
- vector 头部与中间插入和删除效率较低，在尾部插入和删除效率高，支持随机访问。
- deque 是在头部和尾部插入和删除效率较高，支持随机访问，但效率没有 vector 高。
- list 在任意位置的插入和删除效率都较高，但不支持随机访问。
此外你也可以把 string 和 array 当做一种序列式容器
stack，queue（容器适配器），heap，priority_queue，slist
2. 四个关联式容器： set，map，multiset，multimap（底层都是红黑树）
从容器的底层存储结构和内部数据结构、随机访问元素及性能、增删元素性能进行分析。【迭代器失效、内存动态变化】
-
set<T> 集合容器: 由红黑树实现，内部元素依据其值自动排序，元素不重复，且插入和删除效率比用其他序列容器高。
-
map<T> 关联数据容器: 由红黑树实现, 可以自动建立kv的对应，kv可以是任意你需要的类型，根据 key 快速查找记录。
-
vector<T>, 向量容器: 连续存储，封装数组、常量级别随机访问
-
list<T>, 双向链表容器：双向环状链表，不支持随机访问
-
slist<T>, 单向链表,不支持随机访问
-
queue<T>, 队列容器：连续存储或者分段连续存储。实现依赖数组。常量级别随机访问
-
stack<T>, 栈容器: deque实现| 不支持随机访问|
-
deque<T>, 双端队列容器: deque实现| 不支持随机访问|
-
unorder_map
-
unorder_set
stl容器之vector
1. vector简介
- vector是一个能存放任意数据类型（类，结构，普通变量类型等）的动态数组！可通过下标索引来进行访问！
- 在数据结构中就相当于顺序储存的线性表，寻找元素非常快，但是插入元素的时间却很大（list是一个双向链表，在同一个为止插入大量的数据时速度很快，但是查找的速度就会慢很多）
与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。 - vector动态数组可以通过数组名进行直接赋值！
- vector<string> c;vector<string> b;b = c;
- 缺点：当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。（比普通的数组具有更高的时间复杂度和空间复杂度）
2. vertor常用操作
2.1、增(定义、初始化)
#include<vector> //头文件一定要有
using namespace std; //其所在的命名空间
vector<int> vec; //声明一个int型向量
vector<int> vecInit1(4,1); //vec的内容为1,1,1,1
vector<int> vecInit2{ 1, 2, 3, 4, 5, 6 }; //vec内容1,2,3,4,5,6
vector<int> vecInit3(tmp); //声明并用tmp向量初始化vec向量
int arr[5] = {1, 2, 3, 4, 5};
vector<int> vecInit4(arr, arr + 5); //将arr数组的元素用于初始化vec向量
vector<int> vecInit5(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值
2.2、删
pop_back() // 删除最后一个元素。
clear() // 清除所有元素。
empty() // 判断该数组是否为空
erase() // 删除指定位置元素。
//（入参是指针变量（迭代器），比如begain(),end()），例如vec.erase(vec.begin()+2); //删除第3个元素
2.3、改（插入）
vec.push_back(同类型量); // 作用是在vector的末尾插入新元素；
insert() // 第一个参数为迭代器，作用为在迭代器前面插入新元素；
assign(5,1) // 向vector中加入5个1，同时清除掉以前的元素。
2.4、查（遍历）
// 可以使用类似数组下标访问向量。
front() // 访问第一个元素（第一个元素的值而不是地址！begin()相反）
back() // 访问最后一个元素（最后一个元素的值而不是地址！end()相反）
size() // 数组的元素个数
2.6、翻转与排序
#include <algorithm>
reverse(vec.begin(), vec.end()) //将元素翻转，即逆序排列！
sort(vec.begin(), vec.end()); //采用的是从小到大的排序
//如果想从大到小排序，可以采用上面反转函数，也可以采用下面方法:
bool Comp(const int& a, const int& b) {
return a > b;
}
sort(vec.begin(), vec.end(), Comp);
2.7、二维向量
//C++ 构建二维动态数组
int **p;
p = new int*[10]; //注意，int*[10]表示一个有10个元素的指针数组
for (int i = 0; i < 10; ++i){
p[i] = new int[5];
}
//用vector构建二维数组
vector<vector<int>> matrix;
vector<int>a;
a.push_back(1);
a.push_back(3);
a.push_back(1);
matrix.push_back(a);
//或者用下面的方法
int i,j;
vector<vector<int>> array(5);
for (i = 0; i < array.size(); i++)
array[i].resize(3);//这里一定要使用resize其相当于每行的元素数并已经初始化过了
3. vertor注意点
迭代器中删除元素的操作时：对vector、queue等，每次erase操作，函数会删除指定迭代器位置的元素，然后将后面的元素前移一位，erase返回指向被删除元素下一元素的迭代器。（其实，我认为，返回的还是指定的迭代器，只不过它现在指向了被删除元素的下一元素，如有不对，恳请大家指正！）
对于erase操作，还有一种写法是：Vec.erase(itVec++)
不过需要注意，这种写法对vector、deque等容器无效！
上面两种写法，第一种对各种容器都有效，第二种写法只对map，list等容器有效。为了方便统一，还是建议采取第一种写法。
STL容器之set
1. set简介
set关联式容器。
set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一（集合内无重复相同的数据），而且系统能根据元素的值自动进行排序。
应该注意的是set中数元素的值不能直接被改变。
C++ STL中标准关联容器set, multiset, map, multimap内部采用的就非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。
关于set有下面几个问题
- （1）为何map和set的插入删除效率比用其他序列容器高？
不需要做内存拷贝和内存移动。说对了，确实如此。
set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。 - （2）为何每次insert之后，以前保存的iterator不会失效？
iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。 - （3）当数据元素增多时，set的插入和搜索速度变化如何？
如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。
set使用方法
begin(); // 返回set容器的第一个迭代器
end(); // 返回set容器的最后一个迭代器
clear(); // 删除set容器中的所有的元素
empty(); // 判断set容器是否为空
max_size(); // 返回set容器可能包含的元素最大个数
size(); //返回当前set容器中的元素实现个数
rbegin(); // 返回的值和end()相同
rend(); // 返回的值和rbegin()相同
2. set常用操作
2.1、增删(定义、初始化、新增数据)
- set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。
- erase(iterator) //删除定位器iterator指向的值
- erase(first,second) //删除定位器first和second之间的值
- erase(key_value) //删除键值key_value的值
#include<vector> //头文件一定要有
using namespace std; //其所在的命名空间
set<int> s; //声明一个int型集合
s.insert(1);
2.2、查 find()，返回给定值值得迭代器，如果没找到则返回end()
int arr[] = {1,2,3};
set<int> s(arr, arr+3); //用数组初始化一个int型集合
set<int>::iterator iter;
if((iter = s.find(2)) != s.end()){
cout<<*iter<<endl;
}
2.4、改
- inset(first,second);将迭代器first到second之间的元素插入到set中，返回值是void.
- insert(key_value); 将key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。
3. set注意点
- 注意begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空.
- count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。
- equal_range() ，返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对迭代器中哪个返回失败，就会等于end()的值。
pair<set<int>::const_iterator,set<int>::const_iterator> pr;
pr = s.equal_range(3);
cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl;
cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;
- lower_bound(key_value) ，返回第一个大于等于key_value的迭代器
- upper_bound(key_value)，返回最后一个大于等于key_value的迭代器
网友评论