容器种类

  • vector 可变大小数组
  • list 双向链表
  • forward_list 单向链表
  • deque 双向队列
  • array 固定大小数组
  • string 数组字符串，与vector类系

每一种容器都有自身的优缺点，下面总结下

数组类容器：vector array string 这一类容器的优点是支持随机访问，访问速度比较快，但是要执行插入或者删除操作时效率低

链表类：list forward_list 这一类数组的优缺点与之相反，不支持随机访问，如果想访问特定数据只能遍历，但是在执行插入和删除时比较方便

队列类：deque 双向队列，支持随机访问，在队尾或者队首删除或者插入元素时效率较快

特别的需要注意array容器是固定大小数组，和vector不同的是array不能再次添加或者删除元素也就是不能使用insert和erase方法

容器操作两个重要方法

swap

1
2
3
4
5
6
// 函数原型
swap(c1, c2);
// 容器自带方法也有swap
c1.swap(c2);
// 容器之间直接拷贝
c1 = c2

作用是交换两个容器之间的元素，使用swap方法比拷贝速度要快，我的理解是swap函数可能是直接在底层交换的两个函数的指针，并没有真正的进行交换，只是我的猜测后面还需要学习STL源代码来深入了解这里面的细节

assign

使用assign方法进行赋值运算，可以直接从一个列表进行赋值，也可以将一个容器中的值赋值到另一个容器中，当然，这两个容器中存放的类型可以不相同，但是要求二者进行强制转换操作，例如：

int -> double

double -> int

const char* -> string

上面这些可以进行强制转换的操作都可以，但是如果是两个容器之间直接进行拷贝，那么容器中存放值的内容必须相等

1
2
3
4
5
6
7
std::vector<double> dvec = {1, 2, 3, 4, 5, 6};
std::vector<int> ivec;

// 正确，可以使用assign来进行两个不同类型容器之间的复制操作
ivec.assign(dvec.begin(), dvec.end());
// 编译时报错，因为两个容器之间的类型不同
ivec = dvec;

forward_list的特殊性

因为forward_list是单向链表，删除或者添加一个元素最多会涉及到三个元素（当前元素，元素前驱，元素后继），所以他的插入和删除函数名字都带有after

1
2
3
4
lst.before_begin()
lst.insert_after()
emplace_after() // 返回新元素迭代器
lst.erase_after() // 返回被删元素之后的迭代器

这是因为在单向链表中插入或删除元素需要获得该元素的前驱，使用前驱元素来删除目标元素，所以会带有after

1
2
3
4
5
6
7
8
9
10
11
12
// 删除forward_list中的奇数元素
std::forward_list<int> flst = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
auto prev = flst.before_begin(); // 首前元素
auto curr = flst.begin(); // 链表的第一个元素
while (curr != flst.end()) {
    if (*curr % 2) {
        curr = flst.erase_after(prev); // 删除首前元素的后一个元素， 将后继元素
    } else {
        prev = curr; // 移动将当前元素变为首前元素
    }
    curr++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void find_str(std::forward_list<std::string>& slst, std::string& str1, std::string& str2) {
    // 查找地一个元素，并且将第二个元素插入第一个元素后面
    // 若str1没有在链表中，则将str2插入链表末尾
    auto prev = slst.before_begin();
    auto curr = slst.begin();

    while (curr != slst.end()) {
        if (*curr == str1) {
            curr = slst.insert_after(curr, str2); // 遍历匹配到字符串，插入
            break;
        } else {
            prev = curr;
        }
        curr++;
    }
    if (curr == slst.end()) { // 如果遍历到尾节点，则在使用首前节点进行插入
        slst.insert_after(prev, str2);
    }
}

改变容器大小

使用resize方法改变容器大小，需要注意resize方法不适用与array<>容器

1
2
3
4
5
6
7
8
std::list<int> ilist(10, 42); // 初始化list容器大小为10
std::cout << ilist.size() << std::endl;
ilist.resize(15); // 将容器大小扩大到15，扩大部分使用0填充
std::cout << ilist.size() << std::endl;
ilist.resize(25, -1); // 继续将容器扩大到25, 扩大部分使用-1填充
std::cout << ilist.size() << std::endl;
ilist.resize(5); // 将容器大小缩小到5,从容器末尾开始删除
std::cout << ilist.size() << std::endl;

迭代器

迭代器失效问题

​ 向容器中添加，或者删除元素的操作可能会使指向容器的指针，引用或者迭代器失效，这种失效类似与指针的非法访问问题。对于这些操作我的理解是在进行添加或者删除操作过后容器在内存中存储的位置可能会发生改变，导致原本指向容器的指针现在指向的是一片不能访问的内存区域。这就可以理解为什么像之前的inster或者erase等函数在添加或者删除容器元素后会返回一个迭代器，意义就在与可以更新容器迭代器。

下面展示一个关于迭代器更新的程序

1
2
3
4
5
6
7
8
9
10
std::vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto iter = vi.begin();
while (iter != vi.end()) {
    if (*iter % 2) {
        iter = vi.insert(iter, *iter); // 插入元素之后更新后的当前迭代器
        iter += 2; // 在更新迭代器之后才可以使用+或者-操作，一旦迭代器失效会导致程序崩溃
    } else {
        iter = vi.erase(iter); // 删除元素，返回删除元素之后的迭代器
    }
}

不要保存end()返回的迭代器

这个问题还是比较好理解的，因为容器的大小是实时更新的，加入将元素插入容器的末尾，那么end方法返回的迭代器不同了

1
2
3
4
5
6
7
8
//错误程序实例
auto begin = vi.begin();
auto end = vi.end();
while (begin != end) {
    ++begin;
    vi.insert(begin, 42);
    ++begin;
}

上面这段代码在运行时会崩溃，原因就是在在插入新元素后没有跟新begin迭代器，以及直接保存了end返回的迭代器，正确的写法应该是使用vi.end()来表示容器末尾，然后使用insert返回的新迭代器来更新begin迭代器

1
2
3
4
5
6
7
8
// 正确遍历方法
auto begin = vi.begin();
auto end = vi.end();
while (begin != vi.end()) {
    ++begin;
    begin = vi.insert(begin, 42);
    ++begin;
}

vector容器增长问题

对于vector中的reserve,size,capacity这几种方法比较模糊，记录一下区别

  • size：返回的是当前容器中元素的个数
  • capacity：返回容器在不进行扩容情况下最大能容纳的元素个数
  • reserve：分配至少能容纳n个元素的空间
  • shrink_to_fit：将最大容纳个数变成当前容器中的元素个数(size个数)

但是虽然容器最大容纳个数由capacity决定，但是在访问时只能访问size的大小，超过size大小会造成越界