鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

Tips for C++ Primer Chapter 9 顺序容器

来源:互联网 作者:佚名 时间:2018-02-27 09:51
第9章 顺序容器 顺序容器概述 vector 可变大小数组 deque 双端队列 list 双向链表 forward_list 单向链表(C++11) array 固定大小数组(C++11) string 与vector相似的容器,但专门用于保存字符 PS:C++11的容器比旧版本的快得多,因为新标准下支持“对象移

第9章 顺序容器

顺序容器概述

vector   可变大小数组

deque   双端队列

list   双向链表

forward_list   单向链表(C++11)

array   固定大小数组(C++11)

string   与vector相似的容器,但专门用于保存字符

PS:C++11的容器比旧版本的快得多,因为新标准下支持“对象移动”(第13章)。

 

容器库概览

所有容器类型都提供的操作:

类型别名

iterator   此容器类型的迭代器类型、

const_iterator   可读取元素,但不能修改元素的迭代器类型

size_type   无符号整数类型;足够保存此种容器类型最大可能的容器大小

difference_type   带符号整数类型;保存两个迭代器之间的距离

value_type   元素类型

reference   元素的左值类型;相当于value_type&

const_reference   元素的const左值类型;即const value_type&

构造函数

C c   默认构造函数;构造空容器(对array而言)

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

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

C c{a, b, c...}   列表初始化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.maxsize()   c可保存的最大元素数目

c.empty()   c中未存储元素则返回true

添加/删除元素(array不支持)

注:在不同容器中,这些操作的接口都不同

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

c.emplace(inits)   使用inits构造c中的一个元素

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

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

关系运算符

== !=  所有容器都支持

< <= > >=   无序关联容器不支持

PS:使用关系运算符要求容器类型和元素类型都要相同。

获取迭代器

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

PS:反向迭代器的++操作会得到上一个位置。

 

迭代器

--运算符不适用于forward_list;

迭代器的算数运算(第3章)只能应用于string、vector、deque、array的迭代器;(强调:forward_list、list都不适用;例如“*(c.end()-1)”是不支持的)

若begin与end相等,则范围为空,否则范围内至少包含一个元素;

 

在获取迭代器的函数当中,不以c开头的函数都是被重载过的;(begin、end、rbegin、rend)

当我们对一个非常量对象调用这些函数时,得到的是返回iterator的版本;只有在对一个const对象调用这些函数时,才会得到一个const版本;

可以将普通iterator转换成对应的const_iterator,反之不行。

 

当auto与begin或end混合使用时,获得的迭代器类型依赖于容器类型;以c开头的版本一定获得const_iterator,而不管容器类型是什么。

  auto it1 = c.begin(); //仅当c是const时,it1是const_iterator

  auto it2 = c.cbegin(); //it2是const_iterator

 

容器定义和初始化

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

C c1(c2)   C c1=c2   c1初始化为c2的拷贝;c1和c2必须是相同的容器类型、相同的元素类型;对于array类型,两者还必须有相同的大小

C c{a,b,c...}   C c={a,b,c...}   c初始化为初始化列表中元素的拷贝;列表中元素的类型必须与C的元素类型相容;对于array类型,列表中元素数目必须等于或小于array的大小,遗漏的元素将进行值初始化(第3章)

C c(b,e)   c初始化为迭代器b和e指定范围中的元素的拷贝;范围中元素的类型必须与C的元素类型相容;array不支持

以下,只有顺序容器(不包括array)的构造函数才能接受大小参数:

C seq(n)   seq包含n个元素,这些元素进行了值初始化;此构造函数是explicit的;string不支持、array不支持

C seq(n,t)   seq包含n个值为t的元素;string支持、array不支持

PS:以上,若元素类型是内置类型或者是具有默认构造函数的类类型,可以使用第一种方式;若元素类型没有默认构造函数,只能使用第二种方式。

 

标准库array具有固定大小

与内置数组一样,标准库array的大小也是类型的一部分。

定义或使用一个array时,除了指定元素类型,还需指定容器大小。

  array<string, 10> //类型为:保存10个string的数组

  array<string, 10>::size_type i; //ok

  array<string>::size_type j; //error

 

