stl
-
**序列式容器**:强调值的排序，序列式容器中的每个元素均有固定的位置。
**关联式容器**:二叉树结构，各元素之间没有严格的物理上的顺序关系
质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等 **迭代器：**容器和算法之间粘合剂
提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。 每个容器都有自己专属的迭代器
迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针 注意在容器里面存放 指针和对象的区别, 容器里面可以套容器!! string 是 stl str3.append(" love "); find查找是从左往后，rfind从右往左 str.insert() str.erase() str.substr(1, 3); **vector与普通数组区别：**
* 不同之处在于数组是静态空间，而vector可以**动态扩展** * `resize(int num);` //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
* `resize(int num, elem);` //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除 * front返回容器第一个元素 * back返回容器最后一个元素 总结：swap可以使两个容器互换，可以达到实用的收缩内存效果 `reserve(int len);`//容器预留len个元素长度，预留位置不初始化，元素不可访问。
* vector对于头部的插入删除效率低，数据量越大，效率越低 * deque相对而言，对头部的插入删除速度回比vector快 * vector访问元素时的速度会比deque快,这和两者内部实现有关push_back(elem);//在容器尾部添加一个数据push_front(elem);//在容器头部插入一个数据pop_back();//删除容器最后一个数据pop_front();//删除容器第一个数据
- 利用算法实现对deque容器进行排序
算法：
sort(iterator beg, iterator end)//对beg和end区间内元素进行排序
list的优点：
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
list的缺点：
- 链表灵活，但是空间(指针域) 和 时间（遍历）额外耗费较大
sort
bool myCompare(int val1 , int val2) { return val1 > val2; }- set/multiset属于关联式容器，底层结构是用二叉树实现。
set和multiset区别：
- set不允许容器中有重复的元素
- multiset允许容器中有重复的元素
s1.insert(40);
- 删除 --- erase
find(key);//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();count(key);//统计key的元素个数
set<int>::iterator pos = s1.find(30);
- set不可以插入重复数据，而multiset可以
- set插入数据的同时会返回插入结果，表示插入是否成功
- multiset不会检测数据，因此可以插入重复数据
-
set<int> s; pair<set<int>::iterator, bool> ret = s.insert(10); if (ret.second) { cout << "第一次插入成功!" << endl; } else { cout << "第一次插入失败!" << endl; }
pair<type, type> p ( value1, value2 );
class comparePerson { public: bool operator()(const Person& p1, const Person &p2) { //按照年龄进行排序 降序 return p1.m_Age > p2.m_Age; } };- map中所有元素都是pair
- pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
- 所有元素都会根据元素的键值自动排序
- map/multimap属于关联式容器，底层结构是用二叉树实现。
m.insert(pair<int, int>(3, 30));
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。erase(key);//删除容器中值为key的元素
find(key);//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();count(key);//统计key的元素个数
binary_search(v.begin(), v.end(),2);
count_if(iterator beg, iterator end, _Pred);int num = count_if(v.begin(), v.end(), Greater4());
sort//对容器内元素进行排序random_shuffle//洗牌 指定范围内的元素随机调整次序merge// 容器元素合并，并存储到另一容器中reverse// 反转指定范围的元素
//从大到小排序 sort(v.begin(), v.end(), greater<int>());
srand((unsigned int)time(NULL));
random_shuffle(v.begin(), v.end());
for_each(vtarget.begin(), vtarget.end(), myPrint());
class myPrint { public: void operator()(int val) { cout << val << " "; } };vector<int> vtarget; //目标容器需要提前开辟空间 vtarget.resize(v1.size() + v2.size()); //合并 需要两个有序序列 merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());
**merge合并的两个容器必须的有序序列
reverse(iterator beg, iterator end);
很多东西都要考虑的容器大小,要不要拓展v2.resize(v1.size()); copy(v1.begin(), v1.end(), v2.begin());
replace(iterator beg, iterator end, oldvalue, newvalue);// 将区间内旧元素 替换成 新元素
//将容器中的20 替换成 2000 replace(v.begin(), v.end(), 20,2000);
replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);
replace_if按条件查找，可以利用仿函数灵活筛选满足的条件- 计算区间内 容器元素累计总和
-
accumulate(iterator beg, iterator end, value);
- 向容器中填充指定的元素
-
fill(iterator beg, iterator end, value);
-
set_intersection// 求两个容器的交集 -
set_union// 求两个容器的并集 -
set_difference// 求两个容器的差集 -
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
注意:两个集合必须是有序序列