C++Primer09-2.顺序容器的操作

委员长

操作

顺序容器的增删改查操作。介绍的都是顺序容器特有的操作。

添加元素

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

这些操作会改变容器的大小，因此 array 不支持这些操作。

forward_list 有自己专有版本的 insert 和 emplace。

forward_list 不支持 push_back 和 emplace_back。

vector 和 string 不支持 push_front 和 emplace_front。

操作	说明
c.push_back(t)<br>c.emplace_back(args)	在 c 的尾部创建一个值为 t 或由 args 创建的元素（特征隐式类型转换）。返回 void。
c.push_front(t)<br>c.emplace_front(args)	在 c 的头部创建一个值为 t 或由 args 创建的元素。返回 void。
c.insert(p, t)<br>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, il)	il 是一个花括号包围的元素值列表。将这些给定值插入到迭代器 p 指向的元素之前。返回指向新添加的第一个元素的迭代器；若列表为空，则返回 p

向一个 vector、string 或 deque 插入元素会使所有指向容器的迭代器、引用和指针失效。这个什么意思呢？这个和 Java ArrayList 一边遍历一边遍删除/新增类似。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> ivec = {1, 2, 3, 4, 5, 6};
    // 迭代器失效。
    for (auto beg = ivec.begin(), last = ivec.end(); beg != last;) {
        cout << *beg++ << endl;
        ivec.insert(ivec.begin() + 2, 10);
    }
    return 0;
}

C++ Primer：vector插入元素时迭代器失效问题_北冥有鱼wyh的博客-CSDN博客

insert 操作会触发拷贝构造，而 emplace 操作可以避免这种拷贝。

vector<strConstructor> c;
c.emplace_back("elel"); // 通过传入的参数构造出对象，放入容器中。不会触发拷贝构造
c.push_back("eee"); // 会先构造出一个临时对象，然后在进行拷贝构造放入容器中

emplace 函数的参数根据元素类型而变化，参数必须与元素类型的构造函。

<span style="color:red">注意：emplace 函数在容器中直接构造元素。传递给 emplace 函数的参数必须与元素类型的构造函数相匹配。</span>

访问元素

at 和下标操作只适用于 string、vector、deque 和 array

操作	说明
c.back()	返回 c 中尾元素的引用。若 c 为空，函数行为未定义。
c.front()	返回 c 中首元素的引用。若 c 为空，函数行为未定义。
c[n]	返回 c 中下标未 n 的元素的引用，n 为 无符号整数。若 n>=c.size()，函数行为为未定义
c.at(n)	返回下标为 n 的元素的引用。如果下标越界，则抛出一个 out_of_range 异常

不要对一个空容器调用 front 和 back。

<b> 注意，这些访问元素的方式返回的都是引用</b>

auto &v = c.back(); // 获取尾部元素的引用

删除元素

这些操作会改变容器的大小，因此不适用于 array

forward_list 有特定版本的 erase

forward_list 不支持 pop_back; vector 和 string 不支持 pop_front

操作	说明
c.pop_back()	删除 c 中尾元素。若 c 为空，则函数行为未定义。函数返回 void。
c.pop_front()	删除 c 中首元素。若 c 为空，则函数行为未定义。函数返回 void。
c.erase(p)	删除迭代器 p 所指定的元素，返回一个指向被删元素之后元素的迭代器，若 p 指向尾元素，则返回尾后迭代器。若 p 是尾后迭代器，则函数行为未定义。
c.erase(b, e)	删除迭代器 b 和 e 所指定范围内的元素。返回一个指向最后一个被删元素之后元素的迭代器，若 e 本身就是尾后迭代器，则函数也返回尾后迭代器
c.clear()	删除 c 中的所有元素，返回 void

删除 deque 中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。<span style="color:red">指向 vector 或 string 中删除点之后位置的迭代器、引用和指针都会失效。</span>

