C++ Primer第九章顺序容器

C++ Primer第九章顺序容器

所有的顺序容器都提供了快速顺序访问的能力。但是这些容器在以下方面都有不同的性能折中。

想容器添加或从容器中删除元素的代价

非顺序访问容器中元素的代价

vector 可变大小数组,支持快速随机访问,在尾部之外的位置插入或删除元素可能很慢。

deque  双端队列.支持快速随机访问。在头尾位置插入/删除速度很快。

list  双向列表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快

forward_list 单向列表,只支持单向顺序访问。在链表任何位置进行插入/删除操作都很快

arry 固定大小数组。支持快速随机访问,不能添加或删除元素

string 与vector相似但专门用于保存字符,随机访问快.在尾部插入/删除速度快

迭代器

forward_list迭代器不支持递减运算符(--)

迭代器范围

由一对迭代器表示,两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置。(begin,end)

end指向的不是最后一个元素而是指向尾元素之后的位置。

即元素范围是左闭合区间[begin,end)

容器类型成员

通过类型别名我们可以在不了解容器中元素类型的情况下使用它。如果需要元素类型可以使用容器的value_type.如果需要元素类型的引用可以使用reference或者const_reference。

begin和end成员

有多个版本带r的版本返回反向迭代器,带c的版本返回const迭代器。

容器定义和初始化

每个容器类型都定义了一个默认构造函数。除array之外,其他容器的默认构造函数都会创建一个指定类型的空容器,且都可以接受指定容器大小和元素初始值的参数

C c;//默认构造函数,如果C是一个array则c中元素按默认方式初始化

C c1(c2);//拷贝构造函数,相同的容器类型和保存相同的元素类型

C c1 = c2;//相同的容器类型,相同的元素类型对于array还需大小相同

C c{a,b,c,...};

C c = {a,b,c,...};

初始化列表。

C c(b,e);初始化为迭代器b和e指定范围中元素的拷贝

只有顺序容器不包括array的构造函数才能接受大小参数

C seq(n);//seq包含n个元素,并对元素进行了值初始化

C seq(n,t);//seq包含n个初始化为值t的元素。

赋值和swap

c1 = c2;//将c1中的元素替换为c2中元素的拷贝。c1和c2必须具有相同的类型

c = {a,b,c...};//初始化列表中元素的拷贝给c

swap(c1,c2);

c1.swap(c2);

交换c1和c2中的元素。c1和c2必须具有相同的类型。

assign操作不适用于关联容器和array

seq.assign(b,e)

将seq中的元素替换为迭代器b和e所表示的范围中的元素。

b,e不能指向seq中的元素

seq.assign(il);//将seq中的元素替换为初始化列表il中的元素

seq.assign(n,t)//将seq中的元素替换为n个值为t的元素。

赋值相关运算会导致指向左边容器内部的迭代器,引用和指针失效。而swap操作将容器内容交换不会导致指向容器的迭代器,引用和指针失效。

swap只是交换了两个容器的内部数据结构除了array外

对一个string调用swap会导致迭代器,引用和指针失效

容器大小操作

每个容器类型都有三个与大小相关的操作。成员函数size返回容器中元素的数目;empty当size为0时返回布尔值true否则false.max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。forward_list不支持size

关系运算符

只有当其元素类型也定义了相应的比较运算符时我们才可以使用关系运算符来比较两个容器。

顺序容器操作

顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储,访问,添加以及删除。

向容器中添加元素

除array外,所有标准库容器都提供灵活的内存管理。在运行时可以动态添加删除元素来改变容器大小

forward_list有自己专有版本的insert,emplace

forward_list不支持push_back和emplace_back

vector和string不支持push_front和emplace_front

c.push_back(t);

c.emplace_back(args);

//在c的尾部创建一个值为t或由args创建的元素

c.push_front(t)

c.emplace_front(args)

//在c的头部创建一个值为t或由args创建的元素

c.insert(p,t)

c.emplace(p,args)

在迭代器p指向的元素之前创建一个值为t或由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)

il是一个花括号保卫的元素值列表。将这些给定值插入到迭代器p指向的元素之前。

向一个vector,string,deque插入元素会使得所有指向容器的迭代器,引用和指针失效。

容器元素是拷贝

当我们用一个对象来初始化容器时,或将一个对象插入到容器中时,实际上放入到容器中的是对象值的一个拷贝而不是对象本身。就像我们将一个对象传递给非引用参数一样,容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象。

使用emplace操作

emplace_front,emplace和emplace_back这些操作构造而不是拷贝元素,即将参数传递给元素类型的构造函数。

访问元素

包括array在内的每个顺序容器都有一个front成员函数而除forword_list之外的所有顺序容器都有一个back函数。