与其它容器不同,一个默认构造的array是非空的:它包含了与其大小一样多的元素。这些元素都被默认初始化。(就像一个内置数组)

若对array进行列表初始化,初始值的数目必须等于或小于array的大小;若小于array的大小,则靠后的元素会进行值初始化

在以上两种情况下,若元素类型是一个类类型,那么该类必须有一个默认构造函数

 

与内置数组类型不同,array支持对象的拷贝或赋值操作。进行array的拷贝或赋值时,必须保证两个对象的元素类型和元素数目都相同

  array<int,3> a{0,1,2};

  array<int,3> b = a; //ok

  array<double,3> c = a; //error;尽管int转换成double可以接受

 

赋值和swap

c1 = c2; //c1的内容和大小都变为和c2一样

c1 = {a,b,c} //c1的大小为3

 

array不支持assign,也不允许用花括号包围的值列表进行赋值。(事实上,某些编译器支持用初始化列表对array进行赋值)

 

容器赋值运算

c1=c2   c1中的元素替换为c2中元素的拷贝;c1与c2必须是相同类型;赋值后c1的大小与c2的大小相同

c1={a,b,c...}   将c1中元素替换为初始化列表中元素的拷贝;对于array,有的编译器支持此操作(例如gcc 4.9.2 -std=c++11),有的不支持此操作

swap(c1,c2)   c1.swap(c2)   交换c1与c2中的元素;swap通常比从c2向c1拷贝元素快得多

(PS:swap只是交换了两个容器的内部数据结构,元素本身并未交换;除array外,swap不对任何元素进行拷贝、删除或插入操作,因此swap是常数时间的。)

(PS:前一个版本的swap是C++11新增的)

以下,assign操作不适用于关联容器array

seq.assign(b,e)   将seq中的元素替换为迭代器[b,e)范围中的元素;迭代器b和e不能指向seq中的元素

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

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

PS:以上,seq表示一个顺序容器的对象(不包括array)。

 

赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效;

swap操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效。(容器类型为array和string的情况除外)

注解:因为swap操作实际上不移动容器内的元素,除string外,指向容器的迭代器、引用和指针在swap操作后都不会失效,它们仍指向swap操作之前的那些元素。但是在swap操作之后,这些元素已经属于不同的容器了。

注解:对于array,swap操作会真正交换它们的元素,交换的时间与元素数目成正比;在swap操作之后,指针、引用和迭代器绑定的元素保持不变,但元素值已经与另一个array中对应的元素的值进行了交换。

 

使用assign(仅顺序容器,且不包括array)

赋值运算符要求左边和右边的对象具有相同的类型。顺序容器(除array外)还定义了一个名为assign的成员,允许从一个不同但相容的类型赋值,并且可以从容器的一个子序列赋值

  list<string> names;

  vector<const char*> oldstyle;

  names = oldstyle; //错误;容器类型不匹配

  names.assign(oldstyle.cbegin(), oldstyle.cend()); //ok;const char*可转换为string

  names.assign(oldstyle.begin(), oldstyle.end()); //ok;char*同样可转换为string

PS:由于其旧元素被替换,因此传递给assign的迭代器不能指向调用assign的容器。

 

顺序容器特有操作

向顺序容器添加元素(非array)

c.push_back(t)   c.emplace_back(args)   在c的尾部创建一个值为t或由args创建的元素;返回void

c.push_front(t)   c.emplace_front(args)   在c的头部创建一个值为t或由args创建的元素;返回void

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中的元素;返回指向新添加的第一个元素的迭代器;若范围为空则返回p

c.insert(p,li)   li是一个花括号包围的元素值列表;将这些给定值插入到迭代器p指向的元素之前;返回指向新添加的第一个元素的迭代器;若列表为空则返回p

forward_list有自己专有版本的insert和emplace(后面讨论)

forward_list不支持push_back和emplace_back

vector和string不支持push_front和emplace_front

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

 

使用emplace操作

C++11引入了三个新成员:emplace_front、emplace、emplace_back;这些操作构造而不是拷贝元素;

这些操作分别对应:push_front、insert、push_back。

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

 

访问元素

每个顺序容器都有front成员函数,除forward_list之外所有顺序容器都有一个back成员函数。

