STL标准库

感谢哔哩哔哩UP“开发者LaoJ”，以下是学习记录~

一、容器

1.1、vector

底层实现是动态数组，向尾部插入数据很方便，但是向中间和头部插入数据需要移动其它元素

可以实现随机访问

如果插入时，当前vector容纳不下，会申请一个更大的空间，然后将当前vector拷贝过去，在执行插入操作

vector<T> v1;                     //默认初始化，v1不包含任何元素
vector<T> v2(v1);
vector<T> v2 = v1;
vector<T> v3(n, val);             //n个元素均为val
vector<T> v4(n);                  //包含n个重复执行了值初始化的对象
vector<T> v5{a, b, c, …};
vector<T> v5 = {a, b, c, …};/*关于vector容器的操作*/
vector<int> ivec;
//1、插入元素
ivec.push_back(10);                   //在末尾追加元素10，涉及数据拷贝
ivec.emplace_back(10);                //在末尾追加元素10，不涉及拷贝，直接在容器中创建元素
ivec.insert(ivec.begin() + 2, 10);    //在vector中的第2个位置插入10//2、删除元素
ivec.pop_back();                      //删除末尾元素
ivec.erase(ivec.begin() + 2);         //将vector中的第2个位置元素删除//3、获取迭代器
auto beg = ivec.begin();              //获取指向vector首元素的迭代器
auto end = ivec.end();                //获取指向vector尾元素的下一位置的迭代器//4、关于容器大小
ivec.size();                          //得到ivec的大小
ivec.capacity();                      //得到目前ivec的容量
ivec.resize();                        //修改ivec的大小(删/补默认值)//5、访问vector
ivec[0];                              //获取ivec的第0个元素
ivec.at(0);                           //获取ivec的第0个元素
for (auto tmp : ivec) {……}            //通过范围for来遍历ivec/*当vector使用const修饰时*迭代器会变为指向常量的迭代器*因此，不可以使用解引用迭代器来修改vector中的内容*/

1.2、deque

底层实现是一系列固定大小的数据块(分段连续)，插入操作方便，可以实现随机访问

双向开口，即两端均可插入和删除数据

#include<iostream>
#include<vector>
#include<deque>
#include <algorithm>
using namespace std;int main(void)
{//创建队列deque<int> mydeq1(5, 10);deque<int> mydeq2 = { 5, 4, 3, 2, 1 };deque<int> mydeq3(mydeq2.begin(), mydeq2.end());vector<int> vec = { 1, 2, 3, 4, 5 };deque<int> mydeq4(vec.begin(), vec.end());//插入mydeq2.push_back(6);mydeq2.emplace_back(7);mydeq2.push_front(0);mydeq2.insert(mydeq2.begin() + 2, 0);//删除mydeq2.pop_front();mydeq2.pop_back();mydeq2.erase(mydeq2.end() - 3);//排序，sort是原地排序sort(mydeq2.begin(), mydeq2.end());//成员访问cout << mydeq2.at(2) << endl;cout << mydeq2.front() << endl;cout << mydeq2.back() <<endl;//其它函数cout << mydeq2.size() << endl;mydeq2.resize(5);cout << mydeq2.size() << endl;mydeq2.clear();swap(mydeq1, mydeq2);return 0;
}

1.3、list

底层实现是双向链表，支持双向迭代，可以高效的插入和删除数据(修改指针即可)，内存不连续

但是不支持随机访问(不可以对迭代器进行加减，但是可以使用advanc移动迭代器)，访问元素需要O(n)复杂度

