C++ - 容器

编程 评论

C++ 学习笔记
C++ Container 浅析

容器的定义

  • 容器是特定类型对象的集合

  • 在没有使用容器之前，我们可能会用数组解决一些问题。使用数组解决问题，那么我们必须要知道或者估算出大约要存储多少个对象，这样我们会创建能够容纳这些对象的内存空间大小。当我们要处理一些完全不知道要存储多少对象的问题时，数组显的力不从心。我们可以使用容器来解决这个问题。容器具有很高的可扩展性，我们不需要预先告诉它要存储多少对象，只要创建一个容器，并合理的调用它所提供的方法，所有的处理细节由容器自身完成。

通用容器的分类

  • 通用容器分为3类：顺序容器、关联容器、容器适配器

顺序容器

  • 顺序容器是一种元素之间有顺序的线性表，是一种线性结构的可序群集。这和我们数据结构课程上所讲的线性表是一样的。顺序容器中的每个元素位置是固定的，除非你使用了插入或者删除操作改变了这个位置。顺序容器不会根据元素的特点排序而是直接保存了元素操作时的逻辑顺序。比如我们一次性对一个顺序容器追加三个元素，这三个元素在容器中的相对位置和追加时的逻辑次序是一致的。

顺序容器的类型：

类别 简介
vector 可变大小数组，一段连续的内存空间，支持快速随机访问。在尾部之外的位置插入或者删除元素可能很慢。
deque 双端队列。支持快速随机访问。在头尾位置插入、删除速度很快。
list 双向链表。只支持双向顺序访问。在list中任何位置进行插入、删除操作速度都很快。
forward_list 单向链表。只支持单向顺序访问。在链表的任何位置进行插入、删除操作都很快。(C++11标准新加)
array 固定大小数组。支持快速随机访问。不能添加或者删除元素。(C++11标准新加)
string 与vector相似的容器，但专门用于保存字符。随机访问快，在尾部插入删除快。
  • 关于各容器的操作，实在是太多了，下面的示例程序列举一些比较常见的操作和用法。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    #include <iostream>
    #include <vector>
    #include <string>
    #include <deque>
    #include <list>
    #include <forward_list>
    #include <array>

    using namespace std;

    int main()
    {
        /*--------------------- vector容器的一些操作  ------------------*/
        vector<int> vect1;            // 定义一个vector容器
        vect1.push_back(1);            // push_back: 向容器的末尾添加元素
        vect1.push_back(2);
        vect1.push_back(3);
        vect1.pop_back();            // pop_back: 去除末尾的元素

        vect1.insert(vect1.begin() + 1, 8);    // 在某个位置插入一个元素,效率低，不适合大批操作
        vect1.at(0);                        // at:取某个位置的元素
        vect1.capacity();                    // capacity: 不分配新的内存空间的前提下它最多能保存多少元素。这个和下面的size 是有区别的！！
        vect1.size();                        // size: 已经保存的元素的数目
        vect1.empty();                        // empty：判断容器是否为空
        vect1.front();                        // front：取第一个元素
        vect1.back();                        // back：取最后一个元素
        vect1.erase(vect1.begin() + 1);        // erase：删除指定位置的元素
        vector<int> vect2;
        vect2.assign(vect1.begin(), vect1.end()); // 赋值操作
        /*------------------------------------------------------------*/

        // 其他容器操作都和vector差不多，以下列举一些其他容器特有的操作


        /*--------------------- string容器一些操作  --------------------*/
        string str1 = "Hello Ace";            // string的几种构造方法
        string str2("Hello World");        
        string str3(str1, 6);                // 从str1下标6开始构造， str3 -> Ace
        
        string str4 = str2.substr(0, 5);    // 求子串： str4 -> Hello
        string str5 = str2.substr(6);        // 求子串： str5 -> World
        string str6 = str2.substr(6, 11);    // 求子串： str6 -> World
        // string str7 = str2.substr(12);    // 抛异常： out_of_range

        string str8 = str2.replace(6, 5, "Game");    // 替换：str8 -> Hello Game 从位置6开始，删除5个字符，并替换成"Game"
        
        string str9 = str2.append(", Hello Beauty");// 追加字符串： str9 -> Hello World, Hello Beauty

        auto pos1 = str1.find("Ace");                // 查找字符串    : pos1 -> 6 ,返回第一次出现字符串的位置，如果没找着，则返回npos

        int res = str1.compare("Hello, Ace");        // 比较字符串： res -> -1, 根据str1是等于、大于还是小于参数指定的字符串， 返回0、整数或者负数

        string str10 = "Pi = 3.14159";
        double pi = stod(str10.substr(str10.find_first_of("+-.0123456789")));    // 数值转换： pi -> 3.14159
        /*------------------------------------------------------------*/


        /*--------------------- deque容器一些操作  --------------------*/
        deque<int> d1;
        d1.push_back(1);                            // 尾后压入元素
        d1.push_back(2);
        d1.push_back(3);
        d1.push_front(4);                            // 队头压入元素
        d1.push_front(5);
        d1.push_front(6);
        d1.pop_back();                                // 尾后弹出一个元素
        d1.pop_front();                                // 队头弹出一个元素

        d1.front();                                    // 取队头元素
        d1.back();                                    // 取队尾元素
        /*------------------------------------------------------------*/


        /*--------------------- list容器一些操作  --------------------*/
        list<int> l;
        l.push_back(1);                                // 尾后压入元素
        l.push_back(2);
        l.push_back(3);
        l.push_front(4);                            // 队头压入元素
        l.push_front(5);
        l.push_front(6);
        l.pop_back();                                // 尾后弹出一个元素
        l.pop_front();                                // 队头弹出一个元素
        l.front();                                    // 取队头元素
        l.back();                                    // 取队尾元素

        l.insert(l.begin(), 88);                    // 某个位置插入元素(性能好)
        l.remove(2);                                // 删除某个元素(和所给值相同的都删除)
        l.reverse();                                // 倒置所有元素
        l.erase(--l.end());                            // 删除某个位置的元素(性能好)
        /*------------------------------------------------------------*/


        /*--------------------- forward_list容器一些操作  --------------*/
        forward_list<int> fl = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        fl.push_front(0);                // 压入元素，该容器没有push_back方法
        auto prev = fl.before_begin();    // 表示fl的"首前元素"
        auto curr = fl.begin();            // 表示fl的第一个元素

        // 循环遍历
        while (curr != fl.end())        // 表示仍有元素要处理
        {
            if (*curr % 2)                // 若元素为奇数，则删除
            {
                curr = fl.erase_after(prev);    // 删除它并移动curr
            }
            else
            {
                prev = curr;            // 移动迭代器curr，指向下一个元素，prev指向curr之前的元素
                ++curr;
            }
        }

        // 操作后： fl = {0, 2, 4, 6, 8}
        /*------------------------------------------------------------*/


        /*--------------------- array容器一些操作  --------------------*/
        array<int, 5> myArray1 = { 1, 2, 3, 4, 5 };    // 定义一个一维数组
        array<array<int, 2>, 3> myArray2 = {1, 2, 3, 4, 5, 6};    // 定义一个二维数组
        array<int, 5> myArray3 = {6, 7, 8, 9, 10};
        array<int, 5> myArray4;                // 此数组并未初始化

        // array.resize();        // array 不能有改变容器大小的操作，它的效率比vector高
        myArray1.swap(myArray3);// 交换两个数组的的元素
        myArray4 = myArray1;    // 支持直接这样赋值，原生的数组不可以这样。它把值全部复制过去，而不是引用
        myArray1.assign(0);        // 把myArray1的元素全部置为0

        // 遍历数组元素
        for (int i = 0; i < myArray1.size(); ++i)
        {
            cout << myArray1[i] << endl;
        }
        /*------------------------------------------------------------*/

        return 0;
    }