c.front()   返回c的首元素的引用;若c为空,则函数行为未定义

c.back()   返回c的尾元素的引用;若c为空,则函数行为未定义

*c.begin()   通过解引用begin返回的迭代器来获取首元素的引用

*(c.end()-1)   解引用尾元素位置对应的迭代器来获取尾元素的引用(注意:不适用于forward_list和list,因为它们不支持迭代器的算数运算)

auto tail = c.end();

*(--tail)   解引用尾元素位置对应的迭代器来获取尾元素的引用(注意:不适用于forward_list,它的迭代器不支持--运算;可以用于list或其它顺序容器)

c[n]   返回c中下标为n的元素的引用;n是无符号整数,若n>=c.size()则函数行为未定义;(只适用于string、vector、deque、array)

c.at(n)   返回c中下标为n的元素的引用;若下标越界,则抛出out_of_range异常;(只适用于string、vector、deque、array)

PS:在调用front或back之前,要确保c非空;在使用下标操作或at操作之前,要确保c非空。

 

例子:

vector<int> c{1,2,3};
if(!c.empty()) //这里只是强调一下使用front或back之前需要确保容器非空的必要性
{
    c.front() = 4; //c[0]修改为4
    auto v1 = c.back(); //v1值与c[2]值相等,都为3
    v1 = 6; //v1值修改为6,c[2]值不变
    auto &v2 = c.back();
    v2 = 6; //c[2]值修改为6,v2是c[2]的引用
}

 

删除元素(非array)

c.pop_back()   删除c中尾元素;若c为空,则函数行为未定义;返回void

c.pop_front()   删除c中首元素;若c为空,则函数行为未定义;返回void

c.erase(p)   删除迭代器p所指的元素;返回一个指向被删元素之后元素的迭代器,若p指向尾元素,则返回尾后迭代器;若p是尾后迭代器,则函数未定义

c.earse(b,e)   删除迭代器[b,e)所指定范围内的元素;返回一个指向最后一个被删元素之后元素的迭代器;若e本身就是尾后迭代器,则返回尾后迭代器

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

forward_list有其特殊版本的erase(之后讨论)

forward_list不支持pop_back

vector和string不支持pop_front

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

PS:用于删除元素的成员函数不检查其参数,程序员必须确保要删除的元素是存在的。

 

特殊的forward_list操作

在forward_list中插入和删除操作

lst.before_begin()   lst.cbefore_begin()   返回指向链表首元素之前不存在的元素的迭代器;此迭代器不能解引用;第二个版本返回const_iterator

以下函数都是在迭代器p之后的位置插入元素,返回一个指向最后一个插入元素的迭代器,若范围[b,e)为空则返回p;若p为尾后迭代器,则函数行为未定义。

lst.insert_after(p,t)   t是一个对象

lst.insert_after(p,n,t)    n是数量,t是一个对象

lst.insert_after(p,b,e)    b和e是表示范围的一对迭代器(b和e不能指向lst内)

lst.insert_after(p,li)   li是一个花括号列表

emplace_after(p,args)   使用args在p指定的位置之后创建一个元素;返回一个指向这个新元素的迭代器;若p为尾后迭代器,则函数行为未定义

lst.erase_after(p)   删除p指向的位置之后的元素;返回一个指向被删元素之后元素的迭代器,若不存在这样的元素,则返回尾后迭代器;若p指向lst的尾元素或是一个尾后迭代器,则函数行为未定义

lst.erase_after(b,e)   删除[b,e)范围的元素;返回一个指向被删元素之后元素的迭代器

 

当在forward_list中添加或删除元素时, 必须关注两个迭代器:一个指向我们当前要处理的元素,另一个指向其前驱

例子:以下程序的作用是删除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_after(prev);
    }
    else //跳过偶数,curr和prev都向后挪一位
    {
        prev = curr;
        ++curr;
    }
}

 

例子:以下函数接受一个forward_list<string>和两个string,在链表fl中查找s1,并将s2插入到s1之后的位置;若s1不在链表中,则将s2插入到链表末尾

