c++primer笔记九、顺序容器

一个容器就是一些特定类型对象的集合。
顺序容器为程序员提供了控制元素存储和访问顺序的能力。
顺序和元素加入时的位置有关，和本身的值无关。

9.1顺序容器概述

主要类型有

vector              //向量，可变大小的数组,访问快速，插入删除慢
deque               //双端队列，支持快速随机访问，头尾插入删除很快
list                //双向链表，只支持双向顺序访问，插入删除很快
forward_list        //单向链表，只支持单向顺序访问。插入删除很快
array               //固定大小数组，支持快速随机访问，不能
string              //字符串，类似vector

选择使用哪种容器

一些基本原则

1：如果有很好的理由选择其他容器，否则就用vector
2：有很多小的元素，且空间的额外开销很重要，则不用list
3：要求随机访问元素用vector和deque
4：要求中间插入用list
5：头尾插入用deque
6：只有读取时要在中间位置插入，读取完要随机访问，可以先list然后拷贝到vector。
如果程序既要随机访问，又要在中间插入，就应该比较性能

9.2容器库概览

容器的操作有一些层次：

1、有些操作所有容器都提供
2、有一些操作仅仅针对顺序容器，关联容器或无序容器
3、有些操作适用于小部分容器

每个容器都定义在一个头文件中，与类型名相同。

对容器可以保存的元素类型的限制

可以保存几乎任何类型，除了某些容器对元素类型有自己的特殊要求。
例如：如果类没有默认构造函数，则必须初始化才行。

//noDefault时一个没有默认构造函数的类型
vector<noDefault> v1(10, init);
vector<noDefault> v2(10);       //错误，必须提供初始化器，因为noDefault没有构造函数

迭代器

标准容器类型上的所有迭代器都允许我们访问容器中的元素。
迭代器都通过解引用来实现。
操作见表3.6
一个例外forward_list不支持递减(--)

迭代器范围

迭代器由一对迭代器表示，分别指向容器中的元素或者是尾元素之后的位置。
通常称为begin和end，或者first和last。
第二个end指向尾元素之后的位置，是个空的
成为左闭合区间[begin, end)

使用左闭合范围蕴含的编程假定

假设begin和end构成一个迭代器范围，则：
1：如果begin和end相等，范围为空
2：如果不能，则至少包含一个，且begin指向范围内的第一个元素
3：可以对begin递增若干次，直到begin == end

while (begin != end)
{
    *begin = val;
    ++begin;
}

容器类型成员

每个容器都定义了多个类型，使用这些类型必须显式地使用其类名

list<string> :: iterator iter;
vector<int> :: difference_type;

begin和end成员

有4种版本，r开头的是反向迭代器，c开头的是const迭代器

list<string> a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin();
auto it2 = a.rbegin();
auto it3 = a.cbegin();
auto it4 = a.crbegin();

不过以c开头的函数都是重载过的,实际上有两个begin的成员，一个是const成员，返回const_iterator，另一个返回iterator。当对非常量调用是，得到的是iterator版本，只有对一个const对象调用时，才会得到一个const版本。
可以将普通的iterator转换为对应的const_iterator，反之不行。
c开头时新加的，用以支持auto使用。过去只能显式声明使用哪种迭代器。

list<string>::iterator it5 = a.begin();
list<string>::const_iterator it6 = a.begin();
//等同于
auto it7 = a.begin();
auto it9 = a.cbegin();

当不需要写访问时，就应该用cbegin和cend

容器定义和初始化

每个容器都有默认的构造函数，除了array，其他的默认构造函数都会创建一个指定的空容器，且都可以接受大小和初始值的参数。
更多见表9.3

将一个容器初始化为另一个容器的拷贝

将一个容器创建为另一个容器的拷贝有两种方法：可以之间拷贝，或者拷贝由一个迭代器对指定的元素范围。
第一种要求两种容器类型及元素必须匹配，第二种不要求容器类型相同，且元素类型也可以不同，只要能够进行元素转换即可。

list<string> authors = {"Milton", "Shakespeare", "Austen"}
vector<const char*> articles = {"a", "an", "the"}

list<string> list2(authors);    //正确
deque<string> authList(authors);    //错误
vector<string> word(articles);      //错误
forward_list<string> words(articles.begin(), articles.end());   //正确

列表初始化

