C++ Primer学习笔记-----第九章：顺序容器

访问元素

获取首尾元素：要确保容器非空
1.直接调用front和back
2.间接方法：解引用begin返回的迭代器来获得首元素的引用，递减然后解引用end返回的迭代器来获得尾元素的引用。

*****访问成员函数返回的是引用*****
在容器中访问元素的成员函数（front、back、下标、at）返回的都是引用。
如果容器是一个const对象，则返回值是const的引用。

if(!c.empty())
{
	c.front() = 42;				
	auto &v = c.back();			
	v = 1024;					引用可以改变容器中的值
	auto v2 = c.back();
	v2 = 0;						v2是一个拷贝，为改变容器中的值
}

*****下标操作和安全的随机访问*****
使用下标时，要保证下标有效，下标运算符并不检查下标是否在合法范围内。
可以使用at成员函数，如果下标越界，at会抛出一个out_of_range异常。

删除元素

删除元素的成员函数并不检查其参数。在删除元素之前，程序员必须确保它是存在的

特殊的forward_list操作

当在forward_list中添加或删除元素时，我们必须关注两个迭代器：一个指向我们要处理的元素，另一个指向其前驱。
forward_list flist={0,1,2,3,4,5};
auto prev = flist.before_begin();				表示flist的首前元素
auto curr = flist.begin();						表示flist的第一个元素
while(curr != flist.end())
{
	if(*curr % 2)
		curr = flist.erase_after(prev);			删除奇数并移动curr
	else
	{
		prev = curr;
		++curr;
	}
}
此例中，curr表示我们要处理的元素，prev表示curr的前驱。

改变容器大小

可以用resize来增大或缩小容器，array不支持resize。
如果当前大小大于所要求的大小，容器后部的元素会被删除；
如果当前大小小于新的大小，会将新元素添加到容器后部：
list ilist(1,2);
ilist.resize(10);		将8个值为0的元素添加到容器末尾
ilist.resize(20,6);		将10个值为6的元素添加到容器末尾
ilist.resize(5);		删除容器后面15个元素

容器操作可能使迭代器失效

向容器添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。
一个失效的指针、引用或迭代器不再表示任何元素。

向容器添加元素后：
1.如果容器时vector或string,且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。
  如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后的元素迭代器指针引用无效。
2.对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，
  但指向存在的元素的引用和指针不会失效。
3.对于list和forward_list，指向容器的迭代器、指针和引用仍有效。

当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用会失效。
删除一个元素后：
1.对于list和forward_list，指向容器其他位置的迭代器（包括尾后和首前迭代器）、引用和指针仍有效。
2.对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用和指针也会失效。
  如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些
  也不会受影响。
3.对于vector和string，指向被删除元素之前元素的迭代器、引用和指针仍有效，删除元素时，尾后迭代器总是会失效。

总结：添加删除对链式存储的数据结构影响更小，对顺序存储的数据结构影响较大。 

编写改变容器的循环程序

