C++ 顺序容器

《C++ Primer 4th》读书笔记

顺序容器内的元素按其位置存储和访问。容器类共享公共的接口,每种容器类型提供一组不同的时间和功能折衷方案。通常不需要修改代码,只需改变类型声明,用一种容器类型替代另一种容器类型,就可以优化程序的性能。

标准库定义了三种顺序容器类型:vector、list 和 deque(是双端队列“double-ended queue”的简写,发音为“deck”)。它们的差别在于访问元素的方式,以及添加或删除元素相关操作的运行代价。标准库还提供了三种容器适配器(adaptors)。实际上,适配器是根据原始的容器类型所提供的操作,通过定义新的操作接口,来适应基础的容器类型。顺序容器适配器包括 stack、queue 和 priority_queue 类型。

容器只定义了少量操作。大多数额外操作则由算法库提供。

顺序容器类型

顺序容器

vector

支持快速随机访问

list

支持快速插入/删除

deque

双端队列

顺序容器适配器

stack

后进先出(LIFO)堆栈

queue

先进先出(FIFO)队列

priority_queue

有优先级管理的队列

为了定义一个容器类型的对象,必须先包含相关的头文件,即下列头文件之一:

#include <vector>

#include <list>

#include <deque>

所有的容器都是类模板。要定义某种特殊的容器,必须在容器名后加一对尖括号,尖括号里面提供容器中存放的元素的类型,所有容器类型都定义了默认构造函数,用于创建指定类型的空容器对象:

vector<string> svec; // empty vector that can hold strings

list<int> ilist; // empty list that can hold ints

deque<Sales_item> items; // empty deque that holds Sales_items

不提供元素初始化式时,标准库将为该容器实现值初始化.采用这种类型的初始化,元素类型必须是内置或复合类型,或者是提供了默认构造函数的类类型。如果元素类型没有默认构造函数,则必须显式指定其元素初始化式。

容器构造函数

C<T> c;

创建一个名为 c 的空容器。C   是容器类型名,如 vector,T 是元素类型,如 int 或 string 适用于所有容器。

C c(c2);

创建容器 c2 的副本 c;c 和 c2   必须具有相同的容器类型,并存放相同类型的元素。适用于所有容器。

C c(b,e);

创建 c,其元素是迭代器 b 和 e 标示的范围内元素的副本。适用于所有容器。

C c(n,t);

用 n 个值为 t 的元素创建容器   c,其中值 t 必须是容器类型 C 的元素类型的值,或者是可转换为该类型的值。只适用于顺序容器

C c(n);

创建有 n 个值初始化(第 3.3.1   节)(value-initialized)元素的容器 c。只适用于顺序容器

不能直接将一种容器内的元素复制给另一种容器,但系统允许通过传递一对迭代器间接实现该实现该功能。使用迭代器时,不要求容器类型相同。容器内的元素类型也可以不相同,只要它们相互兼容,能够将要复制的元素转换为所构建的新容器的元素类型,即可实现复制。

指针就是迭代器,因此允许通过使用内置数组中的一对指针初始化容器也就不奇怪了:

char *words[] = {"stately", "plump", "buck", "mulligan"};

// calculate how many elements in words

size_t words_size = sizeof(words)/sizeof(char *);

// use entire array to initialize words2

list<string> words2(words, words + words_size);

容器内元素的类型约束

容器元素类型必须满足以下两个约束:

• 元素类型必须支持赋值运算。

• 元素类型的对象必须可以复制。

除了引用类型外,所有内置或复合类型都可用做元素类型。引用不支持一般意义的赋值运算,因此没有元素是引用类型的容器。除输入输出(IO)标准库类型(以及 auto_ptr 类型)之外,所有其他标准库类型都是有效的容器元素类型。IO 库类型不支持复制或赋值。因此,不能创建存放 IO 类型对象的容器。

可定义元素是容器类型的容器。

// note spacing: use ">>" not ">>" when specifying a container element type

vector< vector<string> > lines; // vector of vectors

