C++ STL 学习笔记

本笔记部分内容来自 c++ 经典教程《C++ Primer Plus》

STL(Standard Template Library) 标准模板库中有 6 大组件。

• 容器（containers）：与数组类似的单元，可以储存若干值。
• 算法（algorithms）：完成特定任务的方法。
• 迭代器（iterators）：与数组的指针类似，可以遍历容器的对象。
• 仿函数（functors）：类似函数的对象，类对象或函数指针。
• 适配器（adapters）：提供容器不同的接口。
• 空间配置器（allocator）：容器分配内存和回收内存。

容器（containers）

容器是与数组类似的单元，可以储存若干值。一般认为，STL中有三类容器。

• 顺序容器
• 关联容器
• 无序关联容器

顺序容器

顺序容器实现能按顺序访问的数据结构。

array 静态的连续数组

定义于头文件 <array>

std::array是封装固定大小数组的容器，可以看作一个不会退化成指针的数组。它有一个非静态数据成员内建数组T[N]，因此 array 结合了内建数组的性能、可访问性与容器的优点，比如可获取大小、支持赋值、随机访问迭代器等。

成员函数

隐式定义的成员函数

• 构造函数
• 析构函数
• 复制构造函数

元素访问

• at 访问指定的元素，同时进行越界检查

• operator[] 访问指定的元素

• front 访问第一个元素

• back 访问最后一个元素

• data返回指向内存中数组第一个元素的指针

    #include <iostream>
    #include <array>
  
    int main()
    {
        std::array<int, 6> data = {1, 2, 4, 5, 5, 6};
        auto data2 = data;
        data.at(1) = 88; // data 中的 2 改为 88
        data[0] = 78; // data 中的 1 改为 78
        try {
            data.at(6)++; // 抛出 out_of_range
        } catch (std::out_of_range const& exc) {
            std::cout << exc.what() << '\n'; 
            // array::at: __n (which is 6) >= _Nm (which is 6)
        }
        data.front() += data.back();
        int* ptr = data.data();
        return 0;
    }

容量

• empty 检查容器是否为空（在 array 中一般不使用）
• size 返回容纳的元素数
• max_size 返回可容纳的最大元素数（在 array 中与 size 作用相同）

操作

• fill 以指定值填充容器（覆盖填充）

• swap 交换内容（交换大小与类型完全相同的数组内容）

    #include <iostream>
    #include <array>
  
    int main()
    {
        std::array<int, 10> data = {1, 2, 3, 4, 5, 6};
        std::cout << (data.size() == data.max_size())<< '\n'; // 1
        data.fill(7);
        for (const auto& i : data) {
            std::cout << i << ' '; // 7 7 7 7 7 7 7 7 7 7 
        }
        std::cout << '\n';
        std::array<int, 10> data2;
        if (!data2.empty()) { // 除非在定义时指定数组大小为 0，否则 empty 永远为 false
            std::cout << data2.size() << '\n'; // 10
        }
        data2.fill(1);
        data.swap(data2); // 交换两个同类型数组（元素类型和大小）
        for (const auto& i : data) {
            std::cout << i << ' '; // 1 1 1 1 1 1 1 1 1 1 
        }
        std::cout << '\n';
        return 0;
    }

迭代器

迭代器类似指针。

• begin 返回指向起始的迭代器

• end 返回指向末尾的迭代器

• rbegin 返回指向起始的逆向迭代器

• rend 返回指向末尾的逆向迭代器

• cbegin cend crbegin crend 只读迭代器

    #include <iostream>
    #include <array>
  
    int main()
    {
        std::array<int, 5> data = {1, 2, 3, 4, 5};
        for (auto i = data.begin(); i != data.end(); ++i) {
            std::cout << *i << ' '; // 1 2 3 4 5 
        }
        std::cout << '\n';
        for (auto i = data.rbegin(); i != data.rend(); ++i) {
            std::cout << *i << ' '; // 5 4 3 2 1 
        }
        std::cout << '\n';
        auto i = data.cbegin(); // 推导出 const 类型，元素只读
        return 0;
    }

非成员函数

• operator== 按字典序比较字典中的值
• operator!= 按字典序比较字典中的值
• operator< 按字典序比较字典中的值
• operator<= 按字典序比较字典中的值
• operator> 按字典序比较字典中的值
• operator>= 按字典序比较字典中的值
• std::get(std::array) 访问数组中的一个元素
• std::swap(std::array) 交换数组的元素
• to_array (c++20) 将内建数组转为数组对象

vector 变长数组

vector 不像它的名字描述那样，它一点都不像向量，我觉得把它叫做变长数组更贴切一些。

vector 的存储是自动管理的，按需扩张收缩。 vector 通常占用多于静态数组的空间，因为要分配更多内存以管理将来的增长。 vector 所用的方式不在每次插入元素时，而只在额外内存耗尽时重分配。分配的内存总量可用 capacity() 函数查询。额外内存可通过对 shrink_to_fit() 的调用返回给系统。

vector 是非常常用的一类容器，它的相关操作时间复杂度如下：

• 随机访问 O(1)
• 末尾插入或移除元素 O(1)
• 插入或移除元素 O(n) n 为到末尾的距离

特化

std::vector 对类型 bool 有特化，以节省空间。

成员函数（与 array 不同）

容量

• reserve 预留储存空间
• capacity 返回当前储存空间能够容纳的元素数
• shrink_to_fit 通过释放未使用的内存减少内存的使用

