顺序器皿 C++

顺序容器 C++

9.1 顺序容器定义

    将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素，这就是顺序容器。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。

顺序容器

vector            支持快速随机访问

list                 支持快速插入删除

deque             双端队列

顺序容器适配器

stack              先进后出(LIFO)栈

queue             先进先出(FIFO)队列

priority_queue 有优先级管理的队列

 

    所有容器都是类模板，为了使程序更清晰、简短，容器类型最常用的构造函数是默认 构造函数。在大多数的程序中，使用默认构造函数能达到最佳 运行时性能，并且使容器更容易使用。

    容器内元素一般满足两个条件：1.元素类型需支持赋值操作 2. 元素类型必须可以复制。因为IO库不支持赋值或复制，所以不能创建IO类型的对象

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

vector<vector<string> > lines; // ok: space required between close

vector<vector<string>> lines; // error: >> treated as shift operator

 

除了默认构造函数，容器类型还提供其他的构造函数

C<T> c;

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

C c(c2);

 

9.2 迭代器和迭代器范围

常用的迭代器运算

 

vector和 deque 容器的迭代器提供额外的运算

 

9.3 顺序容器操作

begin和end成员

c.begin() 返回一个迭代器，它指向容器 c 的第一个元素

c.end()   返回一个迭代器，它指向容器 c 的最后一个元素的下一位置

c.rbegin() 返回一个逆序迭代器，它指向容器 c 的最后一个元素

c.rend()  返回一个逆序迭代器，它指向容器 c 的第一个元素前面的位置

 

在顺序容器中添加元素

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

 

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 类型

       在 vector 容器中添加元素可能会导 致整个容器的重新加载，这样的话，该容器涉及的所有迭代器都会失效。

关系运算符

        容器的比较是基于容器内元素的比较。容器的比较使用了元素类型定义的同 一个关系操作符：两个容器做 != 比较使用了其元素类型定义的 != 操作符。如 果容器的元素类型不支持某种操作符，则该容器就不能做这种比较运算

 

容器大小的操作

 

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

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

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

 

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()

 

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中元素的迭代器

c.assign(n,t)

由于 assign 操作首先删除容器中原来存储的所有元素，因此， 传递给 assign 函数的迭代器不能指向调用该函数的容器内的 元素

       带有一对迭代器参数的 assign 操作允许我们将一个容器的元 素赋给另一个不同类型的容器，但是这两个不同类型的需要能够相互转换，否则运行出错

 

9.4 vector容器的自增长

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

       size 指容器当前拥有的元素个数；而 capacity 则指容 器在必须分配新存储空间之前可以存储的元素总数。每当 vector 容器不得不分配新的存储空间时，以加倍当前容量的分配策 略实现重新分配。

       vector 的每种实现都可*地选择自己的内存分配策略。然 而，它们都必须提供 vector 和 capacity 函数，而且必须是 到必要时才分配新的内存空间。分配多少内存取决于其实现方 式。不同的库采用不同的策略实现。

 

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 s(cp, n)

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

string s(s2, pos2)

创建一个 string 对象，它被初始化为一个已存在的 string 对象 s2 中从下标 pos2 开始的字符的副本

string s(s2, pos2, len2)

 

修改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)

 

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)

 

s.substr(pos, n)

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

s.substr(pos)

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

s.substr()

返回 s 的副本

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

append和replace操作的参数：args

s2

string 类型的字符串 s2

s2,pos2, len2

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

cp

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

cp,len2

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

n, c

字符 c 的 n 个副本

b2,e2

 

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.compare(s2)

比较 s 和 s2s.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)

 

9.6 容器适配器

size_type

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

value_type

元素类型

container_type

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

A a;

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

A a(c);

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

关系操作符

 

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)

 

小结

       在容器中添加或删除元素可能会使已存在的迭代器失效。当混合使用迭代器 操作和容器操作时，必须时刻留意给定的容器操作是否会使迭代器失效。许多使 一个迭代器失效的操作，例如 insert 或 erase，将返回一个新的迭代器，让程 序员保留容器中的一个位置。 使用改变容器长度的容器操作的循环必须非常小心 其迭代器的使用

已知有如下 string 对象：

string line1 = "We were her pride of 10 shenamed us:";

string line2 = "Benjamin, Phoenix, theProdigal"string 

line3 = "and perspicacious pacificSuzanne";

string sentence = line1 + ' ' + line2 + ' ' +line3;

编写程序计算 sentence 中有多少个单词，并指出其中最长和最短的单词。如果有多个最长或最短的单词，则将它们全部输出

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(void)
{
    string line1 = "We were her pride of 10 she named us:";
    string line2 = "Benjamin Phoenix, the Prodigal";
    string line3 = "and perspicacious pacific Suzanne";
    string sentence = line1 + ' ' + line2 + ' ' + line3;
    string separators = " \n\t:,\r\f";

    string::size_type maxLen, minLen, wordLen, cnt = 0;
    string word;
    string::size_type startPos = 0, endPos = 0;
    vector<string> longstWord, shortstWord;

    while((startPos = sentence.find_first_not_of(separators, endPos)) != string::npos)
    {
        cnt++;
        endPos = sentence.find_first_of(separators, startPos);

        if(endPos == string::npos)
            wordLen = sentence.size() - startPos;
        else
            wordLen = endPos - startPos;

        word.assign(sentence.begin() + startPos, sentence.begin() +startPos + wordLen);
        if(cnt == 1)
        {
            maxLen = minLen = word.size();
            longstWord.push_back(word);
            shortstWord.push_back(word);
        }
        else
        {
            if(word.size() > maxLen)
            {
                maxLen = word.size();
                longstWord.clear();
                longstWord.push_back(word);
            }
            else if(word.size() == maxLen)
                longstWord.push_back(word);

            if(word.size() < minLen)
            {
                minLen = word.size();
                shortstWord.clear();
                shortstWord.push_back(word);
            }
            else if(word.size() == minLen)
                shortstWord.push_back(word);
        }
    }

    cout<<"word numbers: "<<cnt<<endl;
    vector<string>::iterator iter;

    cout<<"longst word:"<<endl;
    for(iter = longstWord.begin(); iter != longstWord.end(); iter++)
        cout<<*iter<<endl;
    cout<<endl;

    cout<<"shortst word:"<<endl;
    for(iter = shortstWord.begin(); iter != shortstWord.end(); iter++)
        cout<<*iter<<endl;

    return 0;
}

参考资料：

1、《C++ Primer 中文版》 第9章 顺序容器