必须用空格隔开两个相邻的 > 符号,以示这是两个分开的符号,否则,系统会认为 >> 是单个符号,为右移操作符,并导致编译时错误。

常用迭代器运算

所有标准库容器类型所提供的运算

*iter

返回迭代器 iter 所指向的元素的引用

iter->mem

对 iter   进行解引用,获取指定元素中名为 mem 的成员。等效于(*iter).mem

++iter

iter++

给 iter 加   1,使其指向容器里的下一个元素

--iter

iter--

给 iter 减   1,使其指向容器里的前一个元素

iter1 ==iter2

iter1 !=iter2

比较两个迭代器是否相等(或不等)。当两个迭代器指向同一个容器中的同一个元素,或者当它们都指向同一个容器的超出末端的下一位置时,两个迭代器相等

 

vector 和 deque 类型迭代器支持的操作

iter + n

iter - n

在迭代器上加(减)整数值   n,将产生指向容器中前面(后面)第 n个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置

iter1 +=iter2

iter1 -=iter2

这里迭代器加减法的复合赋值运算:将   iter1 加上或减去 iter2 的运算结果赋给 iter1

iter1 -iter2

两个迭代器的减法,其运算结果加上右边的迭代器即得左边的迭代器。用来计算两个迭代器对象的距离.这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置

只适用于 vector   和 deque 容器

>, >=,

<, <=

迭代器的关系操作符。当一个迭代器指向的元素在容器中位于另一个迭代器指向的元素之前,则前一个迭代器小于后一个迭代器。关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置

只适用于 vector   和 deque 容器

关系操作符只适用于 vector 和 deque 容器,这是因为只有这种两种容器为其元素提供快速、随机的访问。它们确保可根据元素位置直接有效地访问指定的容器元素。这两种容器都支持通过元素位置实现的随机访问,因此它们的迭代器可以有效地实现算术和关系运算。

list 容器的迭代器既不支持算术运算(加法或减法),也不支持关系运算(<=, <, >=, >),它只提供前置和后置的自增、自减运算以及相等(不等)运算。

C++ 语言使用一对迭代器标记迭代器范围(iterator range),这两个迭代器分别指向同一个容器中的两个元素或超出末端的下一位置,通常将它们命名为first 和 last,或 beg 和 end,用于标记容器中的一段元素范围。

使用迭代器时,通常可以编写程序使得要求迭代器有效的代码范围相对较短。然后,在该范围内,严格检查每一条语句,判断是否有元素添加或删除,从而相应地调整迭代器的值。

容器定义的类型别名

 

size_type

无符号整型,足以存储此容器类型的最大可能容器长度

iterator

此容器类型的迭代器类型

const_iterator

元素的只读迭代器类型

reverse_iterator

按逆序寻址元素的迭代器

const_reverse_iterator

元素的只读(不能写)逆序迭代器

difference_type

足够存储两个迭代器差值的有符号整型,可为负数

value_type

元素类型

reference

元素的左值类型,是   value_type& 的同义词

const_reference

元素的常量左值类型,等效于 const   value_type&

// iter is the iterator type defined by list<string>

list<string>::iterator iter;

// cnt is the difference_type type defined by vector<int>

vector<int>::difference_type cnt;

容器的begin 和 end 操作

 

c.begin()

返回一个迭代器,它指向容器 c   的第一个元素

c.end()

返回一个迭代器,它指向容器 c   的最后一个元素的下一位置

c.rbegin()

返回一个逆序迭代器,它指向容器 c   的最后一个元素

c.rend()

返回一个逆序迭代器,它指向容器 c   的第一个元素前面的位置

每个操作都有两个不同版本:一个是 const 成员,另一个是非 const 成员。这些操作返回什么类型取决于容器是否为 const。

 

在顺序容器中添加元素的操作

c.push_back(t)

在容器 c 的尾部添加值为 t   的元素。返回 void 类型

c.push_front(t)

在容器 c 的前端添加值为 t 的元素。返回 void 类型.

