c++ 顺序容器

顺序容器

所有容器类都共享公共的接口，不同容器按不同方式对其进行扩展。每种容器都提供了不同的性能和功能的权衡。

顺序容器为程序员提供了控制元素存储和访问顺序的能力。顺序不依赖元素的值，与元素加入容器时的位置相对应。有序和无序关联容器，则根据关键字的值来存储元素。

vector和string将元素保存在连续内存空间中，通过元素下标计算其地址非常快，但在中间位置添加和删除元素时，要移动后面所有的元素。

list和forward_list不支持元素的随机访问，访问某个元素只能遍历整个容器。但是在任何位置添加和删除都很快速。容器的额外内存开销较大。

deque 支持快速的随机访问，其在中间位置添加或删除元素的代价很高，但是在两端添加和删除元素与list和forward_list速度相当。

array 相较于内置数组更安全、更容易使用。大小是固定的，所以不支持添加和删除元素。

forward_list为了更好的性能，舍弃了 size 操作。对于其他容器而言，size保证是一个快速的常量时间的操作。

容器类概述

顺序容器几乎可以保存任意类型的元素，容器的元素类型可以是另一个容器。

vector<vector<string>> ss;
vector<vector<string> > ss; // 较旧的编译器，需要在两个尖括号之间键入空格

顺序容器构造函数的一个版本接收容器大小参数，它使用元素类型的默认构造函数。对于没有默认构造函数的类，可以定义一个保存这种类型对象的容器。

class NoDefault {
public:
	NoDefault(int ival){}
};

vector<NoDefault> v1(10); // 没有合适的默认构造函数可用
vector<NoDefault> v2(10, 0); // 隐式类类型转换
vector<NoDefault> v3(10, NoDefault(1)); // 当构造函数是explicit时

容器操作

迭代器

一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置。迭代器用 != 比较，无法使用 < 比较。

[begin, end)  //自begin开始，end之前结束

带r的版本返回反向迭代器，带c开头的版本返回const迭代器。不需要写访问时，应使用 cbegin 和 cend。

list<string> a = { "Milton", "Shakespeare", "Austen" };
auto it1 = a.begin(); // list<string>::iterator
auto it2 = a.rbegin(); // list<string>::reverse_iterator
auto it3 = a.cbegin(); // list<string>::const_iterator
auto it4 = a.crbegin(); // list<string>::const_reverse_iterator

以c开头的函数都是被重载过的。当const对象调用时，会得到const版本。

vector<int> v1;
const vector<int> v2;
auto it1 = v1.begin(); // vector<int>::iterator
auto it2 = v2.begin(); // vector<int>::const_iterator

容器定义和初始化

list<string> authors = { "Milton", "Shakespeare", "Austen" };
vector<const char*> articles = { "a", "an", "the" };
list<string> list2(authors); // 正确，类型匹配
// deque<string> authList(authors); // 错误，容器类型不匹配
deque<string> authList2(authors.begin(), authors.end()); // 正确，使用迭代器不要求容器类型
// vector<string> words(articles); // 错误，容器类型必须完全匹配
vector<string> words2(articles.begin(), articles.end()); // 正确，使用迭代器不要求容器类型
std::forward_list<string> word3(articles.begin(), articles.end()); // 正确，使用迭代器不要求容器类型

除array之外的容器类型，使用初始化列表得容器大小与初始值得元素一样。除array之外的容器外，容器有另一个构造函数，接受一个容器大小和一个(可选的)元素初始值，若不提供元素初始值则会创建一个值初始化器。

vector<int> ivec(10, -1); // 10个元素，都初始化为-1
list<string> svec(10, "hi"); // 10个元素，都初始化为hi
forward_list<int> ivec2(10); // 10个元素，都初始化为0
deque<string> svec2(10); // 10个元素，都初始化为空字符串

只有当元素类型是内置类型或者是具有默认构造函数的类类型时，才可以只提供容器大小参数。如果元素类型没有默认构造函数必须指定一个显式的元素初始值。 顺序容器构造函数接受大小参数，关联容器并不支持，

标准库array

定义：

array<int, 42>; // 类型：保存42个int的数组
array<string, 10>; // 类型：保存10个string的数组

使用时必须同时指定元素类型和大小：

