C++ Stl学习
IO
终端：istream,ostream,iostream 文件: ifstream,ostream,iofstream; string: istringstream,ostringstream,iostringstream;
容器
容器本身就是对聚合数据结构的一种封装, 数据结构的值类型有模板具体化时指定.
通用特性
迭代器
就是迭代器模式的实现:提供１种方法(这里是迭代器类),顺序访问聚合对象，不同于直接访问，他通过封装的方法访问，不会暴露聚合对象的内部表示.
从外部看，迭代器就代表了那个对象.
迭代器和智能指针有类似的地方，都是 pimple 模式的具体实现,核心是那个指针.
- 和容器的关系?
当具体化了１个 container,可以得到迭代器的具体定义类型.vector<int>::iteraotr
原理是:
class A {
public:
typedef int my_type ;
};
真正的迭代器对象，则要通过 api 返回，无法直接得到，
如auto iter = veci.begin()为何只能通过方法?
背后的实现应该是:
//vector.h
class Vector: public Iterator {
private:
data_structure some_data_elem[100];
}
//vector.cpp
//Iterator可能是抽象类，定义了纯虚方法begin.
template<typename Elem>
const Iterator & Vector::begin() {
//必然需要保存begin代表的index,0
//实际上使用指针来做的
}
private:
//维护１个元素类型的指针
Elem* ptr;
}
额外的 iterator
- insert iterator *it 即写值
front_inserter 执行了push_front
back_inserter 执行了push_back
inserter 执行了insert
make_move_iterator: 剪切
普通迭代器返回指向元素的左值
移动迭代器返回1个右值引用
- stream iterator 用来处理 io，绑定 steam. 操作容器就完成数据流 io 的进出，非常重要的思想!
假设做 web 处理,接收 json:
传输的是json序列化后的原始字符串;
str流用stringstream收;
stringstream绑定到istreamer_iterator<Json> iter;
将iter初始化到vector<Json> vecj;
vecj.push_back(*iter)就可以接收json数据
istream_iterator<int> cin_it(cin);
istream_iterator<int> cin_eof;
vector<int> veci(cin_it, cin_eof);
//压入元素,来的isteam_iteator, 等待输入,
//1个push_back通过iterator在阻塞等待
//精妙的封装
//
veci.push_back(*cin_it);
- reverse iterator
- move iterator
迭代器类别划分
这是根本的迭代器类别划分，不同类别的功能不一,上面的说的各种 iteratoer, 都属于其中某一类:
如:
vector,string,deque的迭代器都是随机访问iterator.
farward_list里是前向iterator.
list里是双向iterator.
stl find 要去用 Input Iterator:
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}
copy 需要 InputIterator 和 OutputItertor:
template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
while (first!=last) {
*result = *first;
++result; ++first;
}
return result;
}
左闭右合的设计
[begin,end)
如果一开始begin == end,容器为空;
否则如果不空，while(begin != end) { begin ++} 直到 begin==end, 迭代完成.
右开意味着 c.end()返回的 iter 是最后 1 个元素的尾后:
std::vector<int> vec1 = {1,2,3};
std::vector<int> vec2 = {4,5,6};
//insert
auto end = vec1.end();
//end指向尾后，最后1个元素应该往前挪
assert( vec1.back() == *(end-1 ) ) ;
赋值与 swap
构造, emplace,assign, swap.
assign 仅适用顺序容器.
swap 仅交换指针，参考之前的高效 swap 实现.
list<string> names;
vector<const char*> other;
name = other ;// no 不相容
name.assign(begin(other),begin(other)+5);
> = <
长度和元素相等则相等;
begin 开始的子序列，第 1 个不等的，谁大，容器就大;
顺序容器
顺序访问能力: iter++, iter–, iter[] ,不一定都支持.
vector,string 连续内存，即数组 ,缺点中间插入慢;
list: 双向链表, 怎么插都快，但是不能随机访问;
forward_list: 单向链表, 小而美
deque: 双端队列，随机访问快，两端增删也很快，中间插入慢，数据结构比较特殊,采用了`分段连续线性空间`,
https://blog.csdn.net/baidu_28312631/article/details/48000123
感觉 deque 比 vector 好？多了 push_front,数据结构本身要复杂，非线性存储，随机访问肯定不如 vector.
看问题是多大规模的: 如小规模，又需要 push_front 的 deque.
怎么确定规模？看具体问题,跑个 benchmark.
添加
insert,push_back,emplace_back,push_front.
- 结合各自的特性,有的支持，有的不支持
- 添加元素的本质是 copy,考虑性能代价的话，最好在容器里放指针.
- insert 有多个版本
push_back 版本
一般容器的添加操作都实现下面的两个版本,好处?
v.push_back(const A & a); //接受任意变量(左值，右值)，包括const的
v.push_back(A && a); //仅精确的接受非const右值,移动操作
处理更加精细.
访问
1 类是操作符: ++,– +n, -n *iter
1 类是成员函数:at, back,front,包括[],成员函数返回的是引用.
c.front() = 42; //ok
auto & v = c.back();
auto v = c.back();//这里发生了拷贝.
删除
pop_front().pop_back(),erase,clear.
farward_list 特殊
insert_after
顺序容器 insert 都是 insert_before，但是单链表无法实现，只能 insert_after.
before_begin
为何需要?因为只实现了 insert_after,那得知道 after 谁把，就是这个 before_begin.
std::forward_list<int> flst = {1,2,3,4,5,6,7};
//如何插入到头部，又只有insert_after? 用before_begin
auto pos = flst.before_begin();
flst.insert_after(pos,0);
for_each(begin(flst),end(flst),[](const int & i){cout << i << " ";});
std::out << std::endl;
容器适配器
适配顺序容器，完成更高级的数据结构功能.
stack: 栈，可接受 list deque, vector,
queue: FIFO,可接收: list deque (vector不支持push_front)
priority_queue: 最大最小堆, 可接受vector deque, (list不支持随机访问)
注意: queque stack 没有迭代器，也就是没有 begin(),end()这种遍历操作.
关联容器
关联容器是按关键字来保存和访问数据的.
不支持位置相关的操作, xx_back,xx_front，它没有头和尾的概念.
(key)有序: set, multiset, map, multimap,
(key)无序:unordered_set,unordered_multiset,unordered_map,unordered_multimap
有序是指 key 在遍历时是排序的，是因为在 key 上定义了默认的<操作符，
无序容器则是按 hash 函数在组织元素，没有明显的顺序关系.
和算法谓词不同，关联容器的的比较函数需要在模板里定义:
sort(begin(v),end(v),[](const & a, const & b){return a >= b;})
bool compare(const A & a, const A & b){
return a.val() >= b.val();
}
//用decltype声明函数类型
std::set<A, decltype(compare) *> set;
### unoredred_xxx 的桶管理
管理就是通常的 hash 数据结构，比如链表数组，不过这里的每个链表叫做桶了:
可以指定 hash 函数和==比较函数，实现自己想要的 hash 桶:
std::unordered_set<A, decltype(hash_function) *, decltype(compare_function) *>;
//如果A定义了==,可不重载==
类型别名
遍历
既然按 key 排序了，容器遍历的顺序就是按 key 来的，
auto start = begin(maps);
while( start != maps.end()) {
...
start ++;
}
算法
关联容器只能适用 read only 类的泛型算法,因为 key_type 是 const 的，不能修改内容.
常用的是 find.
也可以 copy 这种复制值出来，inserter 这种插值进去
操作
泛型算法
algorithm.h.
算法会利用容器迭代器的访问性质([],++.–等)，而不会操作(添加、删除)容器,因此算法不会改变底层容器的大小,但是可以改动值
为何不操作?因为操作没法用 algorithm 统一,需要针对不同容器用不同的 algorithm.
算法都是对某个范围内的元素操作，分 3 类:
只读，只读取容器；
改变, 改变元素到新的容器里
重排.
插入元素
一定要插入元素，怎么办?
前面说了算法只访问容器，但不操作,比如 push_back;
back_inserter 就是打破这个，它接收１个容器，返回 1 个迭代器，当对迭代器赋值时，实际就是 push_back 元素到容器里:
vector<int> veci;// 空vec
fill_n(begin(veci),10,1);//错误,veci没有元素.
fill_n(back_inserter(veci),10,1); ok
算法形参
算法谓词
什么是谓词?
2 大于 1 , 3 不是 4, 5 是 5,中间按个词，就是算法的谓词，用１个函数表示，可接收 1 个 or2 个参数，参数类型等于输入算法的 iterator 的元素类型.
部分算法支持谓词,比如 sort, xx_if
sort(begin,end,pred);
find(begin,end,val);
find_if(begin,end,pred);
谓词函数可用普通函数，可用 lamdba 表达式
//显示定义尾置指针类型，即指定lamdba的返回类型
transform(begin(v),end(v),begin(o),[](const int & i)->int {
if(i) return -i; else return i; });
//ok
transform(begin(v),end(v),begin(o),[](const int & i) {
return i>0? i:-i;});
//fail 推断lambda返回为void
transform(begin(v),end(v),begin(o),[](const int & i) {
if(i) return -i; else return i; });
特定容器算法
主要是 list,为了性能为更好,和普通算法不同，可能改变 list 容器.
allocator
已经有 new 了，还要它干什么?
new 的内存分配和构造通常在一起,new 完，对象也都构造完了.
allocator 可以做到: 分配是分配，构造是构造. 有的情况也许只要分配，不想那么快构造, 尤其是内存大，又需要很多冗余的场景，new 并不合适:
//可能５，可能995,只能先new1000,1000个默认构造或指定构造，代价都是很高的
A * aptr = new A[1000];
allocator 思路:
allocator<A> alloA;
//先分配好内存，但是不构造.
auto const p = alloA.allocate(1000);
//来，手动来
alloA.construct(p++, A("a"));
//配合move效果更佳
alloA.construct(p++, std::move(A("b"));
//调用p对象的析构.
alloA.destroy(p)
//彻底释放该内存
alloA.deallocate(p,1);
//1个太慢,从某个容器里的[b,e)拷贝过来
uninitialized_copy(b,e,p);
//在[b,e)的内存空间里，填充t对象
uninitialized_fill(b,e,t);
