C++ STL 标准模板库

C++ STL 标准模板库

标准容器

顺序容器

vector

vector 向量容器

底层数据结构：动态开辟的数组，每次以原来空间大小的2倍进行扩容。采用allocator进行空间开辟和释放，对象创建和析构的分离。具体如C++模板学习笔记中简要实现C++中的vector。

增加：push_back、insert。

删除：pop_back、erase。

查询：operator[]、iterator、find、for-each。注意连续insert和erase中出现的迭代器失效问题。

其他：size、empty、reserve（预留空间）、resize（扩容）、swap（两个容器进行元素替换）。

reserve函数是给容器预留空间，并不会进行容器填充，容器的空间元素大小size为原来的大小。

resize函数是给容器开辟指定大小的内存空间，会对容器中的值进行添加，如果容器内部的元素是int，那么默认添加的元素为0，容器的空间元素大小size为扩容后的大小。

deque

deque 双端队列机制

#define MAP_SIZE=2; #define QUE_SIZE=4096/sizeof(T);

底层数据结构是一个动态开辟的二维数组（类似于邻接表），一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来的第二维数组，从第一维数组的下标oldsize/2开始存放，上下行都预留相同的空行，方便deque首尾元素的添加。

增加：push_back、push_front、insert

删除：pop_back、pop_front、erase

查询：iterator（连续erase和insert考虑容器失效问题）

deque底层内存是不是连续的？并不是，deque的底层是动态开辟的二维数组，第二维上是连续的，第一维上是不连续的。

list

list 链表容器

底层数据结构是双向循环链表 pre-data-next

增加：push_back、push_front、insert

删除：pop_back、pop_front、erase

查询：iterator（连续erase和insert考虑容器失效问题）

vector和deque的区别

可以从以下角度进行分析：

1. 底层数据结构。vector是连续的动态数组；deque是第二维连续的动态二维数组。
2. 前中后插入的时间复杂度。vector前中后插入的时间分别是O(n)/O(n)/O(1)，deque前中后插入的时间复杂度分别是O(1)/O(n)/O(1)。
3. 对内存的使用效率。vector必须是连续的空间，而deque只需要第二维上是连续的就行。
4. 中间进行insert或者erase，vector效率稍微高一点，因为vector底层内存是连续的，deque因为空间是不连续的，会涉及内存转化等情况。

vector和list的区别

可以从以下角度进行分析：

1. 底层数据结构。vector是连续的数组；list的双向循环链表。
2. 查找和增加、删除的时间复杂度。vector的增加和删除O(n)，查询O(n)，随机访问O(1)；链表的增加和删除O(1)（可能需要涉及搜索时间，具体情况具体分析），查询O(n)，随机访问O(n)。

容器适配器

适配器的基本概念：

1、适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现。
2、没有实现自己的迭代器。

自定义实现的stack容器：

#include<iostream>
#include<deque>
using namespace std;template<typename T,typename Container=deque<T>>
class Stack
{
public:void push(T &val) { con.push_back(val); }void pop() { con.pop_back(); }T top() const { return con.back(); }private:Container con;
};

容器适配器主要有stack、queue、priority_queue。

stack

主要方法有：push、pop、top、empty、size等

主要特点：先进后出

采用deque实现

queue

主要方法有：push、pop、front、back、empty、size等

主要特点：先进先出

采用deque实现

priority_queue

主要方法和stack的方法一致：push、pop、top、empty、size等

主要特点：和queue的不同在于，优先级高的先出队，并不是先进先出。

采用vector实现

为什么stack和queue都采用deque实现？

1. vector初始内存效率很低，默认是0-1-2-4-8- ···-2^n，而deque一开始就是4096/sizeof(T)。
2. queue需要支持头尾插入，所以采用deque效率高。
3. vector需要大量的连续的内存空间，而deque只需要分段的内存，当存在大量数据时，deque效率会高一点。

为什么priority_queue采用vector实现？

1. priority_queue的是一种大根堆的结构，一般情况下都是在一段连续的空间或者内存上进行保存。而deque在一维上不是连续的，所以就会导致很难存储大根堆树。

关联容器

常用方法：insert(val)、iterator、erase(iterator)、erase(key)。还有find的方法，查找对应的元素。

无序关联容器

哈希链式表，增删查的时间复杂度为O(1)，也需要注意迭代器失效的问题。set是无序的。

unordered_set

不会存储key值重复的元素

unordered_multiset

会存储key值重复的元素

unordered_set<int> set1;
for (int i = 0; i < 20;++i)
{set1.insert(rand() % 100 + 1);
}
cout << "size:" << set1.size() << endl;
cout << "count 15:" << set1.count(15) << endl;for (int i = 0; i < 50;i++)
{set1.insert(i);
}
auto it1 = set1.begin();
for (; it1 != set1.end();++it1)
{cout << *it1 << " ";
}
cout << endl;