array<int, 42>::size_type i; // 数组类型包括元素类型和大小
// array<int>::size_type j; // 错误：array<int>不是一个类型

大小是array类型的一部分，array大小是固定的。array不支持容器构造函数。

array<int, 10> ia1; // 10个默认初始化的int
array<int, 10> ia2 = { 0,1,2,3,4,5,6,7,8,9}; // 列表初始化
array<int, 10> ia3 = { 42 }; // ia3[0]为42，剩余元素为0 

array与内置数组类型的区别：array可以进行拷贝或对象赋值操作

int digs[10] = { 0,1,2,3,4,5,6,7,8,9 };
// int cpy[10] = digs; // 错误：内置数组不支持拷贝或赋值

array<int, 10> digits = { 0,1,2,3,4,5,6,7,8,9 };
array<int, 10> copy = digits; // 只要数组类型匹配即合法,大小也是类型的一部分

赋值和swap

array<int, 10> a1 = { 0,1,2,3,4,5,6,7,8,9 };
array<int, 10> a2 = { 0 };
a1 = a2;
a2 = { 0 }; // 赋值号左右两边的运算对象应为相同类型。 此处应是进行了隐式转换

list<string> names;
vector<const char*> oldstyle;
//name = oldstyle;//类型不匹配
// assign会替代就元素，故迭代器不能指向names
names.assign(oldstyle.cbegin(), oldstyle.cend());

swap操作在对除array类型的容器时会很快，swap只交换了容器内部数据结构，运行时间为常数时间。array类型会真正的交换元素。

容器有成员函数版本的swap，也提供非成员版本的swap。使用非成员版本的swap在泛型编程中很重要。

vector<string> svec1(10);
vector<string> svec2(24);
std::swap(svec1, svec2); 

大小操作

容器类型都支持相等运算符(== 和 !=); 除了无序关联容器外的所有容器都支持关系运算符(>, >=, <, <=)。关系运算符左右两边的运算对象必须是相同类型的容器，即相同类型元素。

比较方式同string类似：

1、如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等;否则两个容器不等。
2、如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
3、如果两个容器都不是另一个容器的前缀子序列,则它们的比较结果取决于第一个不相等的元素的比较结果。

vector<int>v1 = { 1,3,5,7,9,12 };
vector<int>v2 = { 1,3,9 };
vector<int>v3 = { 1,3,5,7 };
vector<int>v4 = { 1,3,5,7,9,12 };
bool a = v1 < v2; // true;v1和 v2 在元素[2]处不同:v1[2]小于等于v2[2]
bool b = v1 < v3; // false;所有元素都相等,但v3 中元素数目更少
bool c = v1 == v4; // true;每个元素都相等,且 vl和 v4 大小相同
bool d = v1 == v2; // false;v2 元素数目比 v1 少

新增内容

访问内容

删除内容

特殊的forward_list操作

改变容器大小

array不支持resize。若当前大于所要求的大小，后部元素会被删除；小于时，会添加新元素到容器后部。

list<int> ilist(10, 42); // 10个int: 每个的值都是42
ilist.resize(15); // 将5个值为0的元素添加到末尾
ilist.resize(25, -1); // 将10个-1添加后面
ilist.resize(5);//删除末尾20个元素

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

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

删除元素后，指向被删除元素的迭代器、指针和引用会失效，因为已经销毁了：1、list和forward_list指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。2、对于deque，若在首尾之外的任何位置删除元素，那么指针被删除元素外的其他元素迭代器、引用或指针也会失效。若删除deque尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。3、对于vector和string，指向被删元素之前的迭代器、引用和指针仍有效，尾后迭代器总是会失效。

void test_vector() {
    std::cout << "\n=== Testing std::vector ===\n";
    std::vector<int> vec = { 1, 2, 3, 4, 5 };
    auto it = vec.begin() + 2;  // 指向 vec[2] (3)
    int& ref = vec[2];          // 引用 vec[2] (3)
    int* ptr = &vec[2];         // 指针指向 vec[2] (3)

    std::cout << "Before adding elements: " << *it << ", " << ref << ", " << *ptr << '\n';

    // 添加元素,可能重新分配
    vec.push_back(6);
    vec.push_back(7);

    std::cout << "After adding elements: ";
    try {
        std::cout << *it << ", " << ref << ", " << *ptr << '\n'; // 可能崩溃或无效
    }
    catch (...) {
        std::cout << "Invalidated.\n";
    }
    auto it2 = vec.end();
    // 删除元素
    vec.erase(vec.begin() + 2); // 删除第 3 个元素 (3)
    std::cout << "After deleting element: ";
    try {
        std::cout << *it2 << '\n'; // 尾后迭代器
    }
    catch (...) {
        std::cout << "Invalidated.\n";
    }
}