#include<list>
#include<vector>
#include<iostream>
using namespace std;int main(void)
{/*创建list*/list<int> mylist1 = {5, 4, 4, 4, 4, 3, 2, 1};list<int> mylist2(5, 10);vector<int> vec = { 6, 7, 8, 9, 10 };list<int> mylist3(vec.begin(), vec.end());list<int> mylist4 = mylist3;list<int> mylist5(mylist4);list<int> mylist6(move(mylist5));          //此时，mylist5为空，其中的元素被“搬运”到了mylist6list<int> mylist7, mylist8;mylist7.assign(3, 8);mylist8.assign(vec.begin(), vec.end());//获取迭代器auto beg = mylist1.begin(), end = mylist1.end();cout << "*beg:" << *beg << endl;//插入元素mylist1.push_back(6);mylist1.push_front(0);mylist1.insert(end, 9);//删除元素mylist1.pop_back();mylist1.pop_front();mylist1.erase(beg);mylist1.unique();//排序，默认升序mylist1.sort();/*实现降序排序：*myList.sort([](int a, int b) {*   return a > b;  // 降序排序*});*///splice/*advance可以移动迭代器，而next(it, 3)只是临时返回it+3处的“迭代器”，并没有修改it*/auto it = mylist1.begin();advance(it, 2);mylist2.splice(mylist2.begin(), mylist1, it, next(it, 3));//其它，splice需要再学cout << mylist1.front() << endl;cout << mylist1.back() << endl;mylist1.merge(mylist2);       //将mylist2插入到mylist1的末尾，完成操作后，mylist2为空mylist1.reverse();            //翻转mylist1return 0;
}

1.4、map

map是关联容器，即存储的是键值对，其中键是唯一的。通常情况下，按照键的升序排列

如果访问不存在的键，如：map_name[key]时，会新创建一个键值对，value的值进行默认初始化

map通常是使用红黑树进行实现的

为什么不使用平衡二叉树而是使用红黑树？

• 红黑树的平衡要求相对宽松，实现更简单
• 红黑树的调整策略使得其在插入和删除中表现得更稳定

#include<map>
#include<iostream>
using namespace std;int main(void)
{//创建/*默认情况下，map是按照key的升序进行排列的*如：map<string, int> mymap; 此时，map是按照string的升序排列的*加greater<key_type>后，将按照降序进行排序*如：map<string, int, greater<string>> mymap; 此时，map是按照string的降序排列的*/map<string, int, greater<string>> mymap = {{"zhang", 91},{"li", 78},{"wang", 85}};//插入mymap["zhangsan"] = 90;mymap["lisi"] = 98;mymap["wangwu"] = 88;mymap.insert({ "zhou", 100 });//访问auto val1 = mymap["lisi"];auto val2 = mymap["lisan"];         //并不存在key值为“lisan”的键值对，此时会新建一个键值对，其对应的value值为默认值auto val3 = mymap.at("zhou");cout << val1 << endl;//删除mymap.erase("lisan");mymap.erase("wangrensun");         //试验删除一个不存在的对象，貌似没啥影响，后续再探究一下//查找map<string, int>::iterator it = mymap.find("lisi");if (it != mymap.end())cout << "find it! it's value is:" << it->second << endl;elsecout << "find fail!" << endl;//遍历for (const auto& tmp : mymap)cout << "(" << tmp.first << "," << tmp.second << ")" << endl;for (auto beg = mymap.begin(); beg != mymap.end(); ++beg)cout << "(" << beg->first << "," << beg->second << ")" << endl;//其它mymap.clear();                     //清空mapmymap.size();                      //获得map的大小return 0;
}

1.5、set

set是一种关联容器，用于存储一组唯一的元素，并按照一定的排序规则自动排序

底层实现通常基于红黑树，插入、删除和查找操作的时间复杂度为O(lgn)

#include<iostream>
#include<set>
using namespace std;int main(void)
{/*创建*/set<int> s1;/*键值是唯一的，所以即使初始化列表中有多个1，但是set中只会有一个1*/set<int> s2 = { 3, 1, 4, 1, 5, 9 };set<int> s3(s2);/*插入*不可以对迭代器进行加减，但可以通过advance移动*好像找固定位置插入用处也不大，因为插入后会进行排序~~*/s2.insert(6);auto it = s2.begin();advance(it, 2);s2.insert(it, 8);s2.insert(s2.begin(), 0);/*删除*/s2.erase(0);s2.erase(it);/*查找*/cout << *(s2.lower_bound(5)) << endl;   //第一个大于等于5的cout << *(s2.upper_bound(7)) << endl;   //第一个大于7的auto loc = s2.find(3);if (loc != s2.end())cout << "Find it!" << endl;/*交换*/s1.swap(s2);/*遍历*/for (const auto& tmp : s1)cout << tmp << " ";cout << endl;for (auto beg = s1.begin(); beg != s1.end(); ++beg)cout << *beg << " ";cout << endl;/*其它*/cout << "s1 size:" << s1.size() << endl;s1.clear();cout << "s1 size:" << s1.size() << endl;return 0;
}

