🥣关于容器

STL中容器的概述

容器-Container

容器用于表示由同类型元素构成的、长度可变的元素序列。

容器是由类模板来实现的,模板的参数是容器中元素的类型。

STL中包含了很多种容器,虽然这些容器提供了一些相同的操作,但由于它们采用了不同的内部实现方法,因此,不同的容器往往适合于不同的应用场合

STL的主要容器

vector<元素类型>

用于需要快速定位(访问)任意位置上的元素以及主要在元素序列的尾部增加/删除元素的场合。

在头文件vector中定义,用动态数组实现。

list<元素类型>

用于经常在元素序列中任意位置上插入/删除元素的场合。

在头文件list中定义,用双向链表实现。

在C++11标准中增加了forward_list容器,本质上是一个单向链表,定义在头文件forward_list中。

deque<元素类型>

用于主要在元素序列的两端增加/删除元素以及需要快速定位(访问)任意位置上的元素的场合。

在头文件deque中定义,用分段的连续空间结构实现。

stack<元素类型>

用于仅在元素序列的尾部增加/删除元素的场合。

在头文件stack中定义,可基于dequelistvector来实现。

queue<元素类型>

用于仅在元素序列的尾部增加、头部删除元素的场合。

在头文件queue中定义,可基于dequelist来实现。

priority_queue<元素类型>

它与queue的操作类似,不同之处在于:每次增加/删除元素之后,它将对元素位置进行调整,使得头部元素总是最大的。也就是说,每次删除操作总是把最大(优先级最高)的元素去掉。

在头文件queue中定义,可基于dequevector来实现。

map<关键字类型,值类型> 和 multimap<关键字类型,值类型>

用于需要根据关键字来访问元素的场合。容器中每个元素是一个pair结构类型,该结构有两个成员:firstsecond,关键字对应first,值对应second,元素是根据其关键字排序的。

对于map,不同元素的关键字不能相同;

对于multimap,不同元素的关键字可以相同。

它们在头文件map中定义,常常用某种二叉树来实现。

有时候我们不需要排序,所以在C++11标准中新增加了unordered_map

unordered_multimap容器。

set<元素类型> 和 multiset<元素类型>

它们分别是mapmultimap的特例,每个元素只有关键字而没有值,或者说,关键字与值合一了。

在头文件set中定义。

C++11标准中增加了unordered_setunordered_multiset容器。

basic_string<字符类型>

vector类似,不同之处在于其元素为字符类型,并提供了一系列与字符串相关的操作。

stringwstring分别是它的两个实例:

  • basic_string<char>

  • basic_string<wchar_t>

在头文件string中定义。

容器的基本操作

容器类模板提供了一些成员函数来实现容器的基本操作,其中包括:

  • 往容器中增加元素

  • 从容器中删除元素

  • 获取容器中指定位置的元素

  • 在容器中查找元素

  • 获取容器首/尾元素的迭代器

  • ......

这些成员函数往往具有通用性(大部分容器类模板都包含它们)。

注意:如果容器的元素类型是一个类,则针对该类可能需要:

  • 自定义拷贝构造函数和赋值操作符重载函数

    • 对容器进行的一些操作中可能会创建新的元素(对象的拷贝构造)或进行元素间的赋值(对象赋值)。

    • 重载小于操作符(<) 对容器进行的一些操作中可能要进行元素比较运算。

举例:利用map实现一个简单的电话簿

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
    map<string,int> phone_book; // 创建一个map类容器,用于存储电话号码簿
    
    // 创建电话簿
    phone_book["wang"] = 12345678; // 通过[]操作和关键字往容器中加入元素
    phone_book["li"] = 87654321;
    phone_book["zhang"] = 56781234;
    // ......  还可以添加更多的信息
    // 输出电话号码簿
    cout << "电话号码簿的信息如下:\n";
    for (pair<string, int> item: phone_book) 
    // C++11中引入的enhanced-for loop
        cout << item.first << ": " << item.second << endl; 
    // 输出元素的姓名和电话号码

    // 查找某个人的电话号码
    string name;
    cout << "请输入要查询号码的姓名:";
    cin >> name;
    map<string,int>::const_iterator it; // 创建一个不能修改所指向的元素的迭代器
    it = phone_book.find(name); // 查找关键字为name的容器元素
    if (it == phone_book.end()) // 判断是否找到
        cout << name << ": not found\n"; // 未找到
    else
        cout << it->first << ": " << it->second << endl; // 找到
    return 0;
}

至此,读者应当对于STL中的容器有了一个整体上的把控,知晓各容器的基本特征。

最后更新于