显式地指定了容器每个元素地值，并且隐含了指定容器地大小

vector<const char*> articles = {"a", "an", "the"}

与顺序容器大小相关地构造函数

vector<int> iver(10, -1);       //10个int，每个都初始化-1
deque<string> sver(10);         //10个string，每个都是空

只要顺序容器才支持接受大小参数，关联容器不支持。

标准库array具有固定大小

定义array时必须指定大小

array<int, 10>
array<string, 10>

为了使用array，必须同时指定元素类型和大小

array<int, 10> :: size_tpye i;

列表初始化时值地数目必须小于或等于array大小，剩下的都会进行值初始化。

array<int, 10> ia = {42}        //ia[0]为42，剩下为0

内置数组不能拷贝，array可以拷贝，只需要数组类型和大小匹配

赋值和swap

赋值运算符将左边容器的全部元素替换为右边元素的拷贝

c1 = c2;
c1 = {a, b, c};

与内置数组不同，array允许赋值，且等号两侧必须具有相同类型

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0};    //初始全为0
a1 = a2;        //替换a1的元素
a2 = {0};       //错误

容器赋值运算有:

c1 = c2;
c1 = {a, b, c};
swap(c1, c2);
c1.swap(c2);        //更快
seq.assign(b,e);    seq元素替换为迭代器b和e表示的元素范围
seq.assign(il);     seq替换为初始化列表il中的元素
seq.assign(n,t)     seq中的元素替换为n个值为t的元素

使用assign（仅顺序容器）

用来元素的替换

list<string> names;
vector<const char*> oldstyle;
names = oldstyle;       //错误，类型不匹配
names.assign(oldstyle.cbegin(), oldstyle.cend());   正确

assign中的迭代器不能是调用assign的容器
assign第二个版本接受整型和一个元素值，全部替换

list<string> slist1(1);     //1个元素，为空
slist1.assign(10, "Hiya~"); //10个元素，都为"Hiya~"

//一种等价
slist1.clear();
slist1.insert(slist1.begin(), 10, "Hiya~");

使用swap

交换两个相同类型的容器
元素本身没有交换，交换的是两个容器的内部数据结构（没有进行拷贝删除插入操作，复杂度为常数时间）
元素不会移动意味着除了string外，指向容器的迭代器，引用和指针都不会失效，仍然指向swap操作之前的那些元素。
但是swap后这些元素属于不同容器了。
对string调用swap会使迭代器，引用和指针失效。
对array进行swap，会真正交换元素。
非成员版本的swap在泛型编程中很重要，所以最好使用非成员版本的swap。

容器大小操作

size:返回大小
empty:如果为空则返回true
max_size:返回一个大于或等于该类型容器所能容纳的最大元素的值

有一个例外forward_list不支持size

关系运算符

每种容器都支持相等运算符(==和!=);除了无需关联容器外都支持关系运算符(>、>=、<、<=)
关系运算符左右必须是相同类型的容器，且必须保存相同类型的元素。
比较实际是逐对比较，和string类似：

1:如果两个容器大小相等且所以元素两两相等，则相等
2:如果大小不同，但小容器的元素都等于大容器的元素，则小容器小于大容器
3:如果两个容器都不是另一个的前缀子序列，则取决于第一个不同元素的比较结果

容器的关系运算符使用元素的关系运算符比较

如果元素无法使用关系运算符，就不能比较两个容器

9.3顺序容器操作

向顺序容器添加元素

array大小不能改变，因此不支持任何操作。
forward_list有自己专业版本的insert和emplace
forward_list不支持push_back和emplace_back
vector和string不支持push_front和emplace_fornt

c.push_back(t);     //尾部添加一个值为t或者由args创建的元素
c.emplace_back(args);

c.push_front(t);    //头部添加
c.emplace_front(args);

c.insert(p, t);      //在迭代器p指向的元素前创建t或args创建的元素，返回新添加元素的迭代器
c.emplace(p, args);

c.insert(p, n, t);  //在迭代器p前插入n个t，返回添加的第一个元素迭代器。如果n为0，返回p
c.insert(p, b, e);  //将迭代器b和e指定范围内的元素插入到p指向的元素前。
//b和e不能是c中的元素，返回新添加的第一个元素迭代器
c.insert(p, il);    在p之前插入一个列表