如果我们希望删除 vector 中的偶数，并且希望使用迭代器操作，删除一个元素后需要修改迭代器指针。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> ivec = {1, 2, 3, 4, 5, 6};
    // 因为删除了元素，因此尾指针也失效了。
    for (auto beg = ivec.begin(); beg != ivec.end();) {
        if (*beg % 2 == 0) {
            beg = ivec.erase(beg);
        } else {
            beg++;
        }
    }
    cout << ivec.size() << endl;
    return 0;
}

forward_list 操作

操作	说明
lst.before_begin()

改变容器大小

使用 resize 来修改容器的大小。

list<int> st(10,42); // 10 个元素，每个元素值为 42
st.resize(15); // 容量扩容为 15，填充元素 0
st.resize(25, -1); // 容量扩容为 25，填充元素 -1
st.resize(5); // 缩容为 5，会删除尾部多余的元素

失效的迭代器★

<span style="color:orange">向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。一个失效的指针、引用或迭代器将不再表示任何元素。使用失效的指针、引用或迭代器是一种严重的程序设计错误，很可能引起与使用未初始化指针一样的问题。</span>

在向容器添加元素后

• 如果容器是 vector 或 string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
• 对于 deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效.
• 对于 list 和 forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。

当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用会失效，这应该不会令人惊讶。毕竟，这些元素都已经被销毁了。当我们删除一个元素后

• 对于 list 和 forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效
• 对于 deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除 deque 的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
• 对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。

<b>管理好迭代器</b>

当你使用迭代器（或指向容器元素的引用或指针）时，最小化要求迭代器必须保持有效的程序片段是一个好的方法。

由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。尤其是对 vector、string 和 deque。

<b>编写正确的程序</b>

#include <iostream>
#include <vector>
#include <list>
#include <array>

using namespace std;

void test() {
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    auto iter = vi.begin();
    while (iter != vi.end()) {
        if (*iter % 2 == 0) {
            // 复制偶数
            // insert 会返回指向新添加的第一个元素的迭代器
            iter = vi.insert(iter, *iter);
            iter += 2; // 向前移动，跳过当前元素和插入到它之前的元素。
        } else {
            // 删除奇数
            // iter 此时指向我们删除的元素之后的元素
            iter = vi.erase(iter);
        }
    }
    for (auto w: vi) cout << w << " ";
}
int main(){
    test();
    return 0;
}

在调用 insert 和 erase 后都需要更新迭代器，因为两者都会使迭代器失效。

在调用 erase 后，不必递增迭代器，因为 erase 返回的迭代器已经指向序列中下一个元素。调用 insert 后，需要递增迭代器两次。记住，insert 在给定位置之前插入新元素，然后返回指向新插入元素的迭代器。因此，在调用 insert 后，iter 指向新插入元素，位于我们正在处理的元素之前。我们将迭代器递增两次，恰好越过了新添加的元素和正在处理的元素，指向下一个未处理的元素。

<b>不要保存 end 返回的迭代器</b>

当我们添加/删除 vector 或 string 的元素后，或在 deque 中首元素之外任何位置添加/删除元素后，原来 end 返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用 end，而不能在循环之前保存 end 返回的迭代器，一直当作容器末尾使用。通常 C++ 标准库的实现中 end() 操作都很快，部分就是因为这个原因。

<b>一个错误的写法</b>

void error() {
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8};

    auto beg = vi.begin(), last = vi.end();
    // 
    while (beg!=last){ // error exit code 11
        ++beg; //
        beg = vi.insert(beg,42); // 插入新值
        ++beg; //
    }
}

vector增长策略

为了尽可能的减少内存分配的次数，vector 分配内存时会多分配一些空间。与 Java 的 ArrayList 类似，但是在缩容策略上，如果我们调用 vector 缩容（去除不必要的内容空间）的函数，这只是提供一个建议，C++ 不一定真的会缩容内存空间。

shrink_to_fit 只适用于 vector、string 和 deque。

capacity 和 reserve 只适用于 vector 和 string。