void insert(forward_list<string> &fl, string &s1, string &s2)
{
    auto pre = fl.before_begin();
    auto cur = fl.begin();
    while(cur!=fl.end()) //若fl为空链表(begin() == end()),循环一次也不会执行
    {
        if(*cur == s1)
        {
            fl.insert_after(cur, s2);
            return;
        }
        pre = cur;
        ++cur;
    }

    fl.insert_after(pre, s2); //若s1不存在链表中(包括fl为空链表的情况),这一语句将被执行
    return;
}

 

改变容器大小

list<int> lst(10,1); //10个int,每个值都是1

lst.resize(15); //将5个值为0的元素添加到lst末尾

lst.resize(25,-1); //将10个值为-1的元素添加到lst末尾

lst.resize(5); //从lst末尾删除20个元素

PS:resize操作不适用于array;对vector、string或deque进行resize可能会导致迭代器、指针和引用失效(对list、forward_list则不会)。

 

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

在向容器添加元素后:

(1)如果容器是vector、string,且存储空间被重新分配,则指向容器的迭代器、指针和引用都会失效;如果存储空间未重新分配,则指向插入位置之前的元素的迭代器、指针和引用仍然有效,但指向插入位置之后元素的迭代器、指针和引用将会失效

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

(3)对于list、forward_list,指向容器的迭代器(包括尾后迭代器和首前迭代器)、指针和引用都仍然有效

 

在向容器删除元素后:

显然指向被删除元素的迭代器、指针和引用会失效

(1)对于vector、string,指向被删除元素之前的迭代器、指针和引用仍有效;特别地,尾后迭代器失效

(2)对于deque,如果在首尾之外的任何位置删除元素,那么所有元素迭代器、指针和引用都会失效;如果删除尾元素,则尾后迭代器失效,但其它迭代器、指针、引用都不受影响;如果删除首元素,(除被删元素外)迭代器、指针和引用都不受影响

(3)对于list、forward_list,指向容器其它位置的迭代器、指针、引用都仍然有效

 

因为容器的添加或删除操作可能会使迭代器失效,因此建议在每次改变容器的操作时候都正确地重新定位迭代器

 

vector对象是如何增长的

管理容量的成员函数

c.shrink_to_fit()   将capacity减少为与size相同大小(只适用于vector、string、deque)

c.capacity()   不重新分配内存空的话,c可以保存多少元素(只适用于vector、string)

c.reserve(n)   分配至少能容纳n个元素的内存空间(只适用于vector、string)

 

reserve并不改变容器中元素的数量,它仅影响vector预先分配多大的内存空间;

仅当需要的内存空间超过当前容量时,reserve调用才会改变vector的容量;

若需求大小大于当前容量,reserve至少分配与需求一样大的内存空间(可能更大,依赖于标准库具体实现);

若需求小于或等于当前容量,reserve什么也不做,特别地,当需求大小小于当前容量时,容器不会退回内存空间。

 

之前讨论过resize操作,它只改变容器中元素的数目,而不是容器的容量,同样地使用resize也不会减少容器预留的内存空间。

 

C++11中可以调用shrink_to_fit来退回不需要的内存空间,但是,标准库具体实现时可能会忽略此请求,也就是说调用shrink_to_fit并不保证一定退回内存空间。

 

PS:vector每次需要重新分配内存空间时,将当前容量翻倍。

 

额外的string操作

构造string的其它方法

以下n、len2、pos2都是无符号值。

string s(cp,n)   s是cp指向的数组中的前n个字符的拷贝;此数组至少应包含n个字符(PS:形参cp的类型是const char*)

string s(s2,pos2)   s是string s2从下标pos2开始的字符的拷贝;若pos2>s2.size(),则构造函数的行为未定义(抛出out_of_range异常)

string s(s2,pos2,len2)   s是string s2从下标pos2开始len2个字符的拷贝;若pos2>s2.size(),则构造函数的行为未定义(抛出out_of_range异常);不管len2值是多少,构造函数至多拷贝s2.size()-pos2个字符

 

substr操作

s.substr(pos,n)   返回string,包含s中从pos开始的n个字符的拷贝;pos默认值是0;n的默认值是s.size()-pos;若pos超出范围,抛出out_of_range异常;不管n值多大,最多拷贝至s的末尾

 

