c11中新增加容器

ゝ一纸荒年。 2022-12-25 13:00 189阅读 0赞

转载自 [https://zhuanlan.zhihu.com/p/137428884][https_zhuanlan.zhihu.com_p_137428884]

本文主要对C++11/14中标准库新增容器的特性进行详细说明，方便大家学习参考。

## 1.`std::array` ##

为什么要引入这个容器呢？主要有两点原因：

> A. `std::vector`太强大了，存储在堆内存中，而 `std::array`存储在栈内存中，访问更加灵活，可以获得更高的性能；  
> B. 使用 `std::array`能够让代码变得更加现代，且封装了一些函数和算法，使用起来比传统数组更方便；

`std::array`会在编译时创建一个固定大小的数组，不能被隐式地转换成指针。在使用`std::array`时，只需要指定其类型和大小即可，如下所示：

std::array<int, 4> arr= {1,2,3,4};
    
    int len = 4;
    std::array<int, len> arr = {1,2,3,4}; // 非法, 数组大小参数必须是常量表达式

在使用`std::array`时，要兼容C风格的接口时，可以用如下方法：

void foo(int *p, int len) 
    {
        return;
    }
    
    std::array<int 4> arr = {1,2,3,4};
    
    // C 风格接口传参
    // foo(arr, arr.size());           // 非法, 无法隐式转换
    foo(&arr[0], arr.size());
    foo(arr.data(), arr.size());
    
    // 使用 `std::sort`
    std::sort(arr.begin(), arr.end());

## 2.`std::forward_list` ##

这是一个列表容器，使用方法和`std::list`基本类似。需要注意的是，`std::list`是双向链表实现的，而`std::forward_list`是单向链表实现的，提供了`O(1)`复杂度插入元素，不提供`size()`方法。当不需要双向迭代时，具有比`std::list`更高的利用率。

## 3.无序容器 ##

传统C++中，**有序容器**`std::map`和`std::set`都是通过红黑树进行实现的，搜索和插入的平均复杂度均为`O(log(size))`，在插入元素时，会根据`<`操作符比较元素大小并判断元素是否相同，并选择合适的位置插入到容器中，遍历时，也是按`<`操作符顺序来逐个遍历。

无序容器中的元素不进行排序，内部通过`hash`表实现，插入和删除元素的平均复杂度为`O(常量)`，在不关心内部元素的顺序时，能显著提升性能。

C++11中引入了两组无序容器：

> `std::unordered_map`和 `std::unordered_multimap`  
> `std::unordered_set`和 `std::unordered_multiset`

它们的用法与原有的`map / multimap`和`set / multiset`类似。这里来比较一下`std::map`和`std::multimap`的用法，代码如下：

#include <iostream>
    #include <string>
    #include <unordered_map>
    #include <map>
    
    int main() {
        // 两组结构按同样的顺序初始化
        std::unordered_map<int, std::string> u = {
            {1, "1"},
            {3, "3"},
            {2, "2"}
        };
        std::map<int, std::string> v = {
            {1, "1"},
            {3, "3"},
            {2, "2"}
        };
    
        // 分别对两种容器进行遍历
        std::cout << "std::unordered_map" << std::endl;
        for( const auto & n : u) 
            std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    
        std::cout << std::endl;
        std::cout << "std::map" << std::endl;
        for( const auto & n : v) 
            std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    } 
    /*
    程序输出结果为：
    std::unordered_map
    Key:[2] Value:[2]
    Key:[3] Value:[3]
    Key:[1] Value:[1]
    
    std::map
    Key:[1] Value:[1]
    Key:[2] Value:[2]
    Key:[3] Value:[3]

## 4.元组`std::tuple` ##

在传统C++中，除了`std::pair`外，没有现成的结构能够存放不同类型的数据，但是`std::pair`的缺陷在于只能保存两个元素。

*  **元组的基本操作**

元组的使用有三个核心函数：

> `std::make_tuple`：构造元组  
> `std::get`：获得元组某个位置的值  
> `std::tie`：元组拆包

下面是一外使用的例子：

#include <tuple>
    #include <iostream>
    
    auto get_student(int id)
    {
        // 返回类型被推断为 std::tuple<double, char, std::string>
    
        if (id == 0)
            return std::make_tuple(3.8, 'A', "张三");
        if (id == 1)
            return std::make_tuple(2.9, 'C', "李四");
        if (id == 2)
            return std::make_tuple(1.7, 'D', "王五");
        return std::make_tuple(0.0, 'D', "null");   
        // 如果只写 0 会出现推断错误, 编译失败
    }
    
    int main()
    {
        auto student = get_student(0);
        std::cout << "ID: 0, "
        << "GPA: " << std::get<0>(student) << ", "
        << "成绩: " << std::get<1>(student) << ", "
        << "姓名: " << std::get<2>(student) << '\n';
    
        double gpa;
        char grade;
        std::string name;
    
        // 元组进行拆包
        std::tie(gpa, grade, name) = get_student(1);
        std::cout << "ID: 1, "
        << "GPA: " << gpa << ", "
        << "成绩: " << grade << ", "
        << "姓名: " << name << '\n';
    }

*  **元组合并与遍历**

元组的合并可以用`std::tuple_cat`来实现。

auto new_tuple = std::tuple_cat(get_student(1), std::move(t));

获取元组的长度后，即可以对元组进行迭代了。

template <typename T>
    auto tuple_len(T &tpl) 
    {
        return std::tuple_size<T>::value;
    }
    // 迭代
    for(int i = 0; i != tuple_len(new_tuple); ++i)
        // 运行期索引
        std::cout << tuple_index(i, new_tuple) << std::endl;

[https_zhuanlan.zhihu.com_p_137428884]: https://zhuanlan.zhihu.com/p/137428884