关联容器

  • 关联容器(associative-container)和顺序容器有着根本的不同：关联容器中元素定义是按关键字来保存和访问的。与之相对，顺序容器中的元素是按他们在容器中的位置来顺序保存和访问的。虽然关联容器的很多行为和顺序容器相同，但其不同之处反映了关键字的作用。

  • 关联容器支持高效的关键字查询和访问。标准库一共定义了8个关联容器，最主要的类型是map和set。8个容器中，每个容器：

    • 是一个map或者是一个set。map保存关键字-值对；set只保存关键字。
    • 要求关键字唯一或者不要求。
    • 保持关键字有序或者不保证有序。

关联容器类型：

  • 按关键字有序保存元素
类别 简介
map 关联数组；保存关键字-值对
set 关键字即值，即只保存关键字的容器
multimap 关键字可重复的map
multiset 关键字可重复的set
  • 无序集合
类别 简介
unordered_map 用哈希函数组织的map
unordered_set 用哈希函数组织的set
unordered_multimap 哈希组织的map;关键字可以重复出现
unordered_multiset 哈希组织的set;关键字可以重复出现
  • 从上面的容器名称可以看出：允许重复关键字的容器名字都包含multi；而使用哈希技术的容器名字都以unordered开头。

map的使用

  • 下面的程序是统计每个单词在输入中出现的次数：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <iostream>
    #include <map>
    #include <string>

    using namespace std;

    int main()
    {
        // 统计每个单词在输入中出现的次数
        map<string, size_t> word_count;        // string到map的空map
        string word;
        while (cin >> word)
        {
            ++word_count[word];                // 提取word的计数器并将其加1
        }

        for (const auto &w : word_count)    // 遍历map的每个元素
        {
            cout << w.first << "出现的次数为: " << w.second << endl;
        }

        return 0;
    }