向vector、string和deque插入元素会使迭代器、引用和指针失效

使用push_back

除了array和forward_list,都支持push_back。

string word;
while (cin >> word)
    container.push_back(word);

在container尾部创建了一个新元素，size也增大了1，该元素是word的拷贝。
string也可以push_back向末尾添加字符

word.push_bacl('s')     //等价word += 's'

容器的元素是拷贝

push_front

list、forward_list、deque支持头部插入

list<int> ilist;
ilist.push_front(1);

和vector一样，deque在首尾以外插入元素很耗时。

在容器特定位置添加元素

使用insert进行一般的添加，每个insert都接受一个迭代器作为第一个参数。
在迭代器指向的前一个位置插入

svec.insert(svce.begin(), "Hello!");

插入范围内元素

可以将十个元素插入到末尾

svec.insert(svec.end(), 10, "Anna");

也可以接受一个迭代器或初始化列表的insert版本将给的范围的元素插入到指定位置前。

vector<string> v = {"qyasu", "simba", "frollo", "scar"};
//将V的最后2个元素添加到slist的开始位置
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "end"});

新版本的insert操作会返回指向第一个新加入元素的迭代器。

使用insert的返回值

list<string> lst;
auto iter = lst.begin();
//每次iter都指向第一个，等价于push_front
while (cin >> word)
    iter = lst.insert(iter, word);

使用emplace

emplace_操作构造元素而不是拷贝，而push和insert是把对象拷贝到容器中。
当调用emplace成员时，是把参数传递给元素类型的构造函数。
例如：

//假定c保存Sales_data元素：
c.emplace_back("987-085945", 25, 15.99) //临时构造一个Sales_data，直接传给c
c.push_back(Sales_data("987-085945", 25, 15.99))//临时构造一个Sales_data，拷贝给c

emplace_back构造完直接传递，而push_back则构造完再拷贝

访问元素

有几种方法：

1:at和下标操作适用于string, vector, deque和array
2:back不适合forward_list
c.back()        //尾元素引用
c.front()       //首元素引用
c[n]            //下标n的引用，若n>size,则函数行为未定义
c.at(n)         //返回下标n的引用，若越界，则抛出out_of_range异常

访问成员函数返回的是引用

如果容器是const对象，则返回值是const引用，否则就是普通引用

if (!c.empty()){
    c.front() = 42;
    auto &v = c.back();
    v = 1024;               //改变c中元素
    auto v2 = c.back();
    v2 = 0;                 //未改变
}

下标操作和安全的随机访问

给的下标必须在范围内，下标运算符不会检查是否合法。
如果希望下标是合法的，可以用at函数

vector<string> svec;
cout << svec[0];        //运行错误
cout << svec.at(0);     //抛出异常

删除元素

array不支持删除
forward_list有特殊的erase;
forward_list不支持pop_back;vector和string不支持pop_front

c.pop_back()        //删除尾元素，返回void
c.pop_front()       //删除首元素
c.earse(p)          //删除迭代器p所指元素
c.erase(b, e)       //删除迭代器b和e范围内的元素
c.clear()           //删除全部元素

pop_front和pop_back

分别删除首元素和尾元素。
vector和 string不支持pop_front。
forward_list不支持pop_back

//操作返回void，如果需要值需要先取出
process(ilist.front());
ilist.pop_front();

容器内部删除一个元素

erase从容器中指定位置删除元素。
可以删除迭代器指定的一个或一个范围的元素，返回为删除后的第一个元素的位置迭代器
例：删除list中的奇数

list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while (it != lst.begin())
    if (*it % 2)
        it = lst.erase(it);
    else
        ++it;

删除多个元素

elem1 = slist.erase(elem1, elem2);  //删除elem1到elem2之前的元素
slist.clear();      //删除所有元素
slist.erase(slist.begin(), slist.end()) //等价

特殊的forward_list

链表的操作不太一样，删除当前值会改变上一个值的指向，因此没有insert,emplace和erase,而是用其他操作

lst.before_begin()      //返回首元素之前不存在的元素的迭代器，这个不能解引用。相当于哨兵节点
lst.cbefore_begin()
lst.insert_after(p,t)       //在p之后的位置插入元素，n是数量
lst.insert_after(p,n,t)
lst.insert_after(p,b,e)         //b和e是表示范围的得带起
lst.insert_after(p,il)      //il是花括号
emplace_after(p,args)       //构造版本
lst.erase_after(p)          //删除p所指元素
lst.erase_after(b,e)        //删除b之后直到e的元素。