catch (...) 为什么无效？

catch (...) 可以捕获异常（例如 std::exception），例如：

• std::exception 是所有标准库异常的基类。
• 常见的派生类有：
  • std::out_of_range
  • std::invalid_argument
  • std::runtime_error
  • std::logic_error

但：

• 迭代器或指针失效不是异常：它是未定义行为，没有标准库的机制抛出异常。
• 对无效指针解引用的行为不会自动被 try-catch 捕获。它直接引发运行时错误，例如：
  • 访问未分配内存。
  • 访问越界地址。
  • 指针解引用后访问无效数据。

这些问题不会产生异常，而是直接导致程序崩溃。catch (...) 只能捕获通过 C++ 的 throw 抛出的异常，主要用于捕获标准异常、用户定义异常或非标准异常（如 int 类型）。它无法捕获未定义行为或硬件异常，这类问题需要通过代码逻辑和调试工具来防范和解决。

管理迭代器

在添加/删除 vector、string和deque元素时需考虑上述讨论的失效问题。在循环中，需持续更新迭代器、引用或指针。此代码删除偶数元素，复制奇数元素。insert和erase后需要更新迭代器，否则迭代器会失效。

vector<int> vi = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto iter = vi.begin(); // 要改变vi,故不使用cbegin
while (iter != vi.end())
{
    if (*iter % 2)
    {
        iter = vi.insert(iter, *iter); // 复制当前元素
        iter += 2; // 跳过当前元素以及插入到它之前的元素
        iter++; // 会死循环，因为在前面插入的,会停留在第一个奇数
    }
    else {
        iter = vi.erase(iter); // 删除偶数元素
        // 不应向前移动迭代器，iter指向我们删除的元素之后的元素
    }
}

forward_list版本

forward_list<int> vi = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto cur = vi.begin(), prv = vi.before_begin(); // 要改变vi,故不使用cbegin
while (cur != vi.end())
{
    if (*cur % 2)
    {
        cur = vi.insert_after(prv, *cur); // 复制当前元素
        advance(cur, 2);
        advance(prv, 2);
    }
    else {
        cur = vi.erase_after(prv); 
    }
}

list版本

list<int> vi = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto cur = vi.begin();
while (cur != vi.end())
{
    if (*cur % 2)
    {
        cur = vi.insert(cur, *cur);
        advance(cur, 2);
    }
    else {
        cur = vi.erase(cur);
    }
}

当添加/删除 vector、string后，或在deque首元素之外任何位置添加/删除元素后，end返回的迭代器总会失效。不要保存end返回的迭代器。

 // 运行会报错，end已失效
 vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 auto begin = v.begin(), end = v.end(); // 保存尾迭代器的值是一个坏主意
 while (begin != end) // 正确做法：v.end()
 {
     // 插入新值，对begin重新复制
     ++begin; // 在之后插入元素
     begin = v.insert(begin, 42); // 插入新值
     ++begin; // 跳过新增的元素
 }

vector扩容

扩容特点：1、新增元素：vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；2、对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了 ; 3、初始时刻vector的capacity为0，插入第一个元素后capacity增加为1；4、不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。

capacity为不分配新内存空间时最多可保存的元素数目，size为已保存的元素数目。capacity永远大于等于size。

std::vector<std::string> v;
for (std::string buffer; std::cin >> buffer; v.push_back(buffer))
    std::cout << v.capacity() << std::endl;

string相关

const char* cp = "Hello World!!!"; //以空字符结束的数组
char noNull[]={'H','i'};  //不是以空字符结束
string sl(cp); //拷贝cp中的字符直到遇到空字符;s1=="Hello World!!!"
string s2(noNull,2); //从noNull拷贝两个字符;s2=="Hi"
// string s3(noNull); // 异常字符串，因为没有设置空字符结束
string s4(cp+6,5); //从cp[6]开始拷贝5个字符;s4=="world"
string s5(sl,6,5); //从s1[6]开始拷贝5个字符;s5=="World"
string s6(sl,6); //从s1[6]开始拷贝，直至s1末尾;s6=="world!!!"
string s7(sl,6,20); //正确，只拷贝到s1末尾;s7=="world!!!"
// string s8(sl,16); //抛出一个out of range 异常