只适用于 list 和 deque 容器类型.

c.insert(p,t)

在迭代器 p 所指向的元素前面插入值为 t 的新元素。返回指向新添加元素的迭代器

c.insert(p,n,t)

在迭代器 p 所指向的元素前面插入 n   个值为 t 的新元素。返回 void 类型

c.insert(p,b,e)

在迭代器 p 所指向的元素前面插入由迭代器   b 和 e 标记的范围内的元素。返回 void 类型

容器元素都是副本,在容器中添加元素时,系统是将元素值复制到容器里。类似地,使用一段元素初始化新容器时,新容器存放的是原始元素的副本。被复制的原始值与新容器中的元素各不相关,此后,容器内元素值发生变化时,被复制的原值不会受到影响,反之亦然。

任何 insert 或 push 操作都可能导致迭代器失效。当编写循环将元素插入到 vector 或 deque 容器中时,程序必须确保迭代器在每次循环后都得到更新。

不要存储 end 操作返回的迭代器。添加或删除 deque 或 vector 容器内的元素都会导致存储的迭代器失效。为了避免存储 end 迭代器,可以在每次做完插入运算后重新计算 end 迭代器值:

// safer: recalculate end on each trip whenever the loop adds/eraseselements

while (first != v.end()) {

// do some processing

first = v.insert(first, ); // insert new value

++first; // advance first just past the element we added

}

所有的容器类型都支持用关系操作符来实现两个容器的比较。比较的容器必须具有相同的容器类型,而且其元素类型也必须相同。容器的比较是基于容器内元素的比较。如果容器的元素类型不支持某种操作符,则该容器就不能做这种比较运算。

• 如果两个容器具有相同的长度而且所有元素都相等,那么这两个容器就相等;否则,它们就不相等。

• 如果两个容器的长度不相同,但较短的容器中所有元素都等于较长容器中对应的元素,则称较短的容器小于另一个容器。

• 如果两个容器都不是对文的初始子序列,则它们的比较结果取决于所比较的第一个不相等的元素。

 

顺序容器的大小操作

c.size()

返回容器 c 中的元素个数。返回类型为   c::size_type

c.max_size()

返回容器 c 可容纳的最多元素个数,返回类型为 c::size_type

c.empty()

返回标记容器大小是否为 0 的布尔值

c.resize(n)

调整容器 c 的长度大小,使其能容纳 n   个元素,如果 n <c.size(),则删除多出来的元素;否则,添加采用值初始化的新元素

c.resize(n,t)

调整容器 c 的长度大小,使其能容纳 n   个元素。所有新添加的元素值都为 t

容器类型提供 resize 操作来改变容器所包含的元素个数。如果当前的容器长度大于新的长度值,则该容器后部的元素会被删除;如果当前的容器长度小于新的长度值,则系统会在该容器后部添加新元素.

resize 操作可能会使迭代器失效。在 vector 或 deque 容器上做 resize 操作有可能会使其所有的迭代器都失效。对于所有的容器类型,如果 resize 操作压缩了容器,则指向已删除的元素迭代器失效。

 

访问顺序容器内元素的操作

c.back()

返回容器 c 的最后一个元素的引用。如果   c 为空,则该操作未定义

c.front()

返回容器 c 的第一个元素的引用。如果 c   为空,则该操作未定义

c[n]

返回下标为 n 的元素的引用.   如果 n <0 或 n >=   c.size(),则该操作未定义. 只适用于   vector 和 deque 容器

c.at(n)

返回下标为 n 的元素的引用。如果下标越界,则该操作未定义. 只适用于 vector 和 deque 容器

// check that there are elements before dereferencing an iterator

// or calling front or back

if (!ilist.empty()) {

// val and val2 refer to the same element

list<int>::reference val = *ilist.begin();

list<int>::reference val2 = ilist.front();

// last and last2 refer to the same element

list<int>::reference last = *--ilist.end();

list<int>::reference last2 = ilist.back();

 }