可以forward_list写删除奇数

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin();
auto curr = flst.begin();
while (curr != flst.end()){
    if (*curr % 2)
        curr = flst.erase_fater(prev);
    else{
        prev = curr;
        ++curr;
    }
}

改变容器大小

resize不适用于array
c.resize(n)     //c的大小改为n
c.resize(n,t)   //大小改为n，新增的元素都初始化为t

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

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

当删除元素后：
1：当前元素迭代器指针引用都失效
2：对于list和forward_list，其他位置迭代器引用指针仍有效
3：deque，首尾以外都失效。如果是删除尾元素，则尾后迭代器失效，其它不影响。如果是首元素，其他不影响。
4：对于vector和string,指向被删除元素之前的都有效，后面的迭代器失效。

编写改变容器的循环程序

如果循环调用的是insert或erase,可以容易地更新迭代器。

//删除偶数，复制奇数
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin();
while (iter != vi.end()) {
    if (*iter % 2){
        iter = vi.insert(iter, *iter);
        iter +=2;
    }else
    {
        iter = vi.erase(iter);
    }
}

不要保存end返回的迭代器

当我们添加或删除vector或string元素，或者在deque首元素之外的地方添加删除元素后，end总会失效。
必须在每次操作后重新调用end(),而不能在循环开始前保存它返回的迭代器

auto end = v.end(); //保存尾迭代器是一个坏想法
//安全的方法：每次循环步添加/删除元素后都重新计算end
while(begin != v.end()){
    ++begin;    //向前移动begin,因为想在此元素之后插入元素
    begin = v.insert(begin, 42)
    ++begin;    //向前移动begin, 跳过刚刚加入的元素
}

9.4 vector对象是如何增长的

为了避免每次添加元素vector就执行内存分配和释放，采用了可以减少容器空间重新分配次数的策略。

管理容量的成员函数

vector提供了一些成员函数允许我们与它的实现中内存分配部分互动。

shrink_to_fit只适用于vector、string和deque
capacity和reserve只适用于vector和string

c.shrink_to_fit()   //将capacity()减少为与size()相同大小
c.capacity()        //不重新分配内存，c可以保存多少元素
c.reserve(n)        //分配至少能容纳n个元素的内存空间

只有当需要的内存空间超过当前容量，reserve才会改变。如果需求大于当前容量，reserve至少分配与需求一样大的内存空间（或者更大）。否则什么也不做,且不会退回多余空间。

具体实现时，调用shrink_to_fit也并不保证一定退回内存空间

capacity和size

size是指已经保存的元素的数目；
capacity是不分配新的内存空间的前提下它能最多保存的元素个数

vector<int> ivec;
cout << "ivec: size:" << ivec.size()
     << "ivec: capacity:" << ivec.capacity() << endl;
//add 24 elements
for(vector<int> :: size_type ix = 0; ix != 24; ++ix)
    ivec.push_back(ix);

cout << "ivec: size:" << ivec.size()
     << " capacity :" << ivec.capacity() << endl;

结果为：

ivec: size: 0 capacity : 0
ivec: size: 24 capacity : 32

可以再预分配一些额外空间

ivec.reserve(50);

接下来用光预留空间

while (ivec.size() != ivec.caoacity())
    ivec.push_back(0);

只要操作没大于预留空间，vector就不会重新分配空间

ivec.push_back(42);

此时capacity = 100;
vector实现采用的策略似乎是在每次需要分配空间时将当前容量翻倍
可以调用shrink_to_fit()来要求退回多余内存

ivec.shrink_to_fit();

shrink_to_fit()只是一个请求，标准库不保证能退还内存
所有实现要遵循一个原则：确保用push_back向vector添加元素的操作有高效率

9.5 额外的string操作

构造string的其他方法

string s(cp,n)      //s是cp指向的数组中前n个字符的拷贝,此数组至少包含n个字符
string s(s2,pos2)       //s是string s2从下标pos2开始的拷贝
string s(s2,pos2,lens)  //从s2下标pos2开始拷贝lens长度

构造函数接受一个string或const char*的参数，还可以接受指定数量的字符以及开始的下标