修改器

• clear 清除内容
• insert 插入元素
• emplace 原位构造函数
• erase 擦除元素
• push_back 将元素添加到容器末尾
• resize 改变容器中可存储元素的个数

修改器中 insert 和 emplace 都是插入元素，但是 emplace 在某些情况不会产生临时对象。

在C++11中可以取地址的、有名字的就是左值，反之，不能取地址的、没有名字的就是右值（将亡值或纯右值）。

#include <cmath>

const double&& PI = acos(-1.0); // 3.14159265358...

using namespace std;

int main()
{
    int a = 3;   // 可行，定义 a = 1
    // int &b = 1;  // 报错，1 是右值，b 是左值引用
    int &&c = 1; // 可行，1 是右值，c 是右值引用
    int &d = a;  // 可行，a 是左值，d 是左值引用
    // int &&e = a; // 报错，a 是左值，e 是右值引用
    int &f = c;  // 可行，c 是左值，f 是左值引用
    // int &&g = c; // 报错，c 是左值，g 是右值引用
    int &h = d;  // 可行，d 是左值，h 是左值引用
    // int &&i = d; // 报错，d 是左值，i 是右值引用
}

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

struct A {
    std::string s;
    A(std::string str) : s(std::move(str))  { std::cout << " constructed\n"; }
    A(const A& o) : s(o.s) { std::cout << " copy constructed\n"; }
    A(A&& o) : s(std::move(o.s)) { std::cout << " move constructed\n"; }
    A& operator=(const A& other) {
        s = other.s;
        std::cout << " copy assigned\n";
        return *this;
    }
    A& operator=(A&& other) {
        s = std::move(other.s);
        std::cout << " move assigned\n";
        return *this;
    }
};

int main()
{
    std::vector<A> container;
    // 预留足够的空间以使 vector 不必重设大小
    container.reserve(10);
    std::cout << "construct 2 times A:\n";
    A two { "two" };
    A three { "three" };

    std::cout << "emplace:\n";
    container.emplace(container.end(), "one");

    std::cout << "emplace with A&:\n";
    container.emplace(container.end(), two);

    std::cout << "emplace with A&&:\n";
    container.emplace(container.end(), std::move(three));

    std::cout << "content:\n";
    for (const auto& obj : container)
        std::cout << ' ' << obj.s;
    std::cout << '\n';
}

• assign 将值赋给容器
• get_allocator 返回相关的分配器

list 双向链表

双向链表是一个常用的数据结构，适合用来进行大量的插入删除操作，但是随机读写性能较差，与 vector 容器互补。

修改器

• push_head 向前插入一个元素
• emplace_head 向前插入一个元素
• pop_head 删除前面一个函数
• merge 归并两个已排序双向链表

#include <iostream>
#include <list>

std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
    for (auto &i : list) {
        ostr << " " << i;
    }
    return ostr;
}

int main()
{
    std::list<int> list1 = { 5,9,0,1,3 };
    std::list<int> list2 = { 8,7,2,6,4 };

    list1.sort();
    list2.sort();
    std::cout << "list1:  " << list1 << "\n"; // list1:   0 1 3 5 9
    std::cout << "list2:  " << list2 << "\n"; // list2:   2 4 6 7 8
    list1.merge(list2);
    std::cout << "merged: " << list1 << "\n"; // merged:  0 1 2 3 4 5 6 7 8 9
}

链表操作

• splice 从另一个list中移动元素
• remove 移除满足特定标准的元素
• remove_if移除满足特定标准的元素
• reverse 将该链表的所有元素的顺序反转
• unique 删除连续的重复元素
• sort 对元素进行排序

#include <iostream>
#include <list>

std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
    for (auto &i : list) {
        ostr << " " << i;
    }
    return ostr;
}

int main ()
{
    std::list<int> list1 = { 1, 2, 3, 4, 5 };
    std::list<int> list2 = { 10, 20, 30, 40, 50 };

    auto it = list1.begin();
    std::advance(it, 2);

    list1.splice(it, list2);

    std::cout << "list1: " << list1 << "\n"; // list1:  1 2 10 20 30 40 50 3 4 5
    std::cout << "list2: " << list2 << "\n"; // list2: 

    list2.splice(list2.begin(), list1, it, list1.end());

    std::cout << "list1: " << list1 << "\n"; // list1:  1 2 10 20 30 40 50
    std::cout << "list2: " << list2 << "\n"; // list2:  3 4 5
}

关联容器

map 映射

map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。

成员类

• value_compare 比较键类型的对象

#include <iostream>
#include <map>

class key_com
{
    public:
    bool operator() (const int& a, const int& b) {
        return a < b;
    }
};

int main()
{
    std::map<int, int, key_com> m{{1, 1}, {2, 4}, {4, 16}};
    for(const auto& i : m) {
        std::cout << i.first << ": " << i.second << std::endl;
    }
    // 1: 1 
    // 2: 4 
    // 4: 16
    m.insert({3, 9});
    for(const auto& i : m) {
        std::cout << i.first << ": " << i.second << std::endl;
    }
    // 1: 1
    // 2: 4
    // 3: 9
    // 4: 16
}

查找

• count
• find
• equal_range
• lower_bound
• upper_bound

观察器

set 集合

算法（algorithms）

迭代器（iterators）

仿函数（functors）