c++ primer（第五版）笔记 第九章 顺序容器（1）

// 顺序容器（sequential container）
// vector可变大小数组，快速随机访问，在尾部之外的位置插入或删除元素可能很慢
// deque双端队列，快速随机访问，在头尾快速插入或删除
// list双向链表，双向顺序访问，任何位置均可快速插入
// forward_list单向链表，单向顺序访问，任何位置均可快速插入
// array（非内置的 array）固定大小数组，快速随机访问，不能插入或删除元素
// string和 vector 相似，专用于保存字符，快速随机访问，在尾部位置插入或删除元素速度快

// 选择原则
// 除非有很好的理由选择其他容器，否则使用 ventor
// 如果元素较小，且空间开销很重要，不要使用 list ,forward_list 
// 要求快速随机访问，使用 vector ,deque
// 要求快速中间插入或删除，使用 list ,forward_list
// 要求快速头尾插入或删除，但中间不会插入或删除，使用 deque
// 要求读取输入时在中间插入，随后可随机访问
// 使用 vector 向尾端加入，使用 sort 等方法排序
// 使用 list 插入，完成后，转存至 vector

//经验：如果不确定用哪个容器，可以在程序中使用 ventor 和 list 的公共操作：使用迭代器代替下标，避免随机访问，必要时可以方便切换ventor 和 list 

//迭代器（iterator），标准库的基础
// 所有容器都支持的操作（forward_lsit 不支持 --）
// *iter
// iter->member
// ++iter
// --iter
// iter1 == iter2
// iter1 != iter2

// 仅string vector deque array 的迭代器支持的算术运算
// iter + n
// iter - n
// iter -= n
// iter += n
// iter1 - iter2
// >, >=, <, <=

// 迭代器范围（iterator range）,由一对分别指向容器内元素或尾元素的下一个位置（begin , end）表示
// 左闭合区间 [begin，end)
// 如果 begin 和 end 相等，则范围为空
// 如果 begin 和 end 不相等，则至少包含一个元素，且 begin 指向范围中的第一个元素
// 可以递增 begin 若干次，使 begin == end
//构成范围的迭代器的要求：
// 指向同一个容器，或者容器最后一个元素之后的位置，且可以通过递增 begin，到达 end

#include<vector>
#include<array>
#include<list>
#include<iostream>
using std::vector;
using std::array;
using std::list;
using std::cout;
using std::endl;

// bool find_in_vec(vector<int>::iterator first, vector<int>::iterator last, int n);
vector<int>::const_iterator find_in_vec(vector<int>::const_iterator first, vector<int>::const_iterator last, int n);

int main()
{
const vector<int> vi{1,35,7423,8,23,89,213,45,2438,2,2367,923,77,3};
vector<int> vi2{1,35,7423,8,23,89,213,45,2438,2,2367,923,77,3};
//begin 有2个版本，一个非常量一个常量
auto ivi = vi.begin();//vector<int>::const_iterator
auto ivi2 = vi.cbegin();//vector<int>::const_iterator
auto ivi3 = vi2.begin();//vector<int>::iterator
auto ivi4 = vi2.cbegin();//vector<int>::const_iterator

cout <<"find_in_vec : " <<*(find_in_vec(vi.cbegin(), vi.cend(), 923)) << endl;
cout << "===========================================================" << endl;
//直接拷贝内容，必须同容器类型和同元素类型
vector<int> vi3 = vi2;
// vector<double> vi4(vi2);错误
for(auto i:vi3)
cout << "vi3 : " << i << endl;
cout << "===========================================================" << endl;
//使用迭代器范围，不需要容器类型一致，元素类型只要能转换就可以
list<double> vi4(vi2.cbegin(),vi2.cend());
for(auto i:vi4)
cout << "vi4 : " << i << endl;
//列表初始化, 除 array 外，都隐式指明了容器大小
vector<int> vi5{4, 234, 74};
cout << "vi5.size:" << vi5.size() << endl;
cout << "===========================================================" << endl;
//顺序容器（array 除外）都有一个接受容器大小的构造函数
vector<int> vi6(10);//10个元素未定义
for(auto i:vi6)
cout << "vi6 : " << i << endl;
cout << "===========================================================" << endl;
vector<int> vi7{10};//1 个元素
for(auto i:vi7)
cout << "vi7 : " << i << endl;
cout << "===========================================================" << endl;

//创建 array 时，需要指定大小，元素执行默认初始化
array<int, 5> vi8 = {1,2}; //用0初始化第一个元素，其他进行值初始化
for(auto i:vi8)
cout << "vi8 : " << i << endl;
//内置数组不可以拷贝，array 可以但类型要一致，且容器大小也是类型的一部分
//array<int, 11> vi9 = vi8; 错误，类型不同
//vi8 = {2,4,2,6};//这种行为对于 array 是错误的，如果右侧列表元素数量大于容器大小...
for(auto i:vi8)
cout << "2vi8 : " << i << endl;
cout << "===========================================================" << endl;
vector<int> vi10;
vi10.swap(vi2);//交换2个容器的元素,比拷贝快
for(auto i:vi10)
cout << "vi10 : " << i << endl;
cout << "===========================================================" << endl;
for(auto i:vi2)
cout << "vi2 : " << i << endl;
cout << "===========================================================" << endl;
swap(vi5,vi10);//交换2个容器的元素
for(auto i:vi10)
cout << "vi10 : " << i << endl;
for(auto i:vi5)
cout << "vi5 : " << i << endl;

//assign 运算，不支持关联容器 和 array，
// c.assign(iter1,iter2);将c 的元素替换为迭代器范围中的元素
// c.assign(c2);将c 的元素替换为 c2 中元素
// c.assign(n,i);将c 的元素替换为 n 个值为 i 的元素

//只有容器内的元素定义了关系运算符时，才可以用关系运算符比较容器
// 2边必须同容器类型，同元素类型，除无序关联容器外，其他容器都支持
return 1;
}

//传入2个迭代器，查找 n ，返回bool
// bool find_in_vec(vector<int>::iterator first, vector<int>::iterator last, int n)
//返回迭代器版本
vector<int>::const_iterator find_in_vec(vector<int>::const_iterator first, vector<int>::const_iterator last, int n)
{
while(first != last)
{
if(*first == n)
// return true;
return first;
++first;
}
// return false;
return first - 1;
}