1.6、stack

stack是一种适配器，是先进后出的数据结构

不提供迭代器！

通常用deque/list作为底层实现

在弹出元素后，试图访问该元素的原始内存位置，会触发未定义行为！不要试图访问已出栈成员

#include<iostream>
#include<stack>
using namespace std;int main(void)
{/*创建*/stack<int> st;/*入栈*/st.push(1);st.push(3);st.push(5);/*访问栈顶*/cout << st.top() << endl;/*出栈*/st.pop();/*判空*/if (st.empty())cout << "stack empty!" << endl;/*获取栈大小*/cout << st.size() << endl;return 0;
}

1.7、queue

queue是一种适配器，是先进先出的数据结构

不提供迭代器！

通常用deque/list作为底层实现

此数据结构，可以用于消息队列、任务队列。deque通常用于滑动窗口

#include<iostream>
#include<queue>
using namespace std;int main(void)
{/*创建*/queue<int> qu;queue<int> qu2(qu);    //允许复制构造，不可以有初始化参数列表/*入队*/qu.push(2);qu.push(4);qu.push(6);/*出队*/qu.pop();/*访问队尾/首*/cout << qu.front() << endl;cout << qu.back() << endl;/*判空*/if (qu.empty())cout << "queue empty!" << endl;/*获取大小*/cout << qu.size() << endl;return 0;
}

1.8、unordered_map、unordered_set

这两种容器是基于哈希表的~

元素之间是无序的，键是唯一的

查找速度快，平均时间复杂度为O(1)，最坏情况下O(n)

相关操作，unordered_map与map类似，unordered_set与set类似

二、仿函数

仿函数(函数对象)是通过重载operator()的类实例来模拟函数行为的对象。这种特性使得类的对象可以像函数一样被调用

仿函数的优势

• 仿函数可以保存状态(使用类的成员保存状态，比如保存调用次数)
• 仿函数是通过对象调用的，编译器可以轻易地将其内联，减少调用开销
• 可以通过对象的属性来调整其行为

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class Compare {
public:bool operator()(int a, int b) {cnt++;         //可以记录调用次数return a < b;}
private:int cnt = 0;
};int main() {vector<int> numbers = { 10, 65, 30, 99, 23 };sort(numbers.begin(), numbers.end(), Compare());for (const auto& num : numbers) {cout << num << " ";}cout << endl;return 0;
}

三、算法

传入的操作，一般可以为仿函数、函数、lambda表达式

传入的迭代器，不一定是起始/结束迭代器

一般算法包含在头文件algorithm中

3.1、遍历算法

• for_each(iterator beg,iterator end,_func);
• transform(iterator beg1,iterator end1,iterator beg2,_func);

for_each过程中，如果需要对容器中的元素进行修改，_func可以接受引用参数

beg2必须为其对应容器的begin()

transform中的_func接受一个输入，并返回一个值，该值将被写入容器

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;/*传入给for_each*/
class myclass
{
public:void operator()(int& val) {val += 100;}
};
void add100(int& val, int b)
{val += 100;
}/*传入给transform*/
class myclass_t
{
public:int operator()(int val) {return val + 100;}
};
int func(int val)
{return val + 100;
}int main(void)
{vector<int> vec1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };vector<int> vec2 = { 11, 22, 33, 44, 55 };auto Add = bind(add100, placeholders::_1, 0);/*方法一：传入函数，当然，如果函数参数不合适，可以用函数适配器做调整*///for_each(vec1.begin(), vec1.end(), Add);/*方法二：传入lambda表达式*///for_each(vec1.begin(), vec1.end(), [](int& val) {val += 100;});/*方法三：传入仿函数*/for_each(vec1.begin(), vec1.end(), myclass());for_each(vec1.begin(), vec1.end(), [](int val) {cout << val << " ";});cout << endl;//transform(vec1.begin(), vec1.begin() + 5, vec2.begin(), func);//transform(vec1.begin(), vec1.begin() + 5, vec2.begin(), [](int val) {return val + 100;});transform(vec1.begin(), vec1.begin() + 5, vec2.begin(), myclass_t());for_each(vec2.begin(), vec2.end(), [](int val) {cout << val << " ";});cout << endl;return 0;
}

3.2、查找