使用下标运算的另一个可选方案是 at 成员函数。这个函数的行为和下标运算相似,但是如果给出的下标无效,at 函数将会抛出 out_of_range异常:

vector<string> svec; // empty vector

cout << svec[]; // run-time error: There are no elements

in svec!

cout << svec.at(); // throws out_of_range exception

 

删除顺序容器内元素的操作

c.erase(p)

删除迭代器 p 所指向的元素.   返回一个迭代器,它指向被删除元素后面的元素。如果 p   指向容器内的最后一个元素,则返回的迭代器指向容器的超出末端的下一位置。如果 p 本身就是指向超出末端的下一位置的迭代器,则该函数未定义

c.erase(b,e)

删除迭代器 b 和 e   所标记的范围内所有的元素返回一个迭代器,它指向被删除元素段后面的元素。如果 e   本身就是指向超出末端的下一位置的迭代器,则返回的迭代器也指向容器的超出末端的下一位置

c.clear()

删除容器 c 内的所有元素。返回 void

c.pop_back()

删除容器 c 的最后一个元素。返回   void。如果 c 为空容器,则该函数未定义

c.pop_front()

删除容器 c 的第一个元素。返回 void。如果 c 为空容器,则该函数未定义.只适用于 list 或 deque 容器

*pop_front 和 pop_back 函数的返回值并不是删除的元素值,而是 void。要获取删除的元素值,则必须在删除元素之前调用front 或 back 函数。

寻找一个指定元素的最简单方法是使用标准库的 find 算法。为了使用 find 函数或其他泛型算法,在编程时,必

须将 algorithm 头文件包含进来。find 函数需要一对标记查找范围的迭代器以及一个在该范围内查找的值作参数。查找完成后,该函数返回一个迭代器,它指向具有指定值的第一个元素,或超出末端的下一位置。

顺序容器的赋值操作

c1 = c2

删除容器 c1 的所有元素,然后将 c2   的元素复制给 c1。c1 和c2 的类型(包括容器类型和元素类型)必须相同

c1.swap(c2)

交换内容:调用完该函数后,c1 中存放的是   c2 原来的元素,c2 中存放的则是 c1 原来的元素。c1 和 c2 的类型必须相同。该函数的执行速度通常要比将 c2 复制到 c1 的操作快

c.assign(b,e)

重新设置 c 的元素:将迭代器 b 和 e   标记的范围内所有的元素复制到 c 中。b 和 e 必须不是指向 c   中元素的迭代器。如果在不同(或相同)类型的容器内,元素类型不相同但是相互兼容,则其赋值运算必须使用 assign 函数。

c.assign(n,t)

将容器 c 重新设置为存储 n 个值为 t   的元素

vector 容器的自增长如果 resize 容器以扩充其容量,则必须在容器中添加额外的元素。为了支持快速的随机访问,vector 容器的元素以连续的方式存放——每一个元素都紧挨着前一个元素存储。

vector 类提供了两个成员函数:capacity 和 reserve 使程序员可与 vector 容器内存分配的实现部分交互工作。capacity操作获取在容器需要分配更多的存储空间之前能够存储的元素总数,而 reserve操作则告诉 vector 容器应该预留多少个元素的存储空间。

每当 vector 容器不得不分配新的存储空间时,以加倍当前容量的分配策略实现重新分配

元素是否连续存储还会显著地影响:

• 在容器的中间位置添加或删除元素的代价。

• 执行容器元素的随机访问的代价。

vector 和 deque容器提供了对元素的快速随机访问,但付出的代价是,在容器的任意位置插入或删除元素,比在容器尾部插入和删除的开销更大。list 类型在任何位置都能快速插入和删除,但付出的代价是元素的随机访问开销较大。list 容器不支持随机访问,访问某个元素要求遍历涉及的其他元素。

通常来说,除非找到选择使用其他容器的更好理由,否则vector 容器都是最佳选择。

下面列举了一些选择容器类型的法则:

1. 如果程序要求随机访问元素,则应使用 vector 或 deque 容器。

2. 如果程序必须在容器的中间位置插入或删除元素,则应采用 list 容器。

3. 如果程序不是在容器的中间位置,而是在容器首部或尾部插入或删除元素,则应采用 deque 容器。

4. 如果只需在读取输入时在容器的中间位置插入元素,然后需要随机访问元素,则可考虑在输入时将元素读入到一个 list 容器,接着对此容器重新排序,使其适合顺序访问,然后将排序后的 list 容器复制到一个 vector容器。

如果程序既需要随机访问又必须在容器的中间位置插入或删除元素,那应该怎么办呢?

此时,选择何种容器取决于下面两种操作付出的相对代价:随机访问 list 容器元素的代价,以及在 vector 或 deque 容器中插入/删除元素时复制元素的代价。通常来说,应用中占优势的操作(程序中更多使用的是访问操作还是插入

/删除操作)将决定应该什么类型的容器。

在某些方面,可将 string 类型视为字符容器。除了一些特殊操作,string 类型提供与 vector 容器相同的操作。

与 vector 容器不同的是,它不支持以栈方式操纵容器:在 string 类型中不能使用 front、back 和 pop_back 操作。与 vector 容器的元素一样,string 的字符也是连续存储的。

string 操作

string s;

定义一个新的空 string 对象,命名为   s

string s(cp);

定义一个新的 string 对象,用 cp   所指向的(以空字符null 结束的)C 风格字符串初始化该对象

string s(s2);

定义一个新的 string   对象,并将它初始化为 s2 的副本

is >> s;

从输入流 is   中读取一个以空白字符分隔的字符串,写入 s

os << s;

将 s 写到输出流 os 中

getline(is, s)

从输入流 is 中读取一行字符,写入 s

s1 + s2

把 s1 和 s2 串接起来,产生一个新的   string 对象

s1 += s2

将 s2 拼接在 s1 后面

关系操作符

相等运算(== 和   !=)以及关系运算(<、<=、> 和 >=)都可用于 string 对象的比较,等效于(区分大小写的)字典次序的比较

构造 string 对象的其他方法

string   s(cp, n)

创建一个   string 对象,它被初始化为 cp 所指向数组的前 n 个元素的副本

string   s(s2, pos2)

创建一个   string 对象,它被初始化为一个已存在的 string 对象 s2 中从下标 pos2 开始的字符的副本. 如果 pos2 >   s2.size(),则该操作未定义

string   s(s2, pos2, len2)

创建一个   string 对象,它被初始化为 s2 中从下标 pos2 开始的len2 个字符的副本。如果 pos2 >   s2.size(),则该操作未定义,无论 len2 的值是多少,最多只能复制 s2.size() - pos2 个字符

注意:n、len2   和 pos2 都是 unsigned 值

string 类型支持的许多容器操作在操作时都以迭代器为基础。所有版本的 insert 函数的第一参数都是一个指向插入位置之后的迭代器,而新插入的元素值则由其他参数指定.也提供以下标为基础的操作。

与容器共有的 string 操作

s.insert(p,   t)

在迭代器 p   指向的元素之前插入一个值为 t 的新元素。返回指向新插入元素的迭代器

s.insert(p,   n,t)

在迭代器 p   指向的元素之前插入 n 个值为 t 的新元素。返回 void

s.insert(p,   b,e)

在迭代器 p   指向的元素之前插入迭代器 b 和 e 标记范围内所有的元素。返回 void

s.assign(b,   e)

在迭代器 b 和 e   标记范围内的元素替换 s。对于 string 类型,该操作返回 s;对于容器类型,则返回 void

s.assign(n,   t)

用值为 t 的 n   个副本替换 s。对于 string 类型,该操作返回 s;对于容器类型,则返回 void

s.erase(p)

删除迭代器 p   指向的元素。返回一个迭代器,指向被删除元素后面的元素

s.erase(b,   e)