操作	说明
c.shrink_to_fit()	请求将 capacity 减少到和 size() 一样大
c.capacity()	不重新分配内存空间的话，c 可以保存的最大元素个数
c.reserve(n)	分配至少能容纳 n 个元素的内存空间

<span style="color:red">reserve 并不改变容器中元素的数量，它仅影响 vector 预先分配多大的内存空间。而且只有当前容量不足时，reserve 调用才会改变 vector 的容量。如果当前容量不足，reserve至少分配与需求一样大的内存空间（可能更大）</span>

<span style="color:orange">我们可以调用 shrink_to_fit 来要求 deque、vector 或 string 退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是，调用 shrink_to_fit 也并不保证一定退回内存空间，编译器不一定会缩容</span>

一般来说扩容的规则是扩容到原先的 2 倍。

string的操作

<span style="color:red">我的建议是，快速过一遍，用到时再查。</span>

除了顺序容器共同的操作之外，string 类型还提供了一些额外的操作。这些操作中的大部分要么是提供 string 类和 C 风格字符数组之间的相互转换，要么是增加了允许我们用下标代替迭代器的版本。

构造string的其他方法

操作	说明
string s(cp, n)	cp 的前 n 个字符构成字符串 s。
string s(s1, pos2)	从 string s1 的下标 pos2 开始拷贝 pos2~末尾的字符。
string s(s2, pos2, len2)	从 string s1 的下标 pos2 开始，拷贝 len2 个字符。

这些构造函数接受一个 string 或一个 const char* 参数，还接受（可选的）指定拷贝多少个字符的参数。当我们传递给它们的是一个 string 时，还可以给定一个下标来指出从哪里开始拷贝。

substr操作

拷贝 string 中的一部分字符。

操作	说明
s.substr(pos, n)	从 pos 开始，拷贝 n 个字符。pos 的默认值为 0，n 的默认值为 s.size() - pos，即拷贝从 pos 开始的所有字符。

修改string的其他方法

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

s.insert(s.size(), 5, '!'); // s 末尾插入 5 个 !
s.erase(s.size()-5, 5); // 删除最后 5 个字符

利用 assign 替换 s 的内容

const char *cp = "Stately, plum Buck";
s.assign(cp, 7); // s == "Stately"
s.insert(s.size(), cp+7); // s = "Stately, plum Buck"

<b>append 和 replace</b>

append 在末尾追加字符。重点是 replace。

#include <iostream>

using namespace std;


void testStr() {
    string str("hello world");
    // 从 0 开始的两个字符被替换为 c
    str.replace(0, 2, "c"); // cllo world
    cout << str << endl;

    // 将 cllo 替换为 hello
    // 找到 cllo 的起始位置，然后把 cllo 4 个字符替换为 hello
    str.replace(str.find("cllo"), 4, "hello");
    cout << str << endl;

    // c++ 未提供 replace all 的功能奥
}

int main() {
    testStr();
    return 0;
}

实现一个 replaceAll 的功能

#include <iostream>

using namespace std;

string &replaceAll(string &str, const string &old, const string &news);

void testStr() {
    string str("hello world");
    replaceAll(str, "l", "kkx");
    cout << str << endl;
}

string &replaceAll(string &str, const string &old, const string &news) {
    // 把 old 都替換為 news
    int index = -1;
    int start = 0;
    while (-1 != (index = str.find(old, start))) {
        str.replace(index, old.size(), news);
        start = index - old.size() + news.size();
    }
    return str;
}

int main() {
    testStr();
    return 0;
}

string搜索操作

string 类提供了 6 个不同的搜索函数，每个函数都有 4 个重载版本，此处只记录个人认为重要的。

操作	说明
s.find(args)	查找 args 第一次出现的位置
s.find(args, start)	以 start 为起点，查找 args 第一次出现的位置，start 为 size_type 类型。
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 中的字符

数值转换

