C++ Primer

顺序容器

vector对象是如何增长的

这一部分我们来仔细研究一下vector在内存中的管理。
我们已经学过，vector的元素在内存中是连续存储的，这样一来，如果我在添加元素的时候，没有空间去容纳新元素应该怎么办呢？vector是这么做的：

1. 把已有元素移动到新空间中
2. 然后添加新元素
3. 释放旧存储空间 那么问题又来了，我们的新空间要分配多大呢？一般来说貌似是旧空间的两倍，反正就是会预留一些空间。

管理容量的成员函数

reserve()：只有当当前内存空间不够用的时候，reserve才会重新分配内存空间（可能比n还要大），够用的话这个函数什么也不做，这样的话，reserve永远不会减少容器所占用的内存空间。

还有一个resize函数已经用过的，它只改变容器中元素的个数，不会改变容器的容量。

capacity和size

直接看代码：

vector<int> ivec;
ivec.push_back(1);
cout << ivec.size() << ivec.capacity();

size肯定是1，capacity依赖于标准库的具体实现，肯定大于等于1

额外的string操作

除了顺序容器的共同操作之外，string还有些额外操作，在此介绍。（这一章函数特多，你完全可以在用到string的功能时再回来找）

构造string的其他方法

以上这些构造函数接受一个string或者一个const char*参数，还可以接受指定拷贝字符的数量，如果传的参数是string，还可以指定一个下标来指出从哪里开始拷贝。

接下来就是一些破规矩了：

1. 当我们从一个const char*创建string时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符停止：

   const char *cp = "Hello World!!!" //以空字符结束的数组
   string s1(cp); //拷贝cp直到遇到空字符；s1 = "Hello World!!!"
   

2. 如果我们还传递给构造函数一个计数值，数组就不必以空字符结尾：

   char a[] = {'H', 'i'}; //不是以空字符结尾
   string s2(a, 2); //虽然a不是以空字符结尾，但因为构造函数给了计数值，所以可以的
   

3. 如果我们未传递计数值且数组也未以空字符结尾，或者给定的计数值大于数组大小，则非法，构造函数行为未定义：

   string s3(a); //非法
   string s4(cp, 100); //非法
   

substr

取子字符串：

string s("hello world");
string s2 = s.substr(0, 5) //s2 = "hello"
string s3 = s.substr(6) //s2 = "world"
string s4 = s.substr(6, 11) //s2 = "word"，从6开始，最多拷贝到末尾
string s2 = s.substr(12) //抛出一个out_of_range异常

改变string的其他杂七杂八

string s1("hello world");
string s2("C++ Primer");
s1.insert(s1.size(), 5, '!'); //s1 = "hello world!!!!!"
s1.eraser(s1.szie()-5, 5); //s1 = "hello world"

s2.append(" 4th Ed."); //s2 = "C++ Primer 4th Ed."
s2.replace(11, 5, "Fifth"); //s2 = "C++ Primer Fifth Ed."

改变string可能还有一些要注意的地方，这个要靠你实际用的时候注意了。

string搜索操作

一共6个操作，都很好好记，一般来说满足了一般的需求： 找到就返回指定字符的下标，找不到就返回npos（string::npos）
首先说明一下传入参数args的含义，args必须是一下形式之一： c, pos | 从s中位置pos开始查找字符c，pos默认为0 ---|--- s2, pos |从s中位置pos开始查找字符串s2，pos默认为0 cp, pos | 从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串，pos默认为0 cp, pos, n | 从s中位置pos开始查找指针cp指向的数组前n个字符，pos和n无默认值

上面的参数看着很烦，其实就是从指定位置来构造一个字符串，好在原字符串中查找。好的，现在来说搜索函数

我们来举例子用用看：

string river = "西调西"; 
auto first = river.find("西"); //返回0
auto last = river.rfind("西"); //返回2

compare函数

compare有很多重载的版本，好好看下面的代码就知道了：

string s1("hello");
string s2("hi");

s1.compare(s2); //hello跟hi比，都是按字典序
s1.compare(0, 2, s2); //he和hi比
s1.compare(0, 3, s2, 0, 1); //hel和h比

char *p = "bye";
s1.compare(p); //hello和bye比
s1.compare(0, 2, cp); //he和bye
s1.compare(0, 2, cp, 2); //he和by

数值转换

C++11新标准引入了一些函数，可以实现数值数据与string之间的来回转换：

int i = 42;
string s = to_string(i); //s = "42"
double d = stod(s); //string->double

string s2 = "pi = 3.14哈哈哈";
//第一个非空白字符必须是数值中可能出现的字符
d = stod(s2.substr(s2.find_first_of("+-.0123456789"))); //d = 3.14

其他还有转换为long,unsigned long等不再一一介绍。

容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack栈、queue队列、priority_queue优先队列。

到底适配器啥意思呢？适配器就是一种机制，能让某种事物的行为看起来像另一种事物。一个容器适配器接受一种已有的容器类型，使其行为看起来像另一种不同的类型。

我觉得大概意思是这样，栈、队列、优先队列这些数据结构都是大家比较常用的，C++也不好意思不支持，但是又偷懒不想去实现它们，于是把原来顺序容器的那些再通过适配器转换成这三个数据结构。

默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的：

stack<int> stk(deq); //从deq拷贝元素到stk

适配器要求能在头尾添加元素和返回头尾元素，所以不支持这些的顺序容器就没有适配器了，比如array，人家不能改大小不能增加删除啊。

栈适配器

C++自己定义了头文件stack（虽然我觉得可能是引入了顺序容器比如deque），栈是先入后出的：

stack<int> in;
for(size_t i = 0; x != 10; ++i)
{
    in.push(i); //压入元素，还有pop删除栈顶元素，top返回栈顶等
}

再提一句：虽然stack是基于deque实现的，但不能使用push_back，必须用自己的push，这样看起来就像两个不同的事物，不就满足了适配器的意思吗

队列适配器

队列先进先出，操作自己用的时候找，无非就是返回头尾，添加删除代替等。

priority_queue允许我们为队列的元素简历优先级，举个例子，我们的优先队列装的元素是一个类person，它有属性姓名，年龄，学历等，我们就可以以其中任意一个属性为优先级来排序，只要重载<运算符就好，怎么重载<呢？也很简单，不过要之后再学。