添加删除vector、string、或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步
中都更新迭代器、引用和指针。如果循环中调用的是insert或erase，那么更新迭代器很容易。这些操作都返回迭代器，可以
用来更新：
vector v = {0,1,2,3,4,5,6,7,8,9};
auto iter = v.begin();
while(iter != v.end())					更新end
{
	if(*iter % 2）						奇数
	{
		iter = v.insert(iter,*iter);	赋值当前元素，插入当前位置，返回指向新插入的元素
		iter +=2;						移动迭代器，跳过当前元素以及插入到它前面的元素
	}
	else	
		iter = v.erase(iter);			删除偶数元素，返回值指向下一个元素
}
最后容器元素值：1133557799

不要保存end返回的迭代器

当我们添加、删除vector或string的元素后，或在deque中首元素之外任何位置添加删除元素后，原来end返回的迭代器总是失效。
因此添加或删除元素的循环程序必须反复调用end,而不能在循环之前保存end返回的迭代器。
通常C++标准库的实现中end()操作都很快，部分就是因为这个原因。

vector对象是如何增长的

看书理解下就行了，总之：容器容量不够就扩大容量，重新申请一块，把原来的元素拷贝过去。
shrink_to_fit只是一个请求，标准库并不保证退还内存。

额外的string操作

const char* cp = "hello world!";	以空字符结束的数组
char noNull[] = {'H','i'};			不是以空字符‘’结束
string s1(cp);						拷贝cp中的字符直到遇到空字符,s1=="hello world!"
string s2(noNull,2);				从noNull拷贝两个字符,s2=="Hi"
string s3(noNull);					未定义：noNull不是以空字符结束
string s4(cp+6,5);					从cp[6]开始拷贝5个字符；s4=="world"
string s5(s1,6,5);					从s1[6]开始拷贝5个字符；s5=="world"
string s6(s1,6);					从s1[6]开始拷贝到末尾;s6=="world!"
string s7(s1,6,20);					从s1[6]开始拷贝,只拷贝到末尾;s7=="world!"
string s8(s1,16);					out_of_range异常

substr操作：pos超出string大小时会抛出out_of_range异常

改变string的其他方法

s.insert(s.size(),5, '!');		在末尾插入5个感叹号
s.erase(s.size()-5, 5);			删除最后5个字符
const char* cp="Stately,plump Buck";
s.assign(cp,7);					s=="Stately"
s.insert(s.size(),cp+7);		s=="Stately,plump Buck"

string s="some string",s2="some other string";
s.insert(0,s2);					在s中位置0之前插入s2的拷贝
s.insert(0,s2,0,s2.size());		在s[0]之前插入s2中s[0]开始的s2.size()个字符

s.append("abc");				在末尾插入
s.replace(1,3,"ao");			从位置1开始，删除3个字符并插入指定的字符ao

string搜索操作

每个搜索操作都返回一个string::size_type值，表示匹配发生位置的下标。如果搜素失败，则返回一个名为string::npos的
static成员。标准库将npos定义为一个const string::size_type类型，并初始化为值-1,。由于npos是一个unsigned类型，
此初始化意味着npos等于任何string最大的可能大小。

compare函数：与C标准库strcmp函数很相似

数值转换

一般情况，一个数的字符表示不同于其数值。例如：
数值15如果保存为16位的short类型，其二进制位模式为：00000000 00001111，而字符串"15"存为两个Lain-1编码的char
二进制位模式为：00110001 00110101。第一个字节表示字符‘1’，其八进制值为061，第二个字节表示‘5’，其八进制值为065

int i = 3;
string s = to_string(i);
double d = stod(s);

要转换为数值的string中第一个非空白字符必须是数值中可能出现的字符：
string s2="pi = 3.14";
double d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
调用find_first_of获取s2中第一个可能是数值的一部分的字符的位置。
string参数中第一个非空白符必须是符号（+或-）或数字，也可以以0x或0X开头来表示的十六进制数。
对那些将字符串转换为浮点值的函数，string参数也可以以小数点开头，并可以包含e或E来表示指数部分。
对于那些将字符串转换为整型值的函数，根据基数不同，string参数可以包含字母字符，对应大于数字9的数。

如果string不能转换为一个数值，函数会抛出一个invalid_argument异常。
如果转换得到的数值无法用任何类型来表示，则抛出out_of_range异常。

容器适配器

对于一个给定的适配器，可以使用哪些容器是有限制的，所有适配器都要求容器具有添加和删除元素的能力。因此，适配器不能
构造在array之上。类似的，我们也不能用forward_list来构造适配器，因为所有适配器都要求容器具有添加、删除以及访问尾
元素的能力。
stack只要求push_back、pop_back、back操作，因此可以使用除array和forward_list之外的任何容器类型。
queue适配器要求back、push_back、front和push_front,因此它可以构造与list或deque之上，不能基于vector构造。
priority_queue出来front、push_back和pop_back操作之外还要求随机访问能力，因此它可以构造于vector或deque之上
但不能基于list构造。

********************************************
书上说的这些准则是基于标准库的实现。
stack不能基于array？queue不能基于vector构造？
自己实现当然可以，只不过效率没有用其他数据结构好。
如果我们自己实现stack、queue等这些适配器，底层数据结构可以随意选择，但要考虑效率。
********************************************

栈适配器

这里书上又说queue也可以用vector实现，和前面矛盾，应该是前面的说法有问题

priority_queue允许我们为队列中的元素建立优先级。新加入的元素会排在所有优先级比它低的已有元素之前。
默认情况下，标准库在元素类型上使用<运算符来确定相对优先级。后面学习如何重载这个默认设置。

实际支持的操作有不同的地方
std::queue que;
std::queue que2;

queue支持的所有操作：没有top
que.back();
que.emplace();
que.empty();
que.front();
que.pop();
que.push(1);
que.size();
que.swap(que2);
que._Get_container();

std::priority_queue pque;
std::priority_queue pque2;

priority_queue支持的所有操作：没有front、back
pque.emplace();
pque.empty();
pque.pop();
pque.push(1);
pque.size();
pque.swap(pque2);
pque.top();