at和下标操作只适用于string,vector,deque和array

at下标越界会抛出异常而[]不会检查是否越界

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

删除元素

forward_list不支持pop_back,

vector和string不支持pop_front

c.pop_back()删除尾元素

c.pop_front()删除首元素

c.erase(p)删除迭代器p所指定的元素返回一个指向被删除元素之后元素的迭代器。

c.erase(b,e)删除迭代器b和e所指定范围内的元素。

c.clear()删除c中的所有元素

删除deque中除首尾位置之外的任何元素都会使所有迭代器,引用和指针失效。指向vector或string中删除点之后位置的迭代器,引用和指针都会失效。

改变容器大小resize来增大或缩小容器。

c.resize(n)调整c的大小为n个元素

c.resize(n,t)新添加的元素初始化为t

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

向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针。

在向容器添加元素之后

如果容器是vector或string且存储空间被重新分配则指向容器的迭代器,引用都会失效。如果没有重新分配则指向插入位置之前的元素的迭代器,指针,应用仍有效,但指向插入位置之后元素迭代器,指针和引用会失效。

对于deque插入到除首尾以外的任何位置都会导致迭代器,指针和引用失效。如果在首尾添加元素迭代器会失效,但指向存在的元素的引用和指针不会失效。

对于list和forward_list指向容器的迭代器,指针和引用仍有效。

当我们从一个容器删除元素后指向被删除元素的迭代器,指针和引用会失效。

对于list,forward_list指向容器其他位置的迭代器,引用和指针仍有效。

对于deque如果在首尾之外删除元素,那么指向被删除元素外其他元素的迭代器,引用或指针也会失效如果是尾元素则尾后迭代器也会失效。如果是首元素则不受影响。

对于vector,string指向被删元素之前迭代器,引用,指针有效。

vector对象是如何增长的

当没有空间容纳新的元素,容器不可能简单地将它添加到内存中的其他位置。因为元素必须连续存储。容器必须分配新的内存空间来保存已有元素和新元素。将已有元素从旧位置移动到新空间中然后添加锌元素,释放旧存储空间。

shrink_to_fit()只适用于vector,string,deque

c.shrink_to_fit()//将capacity()减少为与size相同大小

c.capacity()//不重新分配内存空间的话,c可以保存多少元素。

c.reserve(n)//分配至少能容纳n个元素的内存空间。

额外的string操作

string s(cp,n);

s是cp指向数组中前n个字符的拷贝

string s(s2,pos2);

s是从s2从下标pos2开始的字符的拷贝。

string s(s2,pos2,len2)

s是s2从下标pos2开始len2个字符拷贝。

substr返回子串

s.substr(pos,n)

返回一个string包含s中从pos开始的n个字符的拷贝。pos的默认值为0.

s.insert(pos,args)

在pos之前插入args指定的字符。pos可以是一个下标或一个迭代器。

s.erase(pos,len)

删除从位置pos开始的len个字符。如果len省略则删除所有

s.assign(args)

将s中的字符替换为args指定的字符

s.append(args)

将args追加到s

s.replace(range,args)

删除s中范围range内的字符,替换为args指定的字符。

string搜索操作

s.find(args)

查找s中args第一次出现的位置

s.rfind(args)

查找s中args最后一次出现的位置

s.find_first_of(args)

在s中查找args中任何一个字符第一次出现的位置

s.find_last_of(args)

在s中查找args中任何一个字符最后一次出现的位置。

s.find_first_not_of(args)

在s中查找第一个不在arg中的字符

s.find_last_not_of(args)

在s中查找最后一个不再args中的字符

compare函数

s2比较s和s2

pos1,n1,n2

将s中从pos1开始的n1个字符与s2进行比较

pos1,n1,s2,pos2,n2

将s中从pos1开始的n1个字符与s2中从pos2开始的n2个字符进行比较。

cp比较s与cp指向的以空字符结尾的字符数组

pos1,n1,cp

将s中从pos1开始的n1个字符与cp指向的以空字符结尾的字符数组进行比较。

pos1,n1,cp,n2

将s中从pos1开始的n1个字符与指针cp指向的地址开始的n2个字符进行比较

转换函数

to_string(val)

转换成string

stoi(s,p,b)

stol(s,p,b)

stoul(s,p,b)

stoll(s,p,b)

stoull(s,p,b)

返回s的起始子串的数值返回类型是int,long,unsigned long long long,unsigned long long .b表示要转换所用的基数默认是10

stof(s,p)

stod(s,p)

stold(s,p)

返回s的起始子串的数值返回类型是float,double,long double

容器适配器

stack,queue,priority_queue

栈默认是基于deque实现也可以在list或vector上实现

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