顺序容器

文章目录
  1. 1. 顺序容器概述
  2. 2. 容器概览
    1. 2.1. 迭代器
    2. 2.2. 容器类型成员
    3. 2.3. begin和end成员
    4. 2.4. 容器的定义和初始化
    5. 2.5. 赋值和swap
    6. 2.6. 容器的大小操作
    7. 2.7. 关系运算符
  3. 3. 顺序容器的操作
    1. 3.1. 向顺序容器添加元素
    2. 3.2. 访问元素
    3. 3.3. 删除元素
    4. 3.4. 改变容器的大小
    5. 3.5. 容器操作可能使迭代器失效
  4. 4. vector对象是如何生长的
  5. 5. 额为的string操作
    1. 5.1. 构造string的其他方法

主要内容

  1. 顺序容器概述
  2. 容器库概览
  3. 顺序容器操作
  4. vector对象是如何生长的
  5. 额外的string操作
  6. 容器适配器

顺序容器概述

容器在以下方面都有不同的性能折中:

  1. 向容器添加或者删除元素的代价
  2. 非顺序访问容器中元素的代价
容器类型 性能
vector 可变大小数组,支持快速随机访问,在尾部之外的位置插入或删除元素可能很慢
deque 双端队列,支持快速随机访问,在头尾位置插入、删除速度快
list 双向链表,只支持双向顺序访问,在list中任何位置插入、删除操作熟读都很快
forward_list 单向链表。只支持单向顺序访问,在链表任何位置插入、删除操作都非常快
array 固定大小数组,支持快速随机访问,不能添加或删除元素
string 与vector相似的容器,但专门用于保存字符,随机访问快,在尾部插入、删除快

string、vector将元素保存在连续的内存空间,由于元素是连续存储的,由元素的下标计算其地址非常快。

list、forword_list两个容器的设计目的是令容器容器的任何位置添加、删除操作都很快

容器概览

类型 说明
类型别名
iterator 容器的迭代器类型
const_iterator 可以读取元素,但不能修改元素的迭代器类型
size_type 无符号整数类型,足够保存此种容器类型最大可能大小
difference_type 带符号整数类型,足够保存两个迭代器之间的距离
value_type 元素类型
reference 元素的左值类型,与value_type&含义相同
const_reference 元素的const左值类型(const value_type &)
构造函数
C c; 默认构造函数,构造空的容器
C c1(c2) 构造出c2的拷贝c1
C c(b,e) 构造c,将迭代器b和e指定的范围内的元素拷贝到c (array不支持)
C c{a,b,c …} 列表初始化
赋值与swap
c1= c2 将c1中的元素地换为c2中的元素
c1 = {a,b,c …} 将c1中的元素退换为列表中的元素(array不适用)
a.swap(b) 交换a和b的元素
swap(a,b) 与a.swap(b)等价
大小
c.size() c中元素的书面(forward_list不支持)
c.max_size() c可保存的最大元素数目
c.empty() c中存储了元素,返回false,否则返回true
添加删除元素(不适用array) 在不同的容器中,这些操作的接口都不同
c.insert(args) 将args中的元素拷贝进c
c.emplace(inits) 使用inits构造c中的一个元素
c.erase(args) 删除args指定的元素
c.clear() 删除c中的所有元素,返回void
关系运算符
==, != 所有容器都支持相等(不等于)运算符
<,<=,>,>= 无序关联容器不支持
获取迭代器
c.begin(), c.end() 返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(),c.cend() 返回const_iterator
反向容器的额外成员(不支持forward_list)
reverse_iterator 逆序寻址元素的迭代器
const_reverse_iterator 不修改元素的逆序迭代器
c.rbegin(),c.rend() 返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(),c.crend 返回const_reverse_iterator

迭代器

forword list 不支持递减运算符

迭代器范围中的元素包括first所表示的元素以及从first开始,直至last(但不包括last)之间的所有元素,左闭合区间。

1
[begin end)

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

  1. 如果begin和end相等,则范围为空
  2. 如果begin和end不相等,则范围至少包含一个元素,且begin指向范围中的第一个元素
  3. 我们可以对begin递增若干次,使得begin==end

容器类型成员

1
list<string>""iterator iter;

begin和end成员

begin和end操作生成指向容器中第一个元素和尾元素之后的迭代器。

容器的定义和初始化

容器的定义和初始哈
C c 默认构造函数,如果C是一个array,则c中元素默认初始化,否则c为空
C c1()c2 C c1 = c2 c1初始化为c2的拷贝,c1和c2必须类型相同,对于arrary,大小相同
C c{a,b,c,…} C c = {a,b,c,…} c初始化为初始化列表中元素的拷贝
C c(b,e) c初始化为迭代器b,e指定范围中的元素的拷贝
C seq(n) C seq(n,t) seq 包含n个元素,这些元素进行了值初始化,此构造函数是explicit的