使用前必须考虑字符串长度没有溢出，且如果一直拷贝到最后必须以空字符结尾。

substr

s.substr(pos,n)     //返回一个string，从pos开始的n个字符的拷贝

改变string的其他方法

拥有额外的insert和erase版本(接受下标的版本)

s.insert(s.size(), 5, '!');     //在s末尾插入5个感叹号
s.erase(s.size() - 5, 5);       //删除最后5个字符

标准库string类型还提供了接受c风格字符串数组的insert和assign

const char *cp = "Stately, plump, Buck";
s.assign(cp, 7);        //s = "Stately"
s.insert(s.size(), cp + 7);     //s = "Stately, plump, Buck"

也可以指定将来自其他string或子字符串的字符插入到string

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

append 和 replace

append是在末尾插入的简写形式
replace是调用erase和insert的简写形式

s.append("aaa");    //末尾添加aaa
s.replace(11, 3, "5th") //从11开始，删除3个字符，插入5th

更多的重载函数见表9.13

string的搜索操作

提供6种搜索函数，每个函数有4个重载版本。见表9.14
每个返回一个string::size_type的值，表示匹配发生位置的下标。
如果搜索失败返回string::npos的static成员,npos定义为一个const string::size_type类型，初始值为-1。
size_type是一个unsigned类型，因此用int或者无符号来保存这个值不好。

find完成简单搜索，查找参数指定的字符串，找到返回下标，找不到返回npos

string name("AnnaBelle")
auto pos1 = name.find("Anna");  //0

查找与给定字符串中任何一个字符匹配的位置

string numbers("0123456789"), name("r2d2");
auto pos = name.find_first_of(numbers);     //1
string dept("03714p3");
auto pos = dept.find_first_not_of(numbers); //5

指定从哪里开始搜索

可以给find传递一个可选的开始位置,默认置0

string::size_type pos = 0;
while ((pos = name.find_first_of(numbers, pos)) != string::npos)
{
    cout << "found number at index:" << pos 
         << " element is " << name[pos] << endl;
    ++pos;
}

逆向搜索

rfind函数搜索最后一个匹配

string river("Mississippi");
auto first_pos = river.find("is");      //返回1
auto last_pos = river.rfind("is");      //返回4

类似还有find_last_of和find_last_not_of,搜索匹配的最后一个字符和最有一个不出现在给定string中的字符

compare函数

用于比较，有6个版本见表9.15

数值转换

int i = 42;
string s = to_string(i);        //i转成字符
double d = stod(s);             //s转成浮点

string s2 = "pi = 3.14";
d = stod(s2.substr(s2.find_first_of("+-.0123456789"))//转换以数字开始的第一个字串

9.6容器适配器

三个顺序容器适配器:stack、queue和priority_queue
适配器是一种机制，使某种事物的行为看起来像另外一种事物。
一个容器适配器能接受一种已有容器类型，使其行为看起来像一种不同的类型。
见表9.17

定义一个适配器

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。
假定deq是一个deque

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

默认情况下，stack和queue是基于deque实现的，priority_queue实在vector之上实现的。我们可以再创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

// 在vector上实现的空栈
stack<string, vector<string>> str_stk;
//str_stk2在vector上实现，初始化时保存svec的拷贝
stack<string, vector<string>> str_stk2(svec);

所有适配器都要求添加删除元素，因此不能构建在array之上。
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头文件

stack<int> intStack;
for (size_t ix = 0; ix != 10; ++ix)
    intStack.push(ix);
while(!intStack.empty())
{
    int value = intStack.top(); //使用栈顶
    intStack.pop(); //弹出栈顶
}

操作有

//默认基于deque，也可以在list或vector上实现
s.pop()     //弹出
s.push(item)    //加入
s.emplace(args)
s.top()   //返回栈顶元素

虽然是基于deque的，但不能直接使用deque的操作，不能用push_back必须用push

队列适配器

queue默认基于deque
priority_queue默认基于vector

q.pop()     //删除
q.front()   //返回首元素或尾元素，但不删除
q.back()    //只适用于queue
q.top()     //只适用priority_queue,返回优先级最高元素
q.push(item)    //末尾添加
q.emplace(args)

queue使用先进先出的存储和访问策略。
priority_queue允许为队列元素建立优先级，按优先级排位置