• iterator find(iterator beg, iterator end, value)

找到值为value的元素则返回指向它的迭代器，否则返回结束迭代器 

• iterator find_if(iterator beg,iterator end,_Pred)；_Pred是谓词

返回满足_Pred位置对应的迭代器，否则返回结束迭代器

• iterator adjacent_find(iterator beg,iterator end);

返回相邻元素第一个位置的迭代器，否则返回结束迭代器

• bool binary_find(iterator beg,iterator end,value);

用于有序序列，找到value值则返回true，否则返回ifalse

• size_t count(iterator beg,iterator end,value);

返回value出现次数(如果是复杂类型，可能需要重载“==”运算符)

• size_t count_if(iteraotr beg,iterator end,_Pred);_Pred是统计的条件

返回满足条件的元素个数

3.3、排序

• sort(iterator beg,iterator end,_Pred);_Pred可以不填，默认为升序排序，实现降序需要传入

对容器内的元素按升序(降序)排序，时间复杂度为O(n*lgn)

• random_shuffle(iterator beg,iterator end);

将[beg, end]内的元素随机打乱，在调用前需要撒下随机种子srand((unsigned)time(NULL))，srand在头文件ctime中

• merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg);

将两个有序的容器合并到另一个目标容器中，合并后该目标容器仍然有序，_beg应为起始迭代器

• reverse(iterator beg,iterator end);

将容器内的元素进行翻转

3.4、替换

• swap(container c1,container c2)

交换两个容器内的元素，两个容器类型必须相同

• replace(iterator beg,iterator end,oldvalue,newvalue)

将[beg, end]范围内的oldvalue元素全部换成newvalue

• replace_if(iterator beg,iterator end,_Pred,newvalue)

将满足_Pred谓词的元素替换成newvalue

3.5、集合

• iterator set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

求两个容器内元素的交集，并把这个交集传给另一个容器。返回值是目标容器最后一个元素的下一个地址处的迭代器

• iterator set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

求两个容器内元素的并集，并把这个并集传给另一个容器。返回值是目标容器最后一个元素的下一个地址处的迭代器

• set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

求两个容器内元素的差集，并把这个差集传给另一个容器。返回值是目标容器最后一个元素的下一个地址处的迭代器

3.6、算术(#include<numeric>)

• size_t accumulate(iterator beg,iterator end,value)

返回容器内元素累计总和

• fill(iterator beg,iterator end,value)

向容器[beg, end]范围填充指定值

四、函数适配器

4.1、bind

可以将函数对象的一些参数绑定为特殊值，从而创建一个新的函数对象

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;bool Isthree(int a, int b) 
{return a == 3;
}int main(void)
{vector<int> vec = { 1, 2, 3, 4, 3, 4, 5, 6, 12, 3, 4, 13, 3, 20 };/*将Isthree中的第二个参数int b，绑定为0*_1表示第一个占位符，后续如果还需要站位符，则_2、_3，以此类推*/auto IsThree = bind(Isthree, placeholders::_1, 0);auto cnt = count_if(vec.begin(), vec.end(), IsThree);cout << "the num of 3 is:" << cnt << endl;return 0;
}

4.2、mem_fn

是一个用于将成员函数转换为可调用对象的适配器。它可以将成员函数包装成一个函数对象，使得成员函数可以像普通函数一样被调用。

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;struct Foo
{void show(int a, int b) {cout << a + b << endl;}
};int main(void)
{Foo foo;/*接受一个成员函数的指针*返回一个可调用对象*/auto showme = mem_fn(&Foo::show);showme(foo, 3, 4);return 0;
}

4.3、not1

not1(谓词取反)：它接受一个一元谓词，并返回一个新的谓词，该谓词对原谓词的结果取反

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;int main(void)
{vector<int> vec = { 1, 2, 3, 4, 5 };auto is_even = [](int i) {return i % 2 == 0;};/*C++标准库中的通用函数包装器，用于包装一个接受int类型参数并返回bool类型的可调用对象*用于对一元谓词取反*一元谓词：接受一个参数并返回bool的函数或函数对象*/auto is_odd = not1(function<bool(int)>(is_even));auto res = find_if(vec.begin(), vec.end(), is_odd);if (res != vec.end())cout << "First odd number is: " << *res << endl;return 0;
}