c++ STL （standard template libaray）标准模板库 一：标准容器 1、顺序容器vectorvector（向量容器）deque（双端链表容器）list（链表容器） 2、容器适配器
stackqueuepriority_queue（基于大根堆实现的优先级队列） 3、关联容器（重点） 无序关联容器 链式哈希表 增删查O(1)
unordered_set（无序单重集合）unordered_multiset（无序多重集合）unordered_map（无序单重映射表）unordered_multimap（无序多重映射表） 有序关联容器 红黑树 增删查O(log2n)，2是底数（树的层数，树的高度）
setmultisetmapmultimap 二：近容器（近似） 数组、string、bitset（位容器） 三、迭代器 iterator和const_iterator reverse_iterator和const_reverse_iterator 四、函数对象（类似c的函数指针） greater,less 五、泛型算法 sort、find、find_if、binary_search、for_each
底层数据结构：动态开辟的数组，每次以原来大小的2倍进行扩容；
再来复习一下基本使用：
注意：对容器进行连续插入或者删除操作（insert/erase）,一定要更新迭代器，
vectorvec; //增加 vec.push_back(20); //末尾添加元素，时间复杂度O(1) vec.insert(it,20);//it迭代器指向的位置添加一个元素20，时间复杂度O(n)，导致容器扩容 // 删除 vec.pop_back();//末尾删除元素，时间复杂度O(1) vec.erase(it);//删除it迭代器指向的元素，时间复杂度O(n) //查询 //operator[] 下标的随机访问vec[5] ,时间复杂度O(1) //iterator 迭代器进行遍历 //find,for_each //foreach ==>通过iterator来实现的
常用的方法介绍：
size()empty()reserve(20)：预留空间，只给容器底层开辟指定大小的内存空间，并不会添加新的元素resize(20)：不仅会给容器底层开辟指定大小的内存空间，还添加新的元素swap：两个容器进行元素交换
使用示例：
int main()
{
vector vec;//起初容量是0.随着插入变成1,2，4，8。。
vec.reserve(20); //给vector预留空间为20
cout<
deque
deque：双端队列容器
deque 是由一块一块的固定大小的连续空间构成（块与块之间是不连续）。一旦有必要在 deque的前端或尾端增加新的空间，便配置一块固定大小的连续空间，串接在整个deque 的头端或尾端。deque 的最大任务，便是在这些分块的固定大小连续空间上，维护其整体连续的假象（每一个第二维是连续的），并提供随机存取的接口（随机迭代器），代价则是迭代器架构较为复杂。deque 采用一块所谓的_M_map（注意，不是 STL 的 map 容器）作为主控。这里所谓_M_map 是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是 deque 的储存空间主体。底层数据结构：动态开辟的二位数组，一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组从新的第一维数组的下标的oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素的添加
deque deq;
//增加
deq.push_back(20);//末尾添加元素O（1）
deq.push_front(20);//首部添加元素O（1）
deq.insert(it,20);//在迭代器指向的位置添加元素O（n）
//删除
deq.pop_back();//从末尾删除元素O（1）
deq.pop_front();//从首部删除元素O（1）
deq.erase(it);//从it指向的位置删除元素O（n）
//查询搜索
//iterator(连续的insert和erase就一定要考虑迭代器失效的问题)
以下是deque的存储结构和其迭代器的存储结构：
#include
#include
using namespace std;
template < class _Tp>
struct _Deque_iterator //迭代器
{
typedef _Tp** _Map_pointer;
_Tp * _M_cur;
_Tp * _M_first;
_Tp * _M_last;
_Map_pointer _M_node;
};
template < class _Tp>
class _Deque_base //deque存储结构
{
typedef _Deque_iterator<_Tp> iterator;
protected:
_Tp * *_M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
};
int main()
{
std::deque iqu;
return 0;
}
常用成员函数如下：
iqu[ ]：用来访问双向队列中单个的元素。iqu.front()：返回第一个元素的引用iqu.back()：返回最后一个元素的引用iqu.push_front(x)：把元素x插入到双向队列的头部。O(1)iqu.pop_front()：弹出双向队列的第一个元素。O(1)iqu.push_back(x)：把元素x插入到双向队列的尾部。O(1)iqu.pop_back()：弹出双向队列的最后一个元素。O(1)iqu.insert(it,20),O(n)iqu.erase(it);从it指向的位置删除元素O(n)
示例：
int main()
{
std::deque iqu;
for (int i = 1; i <= 5; ++i)
{
iqu.push_back(i);
}
deque::iterator it;
for (it = iqu.begin();it != iqu.end();it++)
{
cout << *it ;
}
cout << endl;
cout << iqu.front() << endl;
cout << iqu.back() << endl;
iqu.push_front(0);
iqu.push_back(6);
for (it = iqu.begin();it != iqu.end();it++)
{
cout << *it ;
}
iqu.pop_front();
iqu.pop_back();
cout << endl;
for (it = iqu.begin();it != iqu.end();it++)
{
cout << *it;
}
return 0;
}
图示deque的简单操作：
for (int i = 1; i <= 5; ++i)
{
iqu.push_back(i);
}
iqu.pop_front();
for (int i = 6; i <= 16; ++i)
{
iqu.push_back(i);
}
list
list：链表容器
底层数据结构：双向的循环链表
list lis;
//增加
lis.push_back(20);//末尾添加元素O（1）
lis.push_front(20);//首部添加元素O（1）
lis.insert(it,20);//在迭代器指向的位置添加元素O（1），往往在进行list的insert操作时，先要进行一个query的查询操作
//对于链表来说，查询操作效率就比较低了
//删除
lis.pop_back();//从末尾删除元素O（1）
lis.pop_front();//从首部删除元素O（1）
lis.erase(it);//从it指向的位置删除元素O
//查询搜索
//iterator(连续的insert和erase就一定要考虑迭代器失效的问题)
deque、list和vector对比
vector和deque之间的区别
vector特点：动态数组，内存连续，以二倍的方式扩容，deque特点：动态开辟的二维数组空间，内存并不连续，第二维是独立new出来的，属于分段连续。固定长度，扩容的时候，第一维的数组进行二倍扩容
deque 两端都能够快速插入和删除元素 O（1），vector 只在尾端进行插入和删除 O（1）。对于内存的使用效率：vector需要的内存空间必须是连续的（低），deque可以分块进行数据存储，不需要内存空间必须是一片连续的。在中间进行insert或erase时，时间复杂度都是O（n），但是由于deque的第二维内存空间不是连续的，所以在deque中间进行元素的insert或erase操作，造成元素的移动要比vector慢（deque 的元素存取和迭代器操作会稍微慢一些，因为 deque 的内部结构会多一个间接过程。）deque 中的迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。因为 deque 使用不止一块内存（而 vector 必须使用一块连续内存）。deque 不支持对容量和内存重分配时机的控制，除了首尾两端安插、删除元素外，其他地方安插、删除元素都将导致元素的 pointer、reference、iterator 失效。不过，deque 的内存重分配机制优于 vector，因为 deque 不必在内存重分配时复制所有的元素。deque 的内存区块不再被使用时，会被释放deque和list，比vector容器多出来的增加删除函数接口：push_front和pop_front.
vector和list之间的区别
list特点：双向循环链表
（问到这里一般就是问什么时候用数组好，什么时候用链表好？）
数组：增加删除O（n），随机访问O（1），链表：增加删除一个节点O（1），但是此时还要考虑搜索的时间
容器适配器
如何理解容器适配器？
比如stack：
template>
class Stack
{
public:
void push(const 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：默认依赖deque实现，提供了push，pop，top，size，empty这几个栈常用的方法。依赖deque容器的原因：①deque的第二维是按固定大小开辟的，相比于vector，初始内存使用效率高②deque的内存是分段的，而vector需要一大片连续的空间，内存利用率高queue：默认依赖deque实现，提供了push，pop，front，back，size，empty这几个单向队列常用的方法，依赖deque容器的原因：①deque的第二维是按固定大小开辟的，相比于vector，初始内存使用效率高②deque的内存是分段的，而vector需要一大片连续的空间，内存利用率高③deque本身支持O(1)时间复杂度的头尾增加删除元素，适合实现队列结构priority_queue：默认依赖vector实现，提供了push，pop，top，size，empty这几个优先级队列常用的方法。依赖vector容器的原因，是priority_queue默认需要在一个内存连续的数组中构建一个大根堆，所以使用vector最合适（底层就是一个数组，堆结构需要按下标计算根节点和左右孩子节点在数组中的位置）。
使用示例：
#include
int main()
{
stack s1;
for(int i = 0;i<20;++i)
{
s1.push(rand()%100+1);
}
cout<
#include
int main()
{
queue que;
for(int i = 0;i<20;++i)
{
que.push(rand()%100+1);
}
cout<
#include
int main()
{
priority_queue pque;
for(int i = 0;i<20;++i)
{
pque.push(rand()%100+1);
}
cout<
无序关联容器
底层数据结构;链式哈希表 增删查O(1)
unordered_set（无序单重集合）unordered_multiset（无序多重集合）unordered_map（无序单重映射表）unordered_multimap（无序多重映射表）
需要的头文件：
#include
#include
无序容器增删查代码示例：
#include
#include
#include
using namespace std;
int main()
{
// 不允许key重复 改成unordered_multiset自行测试
unordered_set set1;
for (int i = 0; i < 100; ++i)
{
set1.insert(rand()%100+1);//不需要传入插入的位置，哈希表或者红黑树自己灰操作
}
cout << set1.size() << endl;
cout << set1.count(15) << endl;//返回key为15的元素的个数，单重集合所以一定为1，多重集合可能大于1
autoit = set。begin();
for(;it1 != est1.end();++it1)
{
cout<<*it1<<" ";
}
couit<
#include
#include
#include
using namespace std;
int main()
{
// 定义一个无序映射表// 不允许key重复
unordered_map map;
// 无序映射表三种添加[key,value]的方式，增加元素时需要你打包成一个pair类型的对象而不是两个值
//底层如下的结构：
map.insert({ 1000, "aaa" });
map.insert(make_pair(1001, "bbb"));
map[1002] = "ccc";
cout<first << " value:" << it->second << endl;
}
// 遍历map表2
for (pair &pair : map)
{
cout << "key:" << pair.first << " value:" << pair.second << endl;
}
// 查找key为1000的键值对，并且删除
map.erase(1000);
///
auto it1 = map.find(1000);
if (it1 != map.end())
{
map.erase(it1);
}
return 0;
}
因为哈希表的增删查复杂度都为O（1），在处理海量数据查重复，去重复的时候，比如下面示例：
int main()
{
const int ARR_LEN = 100000;
intarr[ARR_LEN] = {0};
for(int i - 0;imap;
for(int k:arr)
{
auto it = map.find(k);
if(it == map.end())//不存在
{
map.insert({k,1});
}
else
{
it->second++;
}
//上述代码可用map[k]++;直接代替
}
for(const pair&p:map)
{
if(p.second > 1)
{
cout<<"key:"<second > 1)
{
cout<<"key:"<first<<"count"<second;
}
}
//去重
//上面的十万个整数中，对数字进行去重后打印
unordered_set set;
for(int v:arr)
{
set.insert(v);
}
for(int v:set)
{
cout<
有序关联容器
底层数据结构：红黑树 增删查O(log2n)，2是底数（树的层数，树的高度）
setmultisetmapmultimap
需要的头文件：
#include
#include
set、multiset、map、multimap和上面的无序容器相比较，除了底层的数据结构不同，其它的操作几乎都是一样的，上面无序容器的演示代码，换成有序容器同样可以正常执行。一般对于数据有序性没有要求的话，基本上都选择无序容器来使用；如果应用场景对于数据的有序性有所要求，那么就得选择有序关联容器了。
考察有序容器的时候，经常会考察红黑树的结构定义，特征，增加删除操作具体怎么执行，这属于高级数据结构里面的知识，后续我的博客里面会更新红黑树知识的讲解。
迭代器
#if 0
int main()
{
vector vec;
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand() % 100);
}
// vector::iterator
// auto it1 = vec.begin();
// const_iterator <= iterator
vector::const_iterator it1 = vec.begin();
for (; it1 != vec.end(); ++it1)
{
cout << *it1 << " ";
}
cout << endl;
// rbegin()：返回的是最后一个元素的反向迭代器表示
// rend：返回的是首元素前驱位置的迭代器的表示
// vector::reverse_iterator
vector::const_reverse_iterator rit = vec.rbegin();
for (; rit != vec.rend(); ++rit)
{
cout << *rit << " ";
}
cout << endl;
cout << endl;
return 0;
}
函数对象
函数对象就是C语言里面的函数指针
class Sum
{
public:
int operator()(int a, int b)
{
return a + b;
}
};
int main()
{
Sum sum;
int ret = sum(10, 20);//sum.operator()(10,20)
cout << ret << endl;
return 0;
}
把有operator()小括号运算符重载函数的对象，称作函数对象或者称作仿函数。
对于下面的情境，我们只能比较大小的情况下，为了处理不同的比较方式，我们写了两个比较函数：
template
bool compare(T a, T b)
{
return a > b;
}
template
bool compare(T a, T b)
{
return a < b;
}
int main()
{
cout << compare(10, 20) << endl;
cout << compare('b', 'y') << endl;
return 0;
}
其实这样完全没有必要，其实C语言的函数指针就可以解决这个问题：
使用C的函数指针解决方案：
template
bool mygreater(T a, T b)
{
return a > b;
}
bool myless(T a, T b)
{
return a < b;
}
//compare是C++库中的库函数模板
template
bool compare(T a, T b, Compare comp)
{
return comp(a, b);
}
int main()
{
cout << compare(10, 20, mygreater) << endl;
cout << compare(10, 20, myless) << endl;
}
通过函数指针调用函数，是没有办法内联的，效率很低，因为会有函数调用开销，因此：
使用C++的函数对象解决方案：
template
class mygreater
{
public:
bool operator()(T a, T b)//二元函数对象
{
return a > b;
}
};
template
class myless
{
public:
bool operator()(T a, T b)
{
return a < b;
}
};
template
bool compare(T a, T b, Compare comp)
{
return comp(a, b);
}
int main()
{
cout << compare(10, 20, mygreater()) << endl;
cout << compare(10, 20, myless()) << endl;
}
通过函数对象调用operator()，可以省略函数的调用开销，比通过函数指针调用函数（不能够inline内联调用）效率高因为函数对象是类生成的，所以可以添加相关的成员变量，用来记录函数对象使用时更多的信息
泛型算法和绑定器
包含头文件#include
泛型算法：template + 迭代器 + 函数对象
sort, find, find_if, binary_search, for_each —— 做到所有容器通用
特点一：泛型算法的参数接收的都是迭代器特点二：泛型算法的参数还可以接收函数对象（c语言函数指针）
绑定器 + 二元函数对象 ==》 一元函数对象
bind1st:把二元函数对象的operator()(a,b)的第一个形参绑定起来bind2nd:把二元函数对象的operator()(a,b)的第二个形参绑定起来
#include
#include
#include
#include//包含了函数对象和绑定器
using namespace std;
int main()
{
int arr[] = { 23,12,5,6,547,8,7,45,7,4,523,4,3 };
vector vec(arr, arr + sizeof(arr) / sizeof(arr[0]));
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
//默认小到大的排序
sort(vec.begin(), vec.end());
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
//log(2n)有序容器中进行二分查找
if (binary_search(vec.begin(), vec.end(), 547))
{
cout << "所要查找的数547存在" << endl;
}
//O(n)
auto it = find(vec.begin(), vec.end(), 547);
if (it != vec.end())
{
cout << "所要查找的数547存在" << endl;
}
//传入函数对象greater，改变容器元素排列时的比较方式
sort(vec.begin(), vec.end(), greater());
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
//547 523 45 23 12 8 7 7 6 5 4 4 3
//把48按序插入到vector容器中,找到第一个小于48的数字
//find_if需要的是一个一元函数对象
auto it1 = find_if(vec.begin(), vec.end(),
bind1st(greater(), 48));
vec.insert(it1, 48);
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
//for_each可以遍历容器的所有元素，可以自行添加合适的
//函数对象对容器的元素进行过滤
for_each(vec.begin(), vec.end(),
[](int val)->void
{
if (val % 2 == 0)
{
cout << val << " ";
}
});
return 0;
}