容器的拷贝: 两种方式

  1. 直接拷贝整个容器
  2. 拷贝迭代器指定的元素范围

    当将一个容器初始化为另一个容器的拷贝时,两个容器类型和元素类型必须相同。

    列表初始化:对于除了array之外的容器类型,初始化列表还隐含地指定了容器的大小:容器将包含与初始值一样多的元素。

    标准库array具有固定大小:标准库array的大小是类型的一部分, array与内置数组的区别:array可以进行拷贝和对象赋值。

    赋值和swap

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

    容器的大小操作

  3. size

  4. empty
  5. max_size

    关系运算符

    只有当其元素的类型定义了关系运算符,我们才可以使用关系运算符比较容器

    顺序容器的操作

    向顺序容器添加元素

    |操作|说明|
    |—|—|
    |这些操作不支持会改版容器的大小,array不支持这些操作||
    |forward_list有专有版本的insert和emplace||
    |forward_list不支持push_back和emplace_back,由于没有位指针,算法复杂度是o(n)||
    |vector和string不支持push_font和emplace_font,也是算法复杂度的原因,整个元素需要移动,单可以通过inser做到||
    |c.push_back(t)|在C的尾部创建一个值为t或由args创建的创建的元素,返回void|
    |c.emplace_back(args)||
    |||
    |c.push_font(t)|在C的首部创建一个值为t或由args创建的创建的元素,返回void|
    |c.emplace_font(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)|il是花括号包围的元素值列表|
    |向一个vector、string、deque插入元素,会使所有指向容器的迭代器、引用、指针失效|

    使用push_back:除了array、forward_list之外,每个顺序容器都支持push_back。

    当我们用一个对象初始化容器时,或将一个对象插入到容器中,实际上,放入到容器中的是对象的一个拷贝,二不是对象本身。

    使用push_font:和vector一样,在deque首位之外的位置插入元素会很耗时。

    在容器中的特定位置插入元素:insert提供了更一般的功能,它允许在容器中的任何位置插入0个或者多个元素。每个insert函数,都接受一个迭代器作为其第一个参数,迭代器指出了在容器的什么位置插入元素。

    为什么是前插:因为迭代器可能只需容器外部之后不存在的元素的位置,所以只能前插。另外,在容器开始位置插入元素是很有用的功能。

    我们可以使用insert将元素插入容器的开始位置,不用担心是否支持push_font。

    如果我们传递给insert一对迭代器,他们不能指向添加元素的目标容器。

    使用insert的返回值:通过使用insert的返回值,可以在容器中的一个特定位置反复插入元素。

    emplace操作:新标准引入了三个成员:emplace、emplace_font 、emplace_back,这些操作构造而不是拷贝元素。

    emplace函数在容器中直接构造元素,传递给emplace函数的参数必须与元素类型的构造函数相匹配。

    访问元素

    包括array在内的所有容器都有一个font函数,而除了forword_list之外的所有容器都有一个back成员函数。这两个成员函数分别返回首元素和尾元素的索引。

    |容器的访问操作|说明|
    |—|—|
    ||at和下标操作只使用于string、vector、deque、和array|
    ||back不适用forward_list,算法复杂度的问题|
    |c.back()|返回c的尾元素的引用|
    |c.font()|返回c的首元素的引用|
    |c[n]|返回c中下表为n的元素的引用|
    |c.at(n)|返回下标为n的元素的引用。|

提供快速随机访问的容器(string、vector、deque、array)都提供下标运算符

at成员函数类似下标运算符,但如果下标越界,at会抛出一个out_of_range的异常。

删除元素

删除操作 说明
这些操作会给变容器的大小,不适用于array
forward_list有特殊版本的erase
forward_list不支持pop_back,string、vector不支持pop_font
c.pop_font() 删除c中的首元素
c.pop_back() 删除c中的尾元素
c.erase(p) 删除迭代器p所指定的元素
c.erase(b,e) 删除迭代器be所指范围内的元素
c.clear() 删除c中的所有元素

###特殊的forward_list操作

特殊操作的原因:删除或者插入操作,我们需要访问它的前驱,以便改变前驱的链接,但是forward_list中,没有简单的方法获取一个元素的前驱。forward_list定义了insert_after、emplace_after、erase_after操作。before_begain,返回一个首前。

|forward_list操作|说明|
|lst.before_begain()|返回指向链表首元素之前不存在的元素的迭代器,此迭代器不能解引用|
|lst.cbefore_begain()||
|lst.insert_after(p,t)|在迭代器之后插入一个元素|
|lst.insert_after(p,n,t)||
|lst.insert_after(p,b,e)||
|lst.insert_after(p,il)||
|emplace_after(p,args)||
|lst.erase_after(p)||
|lst.erase_after(b,e)||

改变容器的大小

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

vector对象是如何生长的

|容器大小操作|说明|
||shrink_to_fit 只适用于vector、string、deque|
||capacity和reserve只适用于vector、string|
|c.shrink_to_fit|请将capacity()减少为size相同大小|
|c.capacity()|不重新分配内存空间的话,c可以保存多少元素|
|c.reserve()|分配至少容纳那n个元素的内存空间|

额为的string操作

构造string的其他方法

构造string的其他方法 说明
string s(cp,n) s是cp指向的数组中前n个字符的拷贝,此数组至少应该包含n个字符
string s(s2,pos2) s是string s2从下标POS2开始的字符的拷贝,若pos2>s2.size(),构造函数的行为未定义
string s(s2,pos2,len2)