容器
只有一些小tips，主要内容去看《cppp》
迭代器辅助函数
#include<iterator> std::advance (it,5); //将迭代器it向右偏移5位； 这个函数没有返回值，是对it的操作 //demo list<int> li = {1,2,3,5,6,7,8}; auto it = li.begin(); //拷贝指向第一个位置的迭代器 advance(it,3); //因为我们要插到第四个位置前面（1+3=4，迭代器移动到第4位），所以迭代器右移3位 li.insert(it,4); for(auto item : li) cout<<item<<" "; cout<<endl; //输出：1 2 3 4 5 6 7 8顺序迭代器也可以通过
iter += n来移动n位容器元素都是拷贝
要想改变原对象，可以设置容器元素为原对象的引用，或指向原对象的指针
顺序容器访问
at(index)(安全)和[index]操作只适用于string,vector,deque,array（顺序数据结构），链表这种非顺序数据结构(list,forward_list)不适用c.back()，c.front()注意：访问成员函数返回的是引用
int &res = vec[2];也可以接收为非引用，但这实际发生了拷贝赋值
int res = vec[2]，即将返回引用所引用的对象的值来初始化新对象res。要想用返回的变量来改变原对象值，就要使用引用地址失效问题
增加/删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用、指针失效。
增加/删除vector或string中某位置元素，则增加点/删除点之后位置的迭代器、引用、和指针都会失效。
原因：对于顺序容器(vector,string,array,deque)，每个元素是连续存储的，增加点/删除点之后的元素会发生群体平移，元素地址全变了，所以导致与地址有关的都失效了！
对于链表容器（list、forward_list），元素是非连续存储的而是通过指针串起来，所以不会发生平移，地址不变，所以增删后不会失效！
解决办法：保证每次增删操作后的迭代器、引用、和指针都是最新的，不会失效。
对于删除，可以利用
erase操作的返回值来更新迭代器，删除操作的返回值是删除后指向下一个元素的迭代器；对于增加，增加了几个元素，当前迭代器就右移几位对于顺序容器的增删，不要保存其
end()迭代器，必定无用，每一次循环都必须获取新的end()迭代器例子（在循环中增删顺序容器，如果是偶数则删除，如果是奇数则复制）：
//在循环中增删顺序容器 vector<int> vt = {0,1,2,3,4,5}; auto iter = vt.begin(); while (iter != vt.end()) //【注意这里：每一次循环都会求一次vt.end()，也就是每次循环都更新了尾后迭代器！】 { if (*iter%2==0) iter = vt.erase(iter); //删除元素，返回下一个元素迭代器，更新 else { iter = vt.insert(iter,*iter); //插入之后返回的是插入点迭代器 iter += 2; //更新迭代器，跳过被复制元素与复制元素到下一个遍历点 } } for (auto item : vt) cout<<item<<" "; cout<<endl; //输出：1 1 3 3 5 5这个例子的模式非常常用
P.S.删除元素的成员函数并不检查其参数，在删除元素之前，程序员需要确保它们是存在的。
vector和string不支持头部增删操作，但可以用insert/emplace、erase实现
forward_list是手写单链表，非常简单，所以它的所有操作和其它容器都不一样，见《cppp》P313
主要原因是因为单链表没有指向前驱节点的指针，所以删除/添加某元素要从它的前驱着手，没有
insert、erase操作，只有insert_after()，emplace_after()、erase_after()等使用
before_begin()返回首元素前一个位置的迭代器对forward_list进行中间插入/删除操作，就需要建立两个迭代器
begin()，before_begin()，也就是单链表常用的双指针办法对于增删：
insert、erase以及一系列衍生操作，返回值是 增加后指向第一个新增元素的迭代器/删除后指向下一个元素的迭代器vector默认以初始化元素大小来分配空间，然后采用不够则翻倍的空间增长方式。
对于vector和string这种元素在空间上连续存储的结构，如果没有空间容纳新元素，则会发生①重新在内存中找到一块大小翻倍的连续内存空间 ②将原数据拷贝到新内存空间中 ③释放原内存空间
所以消耗大
size_type
size_type是容器里的概念
对string或vector调用
.size()返回的不是一个表元素个数的整数，而是size_type类型使用int变量的问题是：有些机器上的int变量的表示范围太小，甚至无法存储实际并不长的string对象。如在有16位int型的机器上，int类型变量最大只能表示32767个字符的string对象。而能容纳一个文件内容的string对象轻易就能超过这个数字，因此，为了避免溢出，保存一个string对象的size的最安全的方法就是使用标准库类型
string::size_type().其实size_t和size_type类似，size_t 类型定义在cstddef头文件中,该文件是C标准库的头文件stddef.h的C++版本
但一般都可以隐式转化成int类型
注意，关联容器分为有序和无序
和其它语言的关联容器区别非常大，注意细节
map，set，multimap，multiset都是有序容器，由关联数组构成。有序容器通过比较运算符（对关键字）来组织元素。所以如果一个类型定义了行为正常的<运算符，即可作为关键字类型（可以手动传入函数指针类型作为比较操作类型给关联容器，注意其参数必须是const，见书）所以有序容器中的元素，默认是按关键字顺序排列的所以要将对象作为有序容器的关键字需要在定义处传入比较操作类型。详见书
unordered_map，unordered_set，unordered_multimap，unordered_multiset都是无序容器，使用哈希函数组织（使用hash和==运算符来组织元素）。无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。所以要将对象作为无序容器的关键字需要重写hasher()、eqOp()函数。详见书
对于有序和无序关联容器，都可以使用范围for遍历，有序关联容器遍历关联数组，无序容器遍历桶，无序容器可以使用哈希管理操作，也提供了与有序容器相同的操作
c++关联容器没有contains函数，但是关联容器提供了
find函数（不是算法里的find）。find函数返回指向目标的迭代器，如果找不到则指向末尾，判断其是否等于尾后迭代器(end())来判断是否包含某元素注意：使用一个不存在的关键字作为下标，会自动插入一个新元素，其关键字为给定关键字，其值为0。所以不能用下标访问法来判断关键字是否存在，如果不存在，这个操作本身就会插入新元素（但这种特性也有使用场景；也因此下标操作只能操作非const map）但使用
at运算访问一个不存在的元素会抛出out_of_range异常map中实际取出来的元素类型是pair类型，对于取出来的pair对象，要调用pair.first，pair.second来获取key和value。（first和second是pair对象中默认public的成员）。所以如果使用迭代器遍历map，如果迭代器是it，那么访问其key，value应该写：it->first，it->second。当然如果是直接用for范围遍历就w.first，w.second访问成员即可（w可以是遍历map获得的pair引用或拷贝）下标运算/
at运算提供了方便的key，value访问，可以跳过操作pair对象，来插入，修改map中的pair对象的key value值。
如果不用下标运算，如使用insert等函数操作容器，就要考虑插入pair对象了。（不过insert可以隐式创建pair对象，比如map.insert({word,1})）。关于insert，对于map和set，总会返回一个pair，first是指向新插入pair的迭代器，second是插入是否成功的bool（注意，这里就成了pair里有另一个pair的迭代器的形式），对于multi的，则总会插入成功，所以直接返回新pair的迭代器
下标运算的关键字必须是标准库基本类型，我自己定义的对象以及
<操作不行map的关键字，set的迭代器都是const的，不能修改
multimap、multiset即同一个关键字有多个value元素，比如想建立作者到他所写书籍的题目的映射，每个作者可能有多个条目。在可重复关联容器中，同一个关键字的元素会相邻存储。（所以可以获得第一个迭代器，利用find()找到第一个元素，利用count()计算共多少个，再迭代器右移来遍历）erase()删除关键字关联的一个元素，返回剩余的value数量（对于不重复，就是0；对于重复，就是还剩多少了）。对于一个erase有三种重载形式，参数可以是关键字，返回剩余元素数量；两个迭代器，删除中间所有元素；可以是一个迭代器erase(p)，那么就返回返回下一个元素的迭代器（这在遍历map的时候删除元素会用到，返回迭代器可以用于更新迭代器！原迭代器失效了！）insert则不能边遍历边插入（map会保证key有序，所以就不能了）。总结一下常用操作：
下标操作/at操作、insert()、erase()、find()、count()以下写的demo
#include <iostream> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <string> #include <utility> using namespace std; class Student { public: string name; int score; Student(string name,int score) { this->name = name; this->score = score; } }; int score_compare(const Student &s1,const Student &s2) { return s1.score > s2.score; } template <typename T> void print_key(map<T,string> m) { cout<<"key seq : "; for (auto &p : m) cout<<p.first<<" "; cout<<endl; } template <typename T> void print_value(map<T,string> m) { cout<<"value seq : "; for (auto i = m.begin(); i != m.end(); ++i) cout<<i->second<<" "; cout<<endl; } void print_student_key(multimap<Student,string,decltype(score_compare)*> m) { cout<<"key seq : "; for (auto &p : m) cout<<p.first.name<<" "; cout<<endl; } void print_student_value(multimap<Student,string,decltype(score_compare)* >m) { cout<<"value seq : "; for (auto i = m.begin(); i != m.end(); ++i) cout<<i->second<<" "; cout<<endl; } int main() { map<int,string> m; m[4] = "a"; m.insert({1,"b"}); m.insert(make_pair(3,"c")); print_key(m); print_value(m); cout<<m.find(3)->second<<endl; if (m.find(9)!=m.end()) cout<<"found 9"<<endl; else cout<<"could not find 9"<<endl; Student a("Bob",40),b("Ford",99),c("Jean",70); multimap<Student,string,decltype(score_compare)*> student_performance_map(score_compare); //以下访问方法错误 //student_performance_map[a] = "poor"; //student_performance_map[b] = "well done!"; //student_performance_map[c] = "not bad"; cout<<"All performance of all students : "; student_performance_map.insert({a,"poor"}); student_performance_map.insert({b,"well done!"}); student_performance_map.insert({c,"not bad"}); student_performance_map.insert({a,"go on"}); student_performance_map.insert({a,"impressed!"}); print_student_key(student_performance_map); cout<<"All performance of Bob : "; auto iter = student_performance_map.find(a); auto nums = student_performance_map.count(a); while(nums) { cout<<iter->second<<" "; if(iter->second=="poor") iter = student_performance_map.erase(iter); //delete pool performace else ++iter; --nums; } cout<<endl; cout<<"after delete pool performance : "; print_student_key(student_performance_map); }指向容器的指针使用下标运算要对前面所有东西打括号—易错
shared_ptr<vector<int>> np(new vector<int>({1,2,3,4})); (*np)[0] = -1; //容器内容变成 -1 2 3 4 *np[0] = -1; //错误！！！ //若类obj里面右指向容器的指针p (*(obj.p))[0] = -1; //容器内容变成 -1 2 3 4-
vector并没有*vector返回首元素的特性！vector变量并不是指向vector内首元素的指针
泛型算法
- 算法、谓词
- lambda
- 迭代器
笔记都在书上
以下为写的demo
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool is_bigger(const int &a, const int &b)
{
return a > b;
}
void print(vector<int> &vec, const string &str)
{
cout<<str<<" : ";
for (auto &item : vec)
cout<<item<<" ";
cout<<endl;
}
int main()
{
vector<int> vec = {3,2,1,4,5};
sort(vec.begin(),vec.end(),[](const int &a, const int &b){return a>b;});
//sort(vec.begin(),vec.end(),is_bigger);
print(vec,"reverse");
sort(vec.begin(),vec.end());
print(vec,"sort");
cout<<"find_if : ";
int th = 1;
auto it0 = find_if(vec.begin(),vec.end(),[th](const int &a){return a>th;});
for (auto i = it0; i != vec.end(); ++i)
cout<<*i<<" ";
cout<<endl;
cout<<"new vec size : "<<(vec.end()-it0)<<endl;
vector<int> vec2(vec.end()-it0);
//vec2.resize(vec.end()-it0);
copy(it0,vec.end(),vec2.begin());
print(vec2,"copy");
replace(vec.begin(),vec.end(),2,9);
print(vec,"replace");
//for_each(vec.begin)
cout<<"for_each : ";
for_each(vec.begin(),vec.end(),[](int &a){if(a>3) cout<<a<<" ";});
cout<<endl;
//insert intr
vector<int> vec3(vec.size());
auto fi = inserter(vec3,vec3.begin());
copy(vec.begin(),vec.end(),fi);
print(vec3,"inster copy");
}
/*
reverse : 5 4 3 2 1
sort : 1 2 3 4 5
find_if : 2 3 4 5
new vec size : 4
copy : 2 3 4 5
replace : 1 9 3 4 5
for_each : 9 4 5
front_inster copy : 1 9 3 4 5 0 0 0 0 0
*/lambda表达式可以用auto类型表示类型（因为不同参数的lambda表达式类型是不同的，很复杂）
于是就可以写为auto lm = lambda表达式