unorder_map

不允许key重复，如果插入过程中会出现key重复情况，那么就会对原来key对应的value的进行替换。

unorder_multimap

允许key可以重复。

map的operator[]重载函数存在一个情况，在查询时key存在的情况下返回value，不存在的情况下会自动创建一个key和value(默认为空)。

有序关联容器

红黑树，增删查时间复杂度为O(log2n)，采用树进行存储

set

multiset

map

multimap

迭代器

迭代器iterator，一般容器内部都包含了iterator。

iterator：普通正向迭代器。一般是begin()/end()。
const_iterator：常量正向迭代器，返回值只能使用，不能修改。operator*操作符重载返回的是常量 const T& operator*。
reverse_iterator：反向迭代器。和前面两个迭代器不同的是，一般是rbegin()/rend()。
const_reverse_iterator：常量反向迭代器。

#include<iostream>
#include<vector>
using namespace std;int main()
{vector<int> v = {2, 3, 4, 6, 9, 8, 4, 2, 4, 5};auto it = v.begin();for (; it != v.end();++it){cout << *it << " ";// *it = 10;//普通正向迭代器可以修改其值}cout << endl;vector<int>::const_iterator c_it = v.begin();for (; c_it != v.end(); ++c_it){cout << *c_it << " ";// *c_it = 10;//常量正向迭代器无法修改其值}cout << endl;vector<int>::reverse_iterator r_it = v.rbegin();//获取最后一个元素的迭代器for (; r_it != v.rend();++r_it){cout << *r_it << " ";// *r_it = 10;//可以修改其值}cout << endl;vector<int>::const_reverse_iterator cr_it = v.rbegin();for (; cr_it != v.rend();++cr_it){cout << *cr_it << " ";}cout << endl;return 0;
}

函数对象

通过函数指针调用函数，是没有办法内联的，效率很低，因为有函数调用的开销

C++的函数对象，实现了operator()操作符重载

通过函数对象调用operator()，可以省略函数调用的开销，比通过函数指针调用函数（不能用内敛调用），效率更高。

函数对象是用类生成的，所以可以添加许多相关的成员变量，用来记录函数对象调用使用的更多信息。

函数调用类似于C语言的函数指针。

using关键字，对函数更改名字，类似于as方法。

#include<iostream>
using namespace std;template <typename T>
class greater2
{public:bool operator()(T&x,T&y)//二元函数对象{return x > y;}
};
template<typename T>
bool greater1(T&x,T&y)
{return x > y;
}
template<typename T,typename Compare>
bool compare(T x,T y,Compare comp)
{//Compare其实就是调用的对象或者函数实现内部功能return comp(x, y);
}
int main()
{//函数调用实现comparecout << compare<int>(10, 20, greater1<int>) << endl;//对象调用实现comparecout << compare<char>('a', 'c', greater2<char>()) << endl;return 0;
}

泛型算法

C++泛型算法都放在#include<algorithm>头文件内部。常见的泛型算法有sort、find、find_if、count、for_each、binary_search等

泛型算法的特点：

1. 泛型算法的参数接收的都是迭代器。
2. 泛型算法的参数还可以接收函数对象（C语言函数指针）。

int arr[] = {10, 20, 30, 34, 21, 12, 35, 32, 11, 22};
vector<int> vec(arr, arr + sizeof(arr) / sizeof(arr[0]));for(auto i:vec)
{cout << i << " ";
}
cout << endl;sort(vec.begin(), vec.end());for (auto i : vec)
{cout << i << " ";
}
cout << endl;if(binary_search(vec.begin(), vec.end(), 22))
{cout << "22 is existed" << endl;
}
else
{cout << "22 isn't existed" << endl;
}//传入函数对象greater，改变容器的排序方式的比较方式
sort(vec.begin(), vec.end(), greater<int>());
for (auto i : vec)
{cout << i << " ";
}
cout << endl;

绑定器 + 二元函数对象 -> 一元函数对象

绑定器存在C++的#include<functional>头文件中。

bind1st：把二元函数对象的operator()的第一个形参进行绑定起来。
bind2nd：把二元函数对象的operator()的第二个形参进行绑定起来。

//find_if是查找一个元素，需要一个一元函数对象
//查找第一个小于31的元素，并将其插入到其前面，greate a>b a=31
auto it2 = find_if(vec.begin(), vec.end(), bind1st(greater<int>(),31));
vec.insert(it2, 31);for (auto i : vec)
{cout << i << " ";
}
cout << endl;//在第一个小于19的前面插入19  a<b b=19
auto it3 = find_if(vec.begin(), vec.end(), bind2nd(less<int>(), 19));
vec.insert(it3, 19);for (auto i : vec)
{cout << i << " ";
}
cout << endl;

lambda表达式，类似于函数对象[](形参列表)->函数返回值{函数体}。