《C++Primer》第九章 顺序容器

2020-11-19  本文已影响0人  TOMOCAT

简介

容器指的是一些特定类型对象的集合，顺序容器sequential container为程序员提供了控制元素在存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

后面第十一章会介绍有序和无序关联容器，会根据关键字的值来存储元素。

顺序容器类型

需要注意的是：

选择容器的基本原则

如果你不确定应该是用哪种容器，那么可以在程序中只使用vector和list公共的操作：使用迭代器，不使用下标操作，这样可以避免随机访问。

容器库概览

1. 容器操作

类型别名 含义
iterator 此容器类型的迭代器类型
const_iterator 可以读取元素，但是不能修改元素的迭代器类型
size_type 无符号整数类型，足够保存此种容器类型最大可能容器的大小
difference_type 带符号整数类型，足够保存两个迭代器之间的距离
value_type 元素类型
reference 元素的左值类型; 与value_type& 含义相同
const_reference 元素的const左值类型，即const value_type& 
// 默认构造函数, 构造空容器
C c;

// 构造c2的拷贝c1
C c1(c2);

// 构造c, 将迭代器b和e指定范围内的元素拷贝到c
C c(b, e);

// 列表初始化c
C c{a, b, c...};

// 将c1中的元素替换为c2
c1 = c2;

// 将c1中的元素替换为列表中元素
c1 = {a, b, c...};

// 交换a和b的元素
a.swap(b);
swap(a, b);

// c中元素的数目, 不支持forward_list
c.size();

// c可保存的最大元素数目
c.max_size();

// 判断c中是否保存元素
c.empty();

注：在不同的容器中，这些操作的接口都不同

// 将args中的元素拷贝进c
c.insert(args);

// 使用initss构造c中一个元素
c.emplace(inits);

// 删除args指定的元素
c.erase(args);

// 删除c中所有元素, 返回void
c.clear();

// 所有容器都支持相等和不等运算符
==, !=

// 关系运算符, 无序关联容器不支持
<, <=, >, >=

// 返回指向c的首元素和尾元素之后的迭代器
c.begin(), c.end()

// 返回const_iterator
c.cbegin(), c.cend()

// 按逆序寻址元素的迭代器
reverse_iterator

// 不能修改元素的逆序迭代器
const_reverse_iterator

// 不能修改元素的逆序迭代器
c.rbegin(), c.rend()

// 返回const_reverse_iterator
c.crbegin(), c.crend()

2. 迭代器

注意迭代器的范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或尾元素之后的位置。通常被称为begin和end。这种表示有三种方便的性质：

另外注意begin和end有多种版本：带r的版本返回反向迭代器；以c开头的版本返回const迭代器。不以c开头的函数都是被重载过的，即实际上有两个名为begin的成员，一个是const成员返回容器的const_iterator类型，另一个是非常量成员返回容器的iterator类型。

当不需要写访问时，应使用cbegin和cend。

3. 容器定义和初始化

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

// c1初始化为c2的拷贝, c1和c2必须是相同类型, 对于array而言两者还必须具有相同大小
C c1(c2)
C c1=c2

// c初始化为初始化列表中元素的拷贝。列表中的元素类型必须和C的元素类型相容, 对于array类型而言列表中元素数目必须等于或者小于array的大小, 任何遗漏的元素都进行值初始化
C c{a,b,c...}
C c={a,b,c...}

// c初始化为迭代器b和e指定范围内元素的拷贝, 范围中元素的类型必须与C的元素类型相容(array不使用)
C c{b,e}

// 只有顺序容器(不包括array)的构造函数才能接受大小实参
C seq(n)    // seq包含n个元素, 这些元素进行了值初始化; 此构造函数是explicit的(string不适用)
C seq(n,t)  // seq包含n个初始化为t值得元素

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。不过当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了，新容器内的元素类型只要能转换成初始化容器的元素类型即可

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

// 拷贝方式一：直接拷贝整个容器, 要求容器类型和元素类型都必须相同
list<string> list2(authors);    // 正确: 类型匹配
vector<string> words(articles); // 错误: 容器类型不匹配

// 拷贝方式二：传递迭代器参数来拷贝一个范围
// 正确: 可以将const char* 元素转换为string
forward_list<string> words(articles.begin(), articles.end());

我们可以对容器进行列表初始化，这样会显式指定容器内每个元素的值。除了array外，初始化列表还隐含地指定了容器的大小：容器将包含与初始值一样多的元素。

除了与关联容器相同的构造函数外，顺序容器（array除外）还提供另一个构造函数，它接受一个容器大小和一个（可选的）元素初始值。如果不提供初始值，则标准库会创建一个值初始化器。

vector<int> ivec(10, -1);     // 10个int元素, 每个都初始化为-1
list<string> svec(10, "hi!"); // 10个string； 每个都初始化为"hi!"
forward_list<int> ivec(10);   // 10个元素, 每个都初始化为0
deque<string> svec(10);       // 10个元素, 每个都是空string

与内置数组一样，标准库array的大小也是类型的一部分，当定义一个array时，除了指定元素类型还必须指定容器大小：

array<int, 10> ia1;   // 10个默认初始化的int
array<int, 10> ia2 = {42}; // ia3[0]为42, 剩余元素为0

注意：虽然我们不能对内置数组类型进行拷贝或对象赋值操作，但array没有这个限制。

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs;  // 错误: 内置数组不支持拷贝或者赋值
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits; // 正确

4.赋值和swap