删除迭代器 b 和   e 标记范围内所有的元素。返回一个迭代器,指向被删除元素段后面的第一个元素

string 类型特有的版本

s.insert(pos,   n, c)

在下标为 pos   的元素之前插入 n 个字符 c

s.insert(pos,   s2)

在下标为 pos   的元素之前插入 string 对象 s2 的副本

s.insert(pos,   s2, pos2, len)

在下标为 pos   的元素之前插入 s2 中从下标 pos2 开始的 len 个字符

s.insert(pos,   cp,len)

在下标为 pos   打元素之前插入 cp 所指向数组的前len 个字符

s.insert(pos,   cp)

在下标为 pos   的元素之前插入 cp 所指向的以空字符结束的字符串副本

s.assign(s2)

用 s2 的副本替换   s

s.assign(s2,   pos2,len)

用 s2 中从下标   pos2 开始的 len 个字符副本替换 s

s.assign(cp,   len)

用 cp   所指向数组的前 len 个字符副本替换 s

s.assign(cp)

用 cp   所指向的以空字符结束的字符串副本替换 s

s.erase(pos,   len)

删除从下标 pos   开始的 len 个字符

除非特殊声明,上述所有操作都返回 s 的引用

子串操作

s.substr(pos,n)

返回一个   string 类型的字符串,它包含 s 中从下标 pos开始的 n 个字符

s.substr(pos)

返回一个   string 类型的字符串,它包含从下标 pos 开始到s 末尾的所有字符

s.substr()

返回 s 的副本

对于 append操作,字符将添加在 string 对象的末尾。而 replace 函数则将这些字符插入到指定位置,从而替换 string 对象中一段已存在的字符。

修改 string 对象的操作(args 在表 9.18 中定义)

s.append(   args)

将 args 串接在   s 后面。返回 s 引用

s.replace(pos, len, args)

删除 s 中从下标 pos 开始的 len 个字符,用 args指定的字符替换之。返回 s 的引用.

在这个版本中,args   不能为 b2,e2

s.replace(b,   e, args)

删除迭代器 b 和 e 标记范围内所有的字符,用 args替换之。返回 s 的引用

在这个版本中,args   不能为 s2,pos2,len2

表 9.18

append 和 replace 操作的参数:args

s2

string   类型的字符串 s2

s2, pos2,   len2

字符串 s2   中从下标 pos2 开始的 len2 个字符

cp

指针 cp   指向的以空字符结束的数组

cp, len2

cp   指向的以空字符结束的数组中前 len2 个字符

n, c

字符 c 的 n   个副本

b2, e2

迭代器 b2 和   e2 标记的范围内所有字符

string 类提供了 6 种查找函数,每种函数以不同形式的 find命名。这些操作全都返回 string::size_type 类型的值,以下标形式标记查找匹配所发生的位置;或者返回一个名为 string::npos 的特殊值,说明查找没有匹配。string 类将 npos 定义为保证大于任何有效下标的值。

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   中查找第一个不属于 args 的字符

s.find_last_not_of(   args)

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

string 类型提供的 find 操作的参数

c, pos

在 s 中,从下标   pos 标记的位置开始,查找字符 c。pos 的默认值为 0

s2, pos

在 s 中,从下标   pos 标记的位置开始,查找 string 对象 s2。pos 的默认值为 0

cp, pos

在 s 中,从下标   pos 标记的位置形参,查找指针 cp 所指向的 C 风格的以空字符结束的字符串。pos 的默认值为 0

cp, pos, n

在 s 中,从下标   pos 标记的位置开始,查找指针 cp 所指向数组的前 n 个字符。pos 和 n 都没有默认值

如果在查找字符串时希望匹配任意指定的字符,则实现起来稍微复杂一点。例如,下面的程序要在 name 中寻找并定位第一个数字:

string numerics("");

string name("r2d2");

string::size_type pos = name.find_first_of(numerics);

cout << "found number at index: " << pos

<< " element is " << name[pos] << endl;