操作	说明
to_string(val)	将 val 变为 string
stoi(s, p, b)	返回 s p~b 字符范围内表示的数值 i 表示 int
stol(s, p, b)	l 表示 long
stoul(s, p, b)	ul 表示 unsigned long
stoll(s, p, b)	ll 表示 long long
stoull(s, p, b)	ull 表示 unsigned long long
stof(s, p)	f 表示 float
stod(s, p)	od 表示 double
stold(s, p)	old 表示 long double

容器适配器

stack、queue、priorty_queue。

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue和 priority_queue。简单来说，适配器就是让 vector 表现的像 stack 一样。例如，stack 适配器接受一个顺序容器（除 array 或 forward_list 外），并使其操作起来像一个 stack 一样。

<span style="color:red">看代码像是用的装饰模式</span>

类型和操作	说明
size_type	一般是无符号 int
value_type	容器中所存储元素的类型
container_type	实现适配器的底层容器类型
A a;	创建一个名为 a 的空适配器
A a(c)	创建一个名为 a 的适配器，并拷贝容器 c 中的元素
关系运算符	==、!=、<、<=、>、>=
a.empty()	无元素返回 true，反之 false
a.size()	a 中元素的个数
swap(a, b)<br>a.swap(b)	交换 a 和 b 的内容，a 和 b 必须有相同类型，包括底层容器类型也必须相同。

定义适配器

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。例如，假定 deq 是一个 deque\<int>，我们可以用 deq 来初始化一个新的 stack

#include <iostream>
#include <deque>
#include <stack>

using namespace std;

void testAdapter() {
    deque<int> dq = {1, 2, 3, 4, 5};
    stack<int> s(dq);
}

int main() {
    testAdapter();
    return 0;
}

也可以通过泛型来指定用何种容器初始化一个新的 stack

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

void testAdapter() {
    // 在 vector 上实现空栈
    stack<int, vector<int>> int_stk;

    int_stk.push(1);
    int_stk.push(2);
    int_stk.push(3);
    int_stk.push(4);
    cout << int_stk.top() << endl; // 4

    // 在 vector 上实现栈，并用 int_stk 中的元素进行初始化
    stack<int, vector<int>> int_stk2(int_stk);
    cout << int_stk2.size() << endl; // 4
}

int main() {
    testAdapter();
    return 0;
}

对于一个给定的适配器，可以使用哪些容器是有限制的。所有适配器都要求容器具有添加和删除元素的能力。因此，适配器不能构造在 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 实现。 stack 适配器定义在 stack 头文件中。

stack<int> initStack;

操作	说明
s.pop()	删除栈顶元素，返回 void
s.push(item)<br>s.emplace(args)	元素入栈，通过拷贝或移动 item 而来，由 args 构造元素，入栈，不发生拷贝构造
s.top()	返回栈顶元素，不会将元素出栈

队列适配器

queue 和 priority_queue适配器定义在 queue 头文件中。

操作	说明
q.pop()	返回 queue 的首元素或 priority_queue 的最高优先级的元素
q.front()	返回首元素
q.back()	返回尾元素，只适用于 queue
q.top()	返回优先级最高的元素，只适用于 priority_queue
q.push(item)<br>q.emplace(args)	在 queue 尾部或 priority_queue 中恰当的位置创建一个元素。值为 item，或者由 args 构造

自定义 priority_queue 的比较器。

• 入队的元素可比较（重载了操作符）
• 自定义比较函数模板★
• 定义友院操作类重载函数

// 自定义比价函数模板
#include <iostream>
#include <queue>

using namespace std;

struct cmp {
    bool operator()(const int &a, const int &b) {
        return a - b;
    }
};

void testAdapter() {
    // 默认大根堆
    // 利用 greater 改成小根堆
    priority_queue<int, vector<int>, greater<int>> heap;
    heap.push(1);
    heap.push(3);
    heap.push(6);
    cout << heap.top() << endl;

    // 自定义比较器改成小根堆
    priority_queue<int, vector<int>, cmp> heap2;
    heap.push(1);
    heap.push(3);
    heap.push(6);
    cout << heap.top() << endl;
}

int main() {
    testAdapter();
    return 0;
}