截取字符串

string s("hello world"); 
string s2 = s.substr(0, 5); //s2 =hello
string s3 = s.substr(6); //s3 = world 
string s4 = s.substr(6, 11); //s4 = world
// string s5 = s.substr(12); //抛出一个out of range 异常
string s6 = s.substr(6, 2); //s6 = wo

其他方法

string类型支持顺序容器的赋值运算符以及assign、insert和erase操作。此外，它还提供了接受下标的insert与erase。

string s("hello world"); 
s.insert(s.size(), 5, '!'); // s后新增5个！
auto a = s.size();
s.erase(s.size() - 5, 5); // 删除s最后的5个字符

string也提供了接受c风格字符数组的insert和assign版本。

string s("hi!");  
const char* cp = "Stately, plump Buck";
s.assign(cp, 7); // 被替换为 Stately
s.insert(s.size(), cp + 7); // 添加 , plump Buck 

string中插入string

string s("some string"), s2("some other string");
s.insert(0, s2); // 将s2 插入到s 的0之前
s.insert(0, s2, 0, s2.size()); // 在s[0]之前插入【s2中从0到s2.size()的字符】。

append和replace

append 等同于 s.insert(xx.size, args)，replace为erase和insert的简写形式。

s2.append("aaa");

s2.replace(11, 3, "aaaaa"); // 删除从11开始的3个字符，插入aaaa

搜索方法

find函数是大小写敏感的。返回string::size_type值，为unsigned类型。不匹配时返回了一个很大的数，大于size。

string number("0123456"), name("r2d27");
auto a1 = name.find_first_of(number); // 1
auto a2 = name.find_last_of(number); // 3
auto a3 = name.find_first_not_of(number); // 0
auto a4 = name.find_last_not_of(number); // 4,因为7不在number里面
auto a5 = name.find_first_of(number, 2); // 为从d开始搜索，3
auto a6 = name.find_first_of(number, 4); // 为从7开始搜索，搜索不到，为一个超大数

逆向搜索

string river("Mississippi");
auto first_pos = river.find("is"); // 1
auto last_pos = river.rfind("is"); // 4
auto first_pos2 = river.find("is", 2); // 1

compare

数值转换

若string不能转换为一个数值，函数会抛出一个invalid_argument异常。如果得到的数值无法用任何类型来表示，则抛出一个out_of_range异常。

容器适配器

stack、queue和priority_queue是顺序容器适配器。适配器是标准库中的一个通用概念。容器、迭代器和函数都有适配器。它能使某种事物的行为看起来像另一种事物一样，

定义适配器

stack 栈LIFO

list<int> number = {1, 2, 3, 4, 5};
deque<int> deq(number.begin(), number.end());
// 通过容器初始化适配器
stack<int> stk(deq); // 从deq拷贝元素到stk
// 默认构造函数
stack<int> stk2();

默认情况下stack和queue是基于deque实现的，priority_queue是在vector上实现的。

list<string> strs = {"a", "b", "c", "d"};
vector<string> svec(strs.begin(), strs.end());
// 在vector上实现的空栈
stack<string, vector<string>> str_stk;
// str_stk2在vector上实现，初始化时保存sevc的拷贝
stack<string, vector<string>> str_stk2(svec);

适配器要求容器具有添加和删除元素的能力。因此适配器不能构造在array之上。forward_list也不能用于构造适配器，因为适配器都要求容器具有添加、删除以及访问尾元素的能力。

stack要求push_back、pop_back和back操作，故除array和forward_list都可构造stack

queue要求back、push_back、front和push_front操作，因此可构造于list或deque，但vector不行（无push_front）

priority_queue要求front、push_back和pop_back操作，以及随机访问能力，因此可构造于vector或deque，但list不行（不支持随机访问）

#include <stack>

using std::stack;

队列

queue 队列FIFO。priority_queue允许为队列中的元素建立优先级，新元素排在所有优先级比它低的已有元素之前。

#include <queue>

using std::queue;
using std::priority_queue;