还可以调用 find_first_not_of 函数查找第一个与实参不匹配的位置。例如,如果要在 string 对象中寻找第一个非数字字符,可以如下编写程序:

string numbers("");

string dept("03714p3");

// returns 5, which is the index to the character 'p'

string::size_type pos = dept.find_first_not_of(numbers);

标准库还提供了一组类似的从右向左查找 string 对象的操作。rfind 成员函数用于寻找最后一个——也就是是最右边的——指定子串出现的位置:

string river("Mississippi");

string::size_type first_pos = river.find("is"); // returns 1

string::size_type last_pos = river.rfind("is"); // returns 4

string类型 compare 操作

s.compare(s2)

比较 s 和 s2

s.compare(pos1,   n1, s2)

让 s 中从 pos   下标位置开始的 n1 个字符与 s2 做比较

s.compare(pos1,   n1, s2, pos2, n2)

让 s 中从   pos1 下标位置开始的 n1 个字符与 s2 中从 pos2下标位置开始的 n2 个字符做比较

s.compare(cp)

比较 s 和 cp   所指向的以空字符结束的字符串

s.compare(pos1,   n1, cp)

让 s 中从   pos1 下标位置开始的 n1 个字符与 cp 所指向的字符串做比较

s.compare(pos1,   n1, cp, n2)

让 s 中从   pos1 下标位置开始的 n1 个字符与 cp 所指向的字符串的前 n2 个字符做比较

除了顺序容器,标准库还提供了三种顺序容器适配器:queue、priority_queue 和 stack。适配器(adaptor)是标准库中通用的概念,包括容器适配器、迭代器适配器和函数适配器。本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如,stack(栈)适配器可使任何一种顺序容器以栈的方式工作。

适配器通用的操作和类型

size_type

一种类型,足以存储此适配器类型最大对象的长度

value_type

元素类型

container_type

基础容器的类型,适配器在此容器类型上实现

A a;

创建一个新空适配器,命名为   a

A a(c);

创建一个名为 a   的新适配器,初始化为容器 c 的副本

关系操作符

所有适配器都支持全部关系操作符(两个相同类型的适配器):==、 !=、 <、 <=、 >、>=

使用适配器时,必须包含相关的头文件:

#include <stack> // stack adaptor

#include <queue> // both queue and priority_queue adaptors

默认的 stack 和 queue 都基于 deque 容器实现,而 priority_queue 则在 vector 容器上实现。在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型实参,可覆盖其关联的基础容器类型:

// empty stack implemented on top of vector

stack< string, vector<string> > str_stk;

// str_stk2 is implemented on top of vector and holds a copy of svec

stack<string, vector<string> > str_stk2(svec);

stack 栈可以建立在vector、list 或者 deque 容器之上。而

queue 适配器要求其关联的基础容器必须提供 push_front 运算,因此只能建立在 list 容器上,而不能建立在

vector 容器上。priority_queue 适配器要求提供随机访问功能,因此可建立在vector 或 deque 容器上,但不能建立在 list 容器上。

栈容器适配器支持的操作

s.empty()

如果栈为空,则返回   true,否则返回 stack

s.size()

返回栈中元素的个数

s.pop()

删除栈顶元素的值,但不返回其值

s.top()

返回栈顶元素的值,但不删除该元素

s.push(item)

在栈顶压入新元素

队列和优先级队列支持的操作

q.empty()

如果队列为空,则返回   true,否则返回 false

q.size()

返回队列中元素的个数

q.pop()

删除队首元素,但不返回其值

q.front()

返回队首元素的值,但不删除该元素该操作只适用于队列

q.back()

返回队尾元素的值,但不删除该元素该操作只适用于队列

q.top()

返回具有最高优先级的元素值,但不删除该元素该操作只适用于优先级队列

q.push(item)

对于   queue,在队尾压入一个新元素,对于 priority_quue,在基于优先级的适当位置插入新元素

上一篇:C++ Primer 随笔 Chapter 9 顺序容器


下一篇:Memento 备忘录 快照模式 MD