c++顺序表的实现（C++学习笔记九顺序容器（二） ForFreeDom 博客园）

时间2025-05-05 04:21:37分类IT科技浏览3853

导读：一、插入操作如何影响容器的选择：...

一、插入操作如何影响容器的选择：

1.list 容器表示不连续的内存区域，允许向前和向后逐个遍历元素。在任何位置都可高效地 insert 或 erase 一个元素。插入或删除 list 容器中的一个元素不需要移动任何其他元素。另一方面，list 容器不支持随机访问，访问某个元素要求遍历涉及的其他元素。

2.对于 vector 容器，除了容器尾部外，其他任何位置上的插入（或删除）操作都要求移动被插入（或删除）元素右边所有的元素。

3.deque 容器拥有更加复杂的数据结构。从 deque 队列的两端插入和删除元素都非常快。在容器中间插入或删除付出的代价将更高。deque 容器同时提供了 list 和 vector 的一些性质：

A.与 vector 容器一样，在 deque 容器的中间 insert 或 erase 元素效率比较低。

B.不同于 vector 容器，deque 容器提供高效地在其首部实现 insert 和 erase 的操作，就像在容器尾部的一样。

C.与 vector 容器一样而不同于 list 容器的是， deque 容器支持对所有元素的随机访问。

D.在 deque 容器首部或尾部插入元素不会使任何迭代器失效，而首部或尾部删除元素则只会使指向被删除元素的迭代器失效。在 deque 容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器都失效。

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

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

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

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

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

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

此时，选择何种容器取决于下面两种操作付出的相对代价：随机访问 list 容器元素的代价，以及在 vector 或 deque 容器中插入／删除元素时复制元素的代价。通常来说，应用中占优势的操作（程序中更多使用的是访问操作还是插入／删除操作）将决定应该什么类型的容器。

三、如果无法确定某种应用应该采用哪种容器，则编写代码时尝试只使用 vector 和 lists 容器都提供的操作：使用迭代器，而不是下标，并且避免随机访问元素。这样编写，在必要时，可很方便地将程序从使用 vector 容器修改为使用 list 的容器。

四、再谈字符串：

#include <iostream>

#include <string>

using namespace std;

int main()

{

//---------------构造 string 对象的方法测试-------------------------------------------------------

string s1; // s1 是个空字符串

string s2(5, a); // s2 == "aaaaa",初始化有5个字符a的字符串

string s3(s2); // s3 初始为s2的一份拷贝

string s4("abcde"); //用字符串常量初始化s4

string s5(s4.begin(), s4.begin() + s4.size() / 2); // 有迭代器来初始化s5. 注意并不包含第二个参数中迭代器的字符

//---------------有指针或字符数组构造 string 对象的方法测试--------------------------------

const char *cp = "Hiya"; // null-terminated array

char c_array[] = "World!!!!"; // null-terminated

char no_null[] = {H, i}; // not null-terminated

string s6(cp); // s1 == "Hiya"

string s7(c_array, 5); // s2 == "World";第一个参数代表开始位置,第二个参数代表长度

string s8(c_array + 5, 4); // s3 == "!!!!"

string s9(no_null); // 错误:runtime error: no_null not null-terminated

string s10(no_null, 2); // ok: s5 == "Hi" ;第一个参数代表开始位置,第二个参数代表长度

//---------------用子串做初始化式-------------------------------------------------------------------

s1="Hiya";

string s11(s1, 2); // s6 == "ya";第二个参数代表开始位置. 直到字符串结尾

string s12(s1, 0, 2); // s7 == "Hi";第二个参数代表开始位置. 第二个参数代表长度

string s13(s1, 0, 8); // s8 == "Hiya";第二个参数代表开始位置. 第二个参数代表长度.标准库最多只能复制数目与 string 对象长度相等的字符。

//---------------字符串的插入操作----------------------------------------------------------------------

string str1="abcde";

string str2="fghijkl";

string::iterator sitor=str2.begin();

str2.insert(sitor,8);

cout<<str2<<endl;

cout << "Hello world!" << endl;

return 0;

}

1.子串操作：

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

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

s.substr() 返回 s 的副本

2.string 对象的append及replace操作：

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

s2string 类型的字符串 s2

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

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

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

n, c 字符 c 的 n 个副本

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

3.在查找操作中,如果找不到对应的字符串,则返回 string::npos

4.注意一下string,查找函数的区别,用来查找字符串还是查找字符

s.find( args) 在 s 中查找 args 的第一次出现

s.rfind( args) 在 s 中查找 args 的最后一次出现

s.find_first_of( args) 在 s 中查找 args 的任意字符的第一次出现

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

1.适配器的初始化：所有适配器都定义了两个构造函数：默认构造函数用于创建空对象，而带一个容器参数的构造函数将参数容器的副本作为其基础值。例如，假设 deq 是 deque<int> 类型的容器，则可用 deq 初始化一个新的栈，如下所示：

stack<int> stk(deq); // copies elements from deq into stk 2.覆盖基础容器类型：默认的 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);

3.适配器的关系运算：两个相同类型的适配器可以做相等、不等、小于、大于、小于等于以及等于关系比较，只要基础元素类型支持等于和小于操作符既可。这些关系运算由元素依次比较来实现。第一对不相等的元素将决定两者之间的小于或大于关系。