set的使用

  • 对上面那个统计单词的程序做一个扩展，忽略常见单词。比如 the and or then等。 我们使用set保存想要忽略的单词，只对不在集合中的单词进行统计。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #include <iostream>
    #include <map>
    #include <set>
    #include <string>

    using namespace std;

    int main()
    {
        // 统计每个单词在输入中出现的次数
        map<string, size_t> word_count;        // string到map的空map
        set<string> exclude = {"The", "But", "And", "Or", "An", "A", 
                                "the", "but", "and", "or", "an", "a"};
        string word;
        while (cin >> word)
        {
            // 只统计不在exclude中的单词。find调用返回一个迭代器，如果在集合中，返回的迭代器指向其该关键中。否则返回尾后迭代器
            if (exclude.find(word) == exclude.end())
            {
                ++word_count[word];                // 提取word的计数器并将其加1
            }
        }

        for (const auto &w : word_count)    // 遍历map的每个元素
        {
            cout << w.first << "出现的次数为: " << w.second << endl;
        }

        return 0;
    }

容器适配器

  • 除了顺序容器外，标准库还定义了三个顺序容器适配器:stack、 queue和priority_queue。 适配器(adaptor)是标准库的一个通用概念。容器、迭代器和函数都有适配器。
1
本质上，一个适配器是一种机制，能使某种事物的行为看起来像另一种事物一样。
  • 所有容器适配器都支持的操作和类型
操作名 简介
size_type : 一种类型，足以保存当前类型的最大对象的大小
value_type : 元素类型
container_type : 实现适配器的底层容器类型
A a : 创建一个名为a的空适配器
A a(c) : 创建一个名为a的适配器，带有容器c的一个拷贝
关系运算符 : 每个适配器都支持所有关系运算符： ==、！=、<、<=、>、和>=。这些运算符返回底层容器的比较结果。
a.empty() : 若a包含任何元素，返回fasle，反正返回true
a.size() : 返回a中的元素数目
swap(a, b) : 或写作a.swap(b)、b.swap(a)。交换a和b的内容。a和b必须有相同的类型，包括底层容器类型也必须相同
  • 栈适配器(stack)的额外操作
操作名 简介
s.pop() : 删除栈顶元素，但不返回该元素值。
s.push(item) : 创建一个新元素压入栈顶
s.emplace(args) : 同push，其值由args构造
s.top() : 返回栈顶元素，但不将元素弹出栈
  • queue和priority_queue的额外操作
操作名 简介
q.pop() 返回queue的首元素或priority_queue的最高优先级的元素，但不删除此元素。
q.front() 返回首元素或者尾元素，但不删除此元素
q.back() 只使用于queue
q.top() 返回最高优先级元素，但不删除此元素
q.push(item) 在queue末尾或者priority_queue中恰当的位置创建一个元素，其值为item
q.emplace(args) 同push,其值由args构造

  • 栈默认基于deque实现。queue默认基于deque实现。priority_queue默认基于vector实现。

  • stack和queue的使用方法比较简单，priority_queue在存储自己定义的数据结构时，必须重载 operator < 或者自己写仿函数。下面给个简单的例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include <iostream>
    #include <queue>

    using namespace std;

    struct Node
    {
        int x;
        int y;
    };

    struct MyCmp
    {
        // 自定义的比较函数
        bool operator ()(Node a, Node b)
        {
            if (a.x == b.x)
            {
                return a.y > b.y;
            }
            
            return a.x > b.x;
        }
    };

    int main()
    {
        // priority_queue<Type, Container, Functional>
        // Type 为数据类型，Container 为保存数据的容器，Functional 为元素比较方式
        priority_queue<Node, vector<Node>, MyCmp>  myQueue;

        // 添加一些元素
        for (int i = 1; i <= 10; ++i)
        {
            Node node;
            node.x = i;
            node.y = i * i;
            myQueue.push(node);
        }

        // 遍历元素
        while (!myQueue.empty())
        {
            cout << myQueue.top().x << "," << myQueue.top().y << endl;
            myQueue.pop();            // 出队
        }

        return 0;
    }

QinHanGame Developer & Designer

当你发现自己的才华撑不起野心时，就请安静下来学习吧！