修改string的其它方法

s.insert(pos,args)   在pos之前插入args指定的字符;pos可以是一个下标或一个迭代器;接受下标的版本返回一个指向s的引用;接受迭代器的版本返回指向第一个插入字符的迭代器

s.erase(pos,len)   删除从位置pos开始的len个字符;若len被省略,则删除从pos开始直至s末尾的所有字符;返回一个指向s的引用

s.assign(args)    将s中的字符替换为args指定的字符;返回一个指向s的引用

s.append(args)   将args指定的字符追加到s;返回一个指向s的引用

s.replace(range,args)   删除s中range指定范围内的字符,替换为args指定的字符;range一个下标和一个长度,或者是一对指向s的迭代器;返回一个指向s的引用

append assign replace replace insert insert args可以是 备注
(args) (args) (pos,len,args) (b,e,args) (pos,args) (iter,args)   pos是下标,b、e、iter是迭代器
1 1 1 1 1 0 str 字符串str,str不能与s相同
1 1 1 0 1 0 str,pos,len str中从pos开始最多len个字符
1 1 1 1 1 0 cp,len 从cp指向的字符数组的前(最多)len个字符
1 1 1 1 0 0 cp cp指向的以空字符结尾的字符数组
1 1 1 1 1 1 n,c n个字符c
1 1 0 1 0 1 b2,e2 迭代器不能指向s
1 1 0 1 0 1 初始化列表 花括号包围的、以逗号分隔的字符列表

 

 

 

 

 

 

 

 

 

string搜素操作

搜索操作返回指定字符出现的下标,如果未找到则返回string::npos。

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中的字符

args是以下形式之一:

c,pos   从s中位置pos开始查找字符c;pos默认为0

s2,pos   从s中位置pos开始查找字符串s2;pos默认为0

cp,pos   从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串;pos默认为0

cp,pos,n   从s中位置pos开始查找指针cp指向的数组的前n个字符;pos和n无默认值

 

compare函数

(略)

 

数值转换

(略)

 

容器适配器

标准库定义了三个顺序容器适配器:stack、queue、priority_queue。

所有容器适配器都支持的操作

size_type   一种类型,无符号整数

value_type   元素类型

container_type   实现适配器的底层容器类型

A a   创建名为a的空适配器

A a(c)   创建名为a的适配器,带有容器c的一个拷贝

关系运算符   ==、!=、<、<=、>、>=   返回底层容器的比较结果

a.empty()

a.size()

swap(a,b)   a.swap(b)   a和b必须有相同的类型,包括底层容器类型也必须相同

 

在创建一个适配器时,第一个类型参数指定元素类型;将一个命名的顺序容器作为第二个类型参数(可选)来重载默认容器类型。

例如:在vector上实现元素类型是string的栈

  stack<string, vector<string>> str_stk;

 

构造适配器时选择底层容器的限制

所有适配器都要求容器具有添加和删除元素的能力,因此适配器不能构造在array之上;

所有适配器都要求访问尾元素的能力,因此不能用forward_list来构造适配器;

stack只要求push_back、pop_back、back操作,因此可以使用除array、forward_list之外的任何容器类型来构造stack;

queue要求back、push_back、front、push_front操作,因此可以构造于list、deque之上,但不能基于vector构造;

priority_queue除了front、push_back、pop_back以及随机访问能力,因此可以构造于vector、deque之上,但不能基于list构造

 

栈适配器

栈默认基于deque实现,也可在list或vector上实现。

s.pop

s.push(item)   s.emplace(args)   创建一个新元素压入栈顶,该元素通过拷贝或移动item而来,或者由args指定的参数构造

s.top()

 

队列适配器

queue默认基于deque实现,也可用list、vector实现。

priority_queue默认基于vector实现,也可用deque实现。

q.pop()

q.front()   q.back()   只适用于queue

q.top()   返回最高优先级元素;只适用于priority_queue

q.push(item)   q.emplace(args)   在queue末尾或priority_queue中恰当的位置创建一个元素,其值为item,或者由args指定的参数构造

PS:默认情况下,标准库在元素类型上使用<运算符来确定相对优先级,也可重载此默认设置。

 

网友评论
<