STL
standard template library 标准模板库
template: 模板
将类型抽象化 将类型和算法分离 编写更加彻底抽象的算法 \函数\类
1.函数模板 语法规则: template<typename T,…> 函数
函数模板 给类型之后实例化 模板函数 才生成对应类型的那个函数
对于某些特殊类型的，函数模板不一定适用，所以需要函数模板特化 (特殊处理) 函数模板全特化
2.类模板
template<typename T,…> class 类{
};
类模板 --> 实例化 --> 模板类
(1)类模板全特化 全特化 意味着 整个类所有的成员 和 方法都需要重新写一遍，即使一些成员和方法一模一样 template<> class 类名<特化的类型>{
}; (2)类模板成员特化 只针对某些成员方法进行特化处理 对于不需要进行特化理的不需要重新写过 template<> 返回值类型 class_name<特化的类型>::mem_name(形参列表){
} (3)类模板的偏特化 函数模板不支持偏特化 针对类型参数相同 或者 针对 类型的指针 和 数组 进行局部特化 在实例化模板时，需要避免产生歧义
数据结构与算法 用模板实现是最好的
模板的类型可以有默认类型 模板可以有非类型参数 template
模板的非类型参数在实例化必须是常量表达式
在模板定义中 typename和class 可以互换
C++提供了很多类模板 函数模板 STL
STL:
容器、迭代器、函数对象、通用算法
十大容器:
1.线性容器
vector: 向量
list: 列表
deque: 双端队列
2.容器适配器
queue: 队列
stack: 堆栈
properity_queue: 优先队列
3.关联容器
map: 映射
multi_map: 多重映射
set: 集合
multi_set: 多重集合
*所有容器的共同特点:
1.支持自动扩容
2.支持深拷贝 拷贝复制 和 拷贝赋值
3.支持 == 和 !=
如果认为两个容器相等，则容器容量相等，且相同位置的元素也相等
4.往容器中存储元素时，是存储元素的副本(拷贝构造)
5.容器如果要支持sort 自定义类型需要重载< 或者提供比较的函数对象
如果要支持find或者remove 则需要支持==比较
vector: 向量
特点:
1.内存连续
2.支持随机访问 []
3.在末尾增加元素效率高
4.支持自动扩容
方法:
1.构造函数
vector(); //容量为0 元素为0
vector( size_type num, const TYPE &val );//容量为num,元素个数num, 所有的元 素都是val
vector( const vector &from );//拷贝构造
vector( input_iterator start, input_iterator end );//[start,end) 区间的元素来构造
2.向量容量及元素个数
size() 向量在元素的个数
capacity() 向量在没有扩容之前容量的大小
empty() 向量是否为空
3.改变向量容量 和 元素个数
reserve() 设置Vector最小的元素容纳数量 一般只能扩大，不能变小
只增加内存 不增加元素个数
resize() 设置vecotr中元素的个数 可增多 可减少 (类类型成员增加时调用无参构造和拷贝构造 减少调用析构)
改变元素的个数 也可以间接改变 容量大小
可以对新增加的元素指定 默认为"零" 或者调用无参构造
clear() 清空元素 容量不变
4.支持==和!=
两个vectors被认为是相等的,如果:
1.它们具有相同的容量
2.所有相同位置的元素相等.
5.assign 对向量元素赋值 清除赋值之前的元素
6.[]和at front back 返回引用
支持下标访问
[] 可能会越界访问 并不一定会报错 把越界访问的问题隐藏了
at 如果越界 直接抛出异常 可以用try-catch捕获
front() back() 如果没有则出错
7.增加元素
push_back()
在末尾增加一个元素
8.删除元素
pop_back()
删除末尾的元素
9.插入元素
iterator
insert( iterator loc
, const TYPE
&val
);
void insert( iterator loc
, size_type num
, const TYPE
&val
);
void insert( iterator loc
, input_iterator start
, input_iterator end
);
10.迭代器
正向迭代器:begin() end()
begin() 返回的是指向第一个元素的迭代器(指针)
end() 返回最后一个元素的下一个迭代器(指针)
反向迭代器:rbegin() rend()
11.erase 删除
根据迭代器删除
iterator erase( iterator pos );
iterator erase( iterator start, iterator end );
返回最后删除元素的下一个元素迭代器
swap 交换
12.遍历
for(int i
=0;i
<v
.size();i
++){
v
[i
]
v
.at(i
)
}
for(int& i
:v
){
}
for(vecotr
<int>::iterator it
=v
.begin();it
!=v
.end();++it
){
*it
}
13.查找
全局函数 find
template<typename IT
,typename T
>
IT
find(IT begin
,IT end
,T key
){
for(IT it
=begin
;it
!=end
;it
++){
if(*it
== key
){
return it
;
}
}
return end
;
}
14.排序
全局函数 sort
template<typename IT
>
void sort(IT begin
,IT end
){
for(IT it
= begin
; it
!= end
;it
++){
for()
}
}
template<typename IT
,typename CT
>
void sort(IT begin
,IT end
,CT comp
){
}
list: 列表
全局的sort函数不支持list 因为list的内存不连续 list的迭代器不支持减法运算
特点：
1.内存不连续
2.访问时间复杂度 O(n)
3.在任何位置插入和删除效率都比较高
比vector多了 push_front() pop_front() back() front()
(1)merge 合并两个列表 把另外一个列表的元素比较插入到当前列表
如果两个列表有序 merge 有序
(2)erase 删除迭代器指定的元素 返回删除最后一个元素的下一个元素的迭代器
vector<int> v(10,10);
vecotr<int>::iteartor it = v.begin();
for(;it!=v.end();it++){//两个连续的10 ，只能删除一个
if(*it == 10){
v.erase(it);
}
}
list<int> l(10,10);
list<int>::iterator it = l.begin();
for(;it!=l.end();it++){//核心段错误
if(*it == 10){
l.erase(it);
}
}
(3) remove 删除值相等的对象 == 对象需要重载==运算符
remove_if 按指定条件删除
class Com{
private:
int no;
public:
Com(int no):no(no){}
bool operator()(const Emp& e){
//返回true删除
return e.no == no;
}
};
Com(10)
(4) reverse 逆序
(5) sort 排序
list不可以用全局的sort函数
(6) splice 把另外一个列表或者迭代器区间的元素合并到当前list
(7) unique 删除连续重复元素只保留一个 不连续的并不判断
按指定条件删除
class Com{
public:
bool operator()(const T& pre,const T& curr){
//pre是前一对象 curr是当前对象 如果返回true 则把curr对象从列表中删除
}
};
(8) list不支持随机迭代
正向迭代器 和 反向迭代器 支持 ++ -- * 不支持+ 和 -
3.deque 双端队列
和vector相似 但它允许在容器开头位置进行快速的插入和删除
比vector多了push_front() 和 pop_front()
容器适配器:
对list,vector和deque进行了封装，只提供了某些接口(函数)
容器适配器: 都可以指定底层的实现 所谓适配 就是提供满足数据结构的接口
4.stack 堆栈 先进后出
empty()
push()
pop()
size()
top()
stack<元素的类型,底层实现的类型>
5.queue 队列
底层实现不能是vector
在两端进行操作
empty()
push() 调用底层实现的push_back()
pop() 调用底层实现的pop_front() 因为vector没有pop_front 所以vector不能作为queue的底层
front()
back()
size()
6.priority_queue 没有自己的头文件 和 queue共用头文件
优先队列在push元素时，相当于插入排序一样 插入到指定位置
对数据进行排序 排在最后面的优先级更高(优先出队列)
底层实现不能是list
priority_queue<元素类型，底层实现类型，优先指定类型>
优先指定类型 默认是要怕元素类型的 <
底层实现类型 默认是deque
把学生对象放到优先队列中 要求每次取出来的都是学习成绩最好的那个学生 如果成绩一样，取学号较小
关联容器:
底层是红黑树
7.map 映射
查找效率高
map 存储的是 (KVP key-value pairs) 键值对
类似于python中的字典
key唯一
根据key来构建红黑树
pair<key_type,value_type> p;
构造pair对象:
直接调用构造函数: pair<key_type,value_type> p(key,value);
调用函数返回一个: make_pair<key_type,value_type>(key,value);
pair对象如何访问key和value
pair里面有两个成员: first second
map<key_type,value_type,comp_type>
(1)insert 把pair对象插入到map中，如果key重复 则插入失败
返回 pair<iterator,bool> 类型对象
iterator迭代器指向插入的这个元素 bool 表示插入是否成功
mapobj[key] = value; 如果key不存在则往映射中插入key-value pair
如果key存在则更新value的值
(2)find 根据key查找 不是根据value
find在比较时不是调用==进行比较
而是调用<进行比较 它怎么确定是要找的那个key呢?
node->key < key || key < node->key == false 表示 node->key == key;
8.multimap 多重映射
key值可以重复
因为multimap中可以存在多个key相同的记录,所以不能用 []
pair equal_range(const key_type &key )
返回一个记录 值等于key的区间
pair第一个迭代器为第一个键==key的记录 第二个迭代器为最后一条键==key的下一条记录
9.set集合
只有key没有value
key唯一
自定义类型存储到set中需要重载<运算符
find() 根据 < 进行比较
可以指定比较规则
set<元素类型,比较规则类型> 比较规则没有时默认按照元素类型的<
10.multiset 多重集合
元素可以重复
在map容器中的key 还是 set窗口中的元素 都不允许修改
因为在一棵有序二叉树中 不允许对节点的元素进行修改
11.bitset
二进制位集合
12.string
find
没有找到返回 string::npos
auto 万能类型
auto ret = func();
nullptr
比NULL更能代表空指针
for循环
for(auto& val:数组/容器变量){}
容器支持迭代器
array 数组
forward_list 单向链表
list: 双向链表
unordered_map
map,multimap,set,multiset 底层是红黑树实现 查找效率O(logn)
unordered_map,unordered_set 底层用哈希表实现 O(1)
哈希表最大的缺点:
rehash 哈希表在不断地插入和删除之后可以需要重新哈希
内存增长
如果数据固定:
一定是用哈希结构来存储这些数据 能够保证最快的查找效率
多线程
#include <thread>
原子数据类型
#include <atomic>
atomic_int 原子数据类型 操作原子数据类型变量时 相当于底层自动上锁
线程互斥锁
#include <mutex>
条件变量
#include <condition_variable>
用上述内容实现生产者消费者模型
智能指针
auto_ptr
shared_ptr
weak_ptr