如果俩容器的大小不同，那么赋值运算后两者的大小都与右边容器的原大小相同：

c1 = c2;      // 将c1的内容替换为c2中元素的拷贝
c1 = {a,b,c}; // 赋值后, c1大小为3

与内置数组不同，array类型允许赋值，但是赋值号左右两边的运算对象必须具有相同的类型：

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 19> a2 = {0}; // 所有元素均为0
a1 = a2;  // 替换a1中的元素
a2 = {0}; // 错误：不能将一个花括号列表赋予数组

容器赋值运算除了=操作符外，还包括swap()和assign()：

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

// 将c1中元素替换为初始化列表中元素的拷贝（array不适用）
c={a,b,c...}

// 交换c1和c2中的元素, c1和c2必须具有相同的类型, swap操作通常比从c2向c1拷贝元素快得多
swap(c1, c2)
c1.swap(c2)

// assign不适用于关联容器和array
// 将seq中的元素替换为迭代器b和e所表示范围的元素
seq.assign(b,e) 
// 将seq中的元素替换为初始化列表il中的元素
seq.assign(il)
// 将seq中的元素替换为n个值为t的元素
seq.assign(n,t)
seq.assign(il)

5. 容器大小操作

除了forward_list外，所有容器类型都有三个与大小相关的操作：

forward_list支持max_size和empty，但不支持size

6. 关系运算符

每个容器都支持相等运算符（==和!=），除了无序关联容器外的所有容器都支持关系运算符（>, >=, <, <=）。关系运算符两边必须是保存相同类型元素的容器。本质上是对容器内每个元素逐个比较：

顺序容器操作

1. 向顺序容器添加元素

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

需要注意如下几点：

具体的添加元素操作包括：

注意：向一个vector、string或者deque插入元素会使得所有指向容器的迭代器、引用和指针失效。在一个vector或者string的尾部之外任何位置，或是一个deque的首尾之外的任何位置添加元素都需要移动元素。向vector或者string添加元素可能引起整个对象存储空间的重新分配（重新分配一个存储一个对象的内存，并激昂元素从旧的空间移动到新的空间）。

当调用push或者insert成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。

2. 访问元素

包括array在内的每个顺序容器都有一个front成员函数，而除forward_list之外的所有顺序容器都有一个back成员函数。这两个操作分别返回首元素和尾元素的引用。

具体的访问元素操作包括：

使用front或者back成员函数前需要判断c.empty()是否为真

// 在容器中访问元素的成员函数（front、back、at和下标）返回的都是引用
if (!c.empty()) {
    auto &v = c.back();  // 获得最后一个元素的引用
    v = 1024;            // 改变c中最后一个元素
    auto v2 = c.back();  // v2不是一个引用, 只是c.back()的一个拷贝
    v2 = 0;              // 并不会改变c中最后一个元素
}

3. 删除元素

注意：

相关的操作包括：

4. 特殊的forward_list操作

假设一个forward_list表示为如下：

// 删除elem3之前
elem1 -> elem2 -> elem3 -> elem4

// 删除elem3会改变elem2的值
elem1 -> elem2 -> elem4

由于forward_list是一个单向链表，因此我们没有简单的方法来获取一个元素的前驱。forward_list定义了名为insert_after、emplace_after和erase_after。为了支持这些操作，forward_list也定义了before_begin，它返回一个首前元素。这个迭代器允许我们在链表首元素之前添加/删除元素。

具体的操作包括：

5. 改变容器大小

除了array外我们可以使用resize()来增加或者缩小容器，如果当前大小小于所要求的大小，容器后面的元素会被删除；如果当前大小小于新大小，会将新元素添加到容器后部。

6. 容器操作可能使得迭代器失效

向容器添加元素：

删除元素后：

管理容器大小的操作

额外的string操作

1. 构造string的其他方法

2. 改变string的其他方法

string类型支持顺序容器的赋值运算以及assign、insert和erase操作，同时还定义了额外的insert和erase版本。

上面提到的args可以是一下形式之一：

注意：

3. string搜索操作

string类提供了6个不同的搜索函数，每个搜索操作返回一个string::size_type值，表示匹配发生位置的下标。如果搜索失败则返回一个名为string::npos的static成员。搜索操作包括：

args须是以下形式之一：

4. compare函数

类似于strcmp函数，根据s是等于、大于还是小于参数指定的字符串，s.compare返回0、正数或者负数。根据我们是要比较两个string还是一个string与一个字符数组，我们可以将compare划分为6个版本：

5. 数值转换

要转换为数值的string中第一个非空白符必须是数值中可能出现的字符，如果string不能转换为一个数值则这些函数会抛出一个invalid_argument的异常。

容器适配器

标准库定义了三个顺序容器适配器：stack、queue和priority_queue，一个容器适配器接收一种已有的容器类型，使其行为看起来像一种不同的类型。例如stack适配器接收一个顺序容器（除array或forward_list外），并使其操作起来像一个stack一样。

1. 容器适配器都支持的操作和类型

2. 定义一个适配器

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。默认情况下，stack和queue是基于deque实现的，priority_queue是基于vector实现的。但我们也可以通过在创建一个适配器时将一个命名的顺序容器作为第二个类型参数来重载默认容器类型。

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

3. 栈适配器

栈默认基于deque实现，也可以再list或者vecotr上实现

4. 队列适配器

queue默认基于deque实现，也可以用list和vecotr实现。priority_queue默认基于vector实现，也可以用deque实现。

上一篇下一篇

猜你喜欢

热点阅读