Skip to content

C++语言导学(5): 容器

引言

如果一个类的主要目的是保存对象，那么通常称之为容器(container)。

这里主要简单概述一下这些标准库容器:

  • vector: 有序序列
  • list: 双向链表
  • map: 关联字典
  • unordered_map: 无序哈希

vector

一个vector就是一个给定类型元素的序列，元素在内存中是连续存储的。

对于vector最主要的操作是push_back()追加内容，但容量不足的时候它会自动扩充容量，它有一套自己的策略来扩充容器，效率很高。

vector足够灵活、高效，应该作为默认容器；尽量避免容器的拷贝复制，而是使用引用或指针来避免这种耗时操作。

但vector为了保证高效以应用到性能关键的程序中，不会进行下标越界检查，比如:

#include <iostream>
#include <vector>
using namespace std;

int main(){
    try{
        vector<int> vData;

        //int i = vData[vData.size()];
        int i = vData.at(vData.size()); // 推荐使用at()方法而不是下标访问

    } catch(out_of_range& err){
      cerr << "range error\n";
    } catch(...){
      cerr << "unknow exception\n";
    }

    return 0;
}

list

如果希望在一个序列中添加、删除元素而不需要移动其他元素，则选择list，它是双向链表。

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

void display(const list<int>& data){
    for(auto &x:data)
        cout << x << ",";
    cout << "\n";
}

int main()
{
    list<int> lData{10,2,3,5,8,1};
    display(lData); // 10,2,3,5,8,1,

    auto p = find(lData.begin(), lData.end(),3);
    auto q = find(lData.begin(), lData.end(),8);

    lData.insert(p,12); // 在迭代器p前面插入值
    display(lData); // 10,2,12,3,5,8,1,

    lData.erase(p); // 销毁元素
    display(lData); // 10,2,12,5,8,1,

    lData.erase(q); // p,q并没有因为前面insert操作而失效
    display(lData); // 10,2,12,5,1,

    return 0;
}

当数据量较小时，vector性能会优于list，除非有理由选择list，否则应该使用vector。

vector无论在遍历(find,count)性能还是排序和搜索(sort,equal_range)性能都优于list。

map

map又叫关联数组或字典，用平衡二叉树(红黑树)实现。

map<string, int> mData{{"David",123},{"Tom",123}};// David->123;Tom->123;

mData["Leslie"] = 578; // David->123;Leslie->578;Tom->123;

mData["Zhu"]; // David->123;Leslie->578;Tom->123;Zhu->0;

进行下标操作本质是进行一次搜索，如果没找到key就自动插入新元素，value是对应的默认值。

一般常用操作是find()和insert()。

unordered_map

标准库中哈希容器被叫做“无序”容器。

underorder_map的操作和map没太大区别，区别在于不是用一个有序函数进行比较操作，而是使用哈希函数。

比如:

#include <iostream>
#include <unordered_map>

using namespace std;

struct Record{
   friend struct RHash;

   string name;
   int age;

   Record(const string& s, const int& i): name(s), age(i){}

   bool operator==(const Record& rhs) const {
       return name == rhs.name && age == rhs.age;
   }
};

struct RHash{
    size_t operator()(const Record& r) const {
        return hash<string>()(r.name)^hash<int>()(r.age);
    }
};

void display(const unordered_map<Record,int,RHash>& data){
    cout << "unordered map: ";
    for(auto &x:data)
       cout << "("<<x.first.name<<","<<x.first.age<<")" << "->" << x.second << ";";
    cout << "\n";
}

int main()
{
    unordered_map<Record,int,RHash> uData{{{"David",26},123}}; // 使用自定义哈希函数
    display(uData); // (David,26)->123;

    uData[Record("Tom",30)] = 456;
    display(uData); // (Tom,30)->456;(David,26)->123;

    uData[Record("Leslie",35)] = 578;
    display(uData); // (Leslie,35)->578;(Tom,30)->456;(David,26)->123;

    uData[Record("Zhu",40)];
    display(uData); // (Zhu,40)->0;(Leslie,35)->578;(Tom,30)->456;(David,26)->123;

    return 0;
}