C++顺序容器与关联容器的部分基础知识

一、基本概念

1-1 概述

1 容器：类模板，通用数据结构（容器元素的组织方式）

2 迭代器：类似于指针，可依次存取容器中的元素(访问容器元素的媒介)

3 算法：函数模板，操作容器中的元素（操作方法）。

注意点：

• 算法模板实现了对元素类型的无视
• 如果容器中元素是类的对象，被插入的对象往往是复制品
• 许多容器往往需要对元素进行排序，此时往往要对相关的类重载==和<运算符

1-2 容器的分类

顺序容器(sequential container)

• 顺序容器中元素的顺序不受元素的值影响，而是与元素添加到容器中的位置对应。

关联容器(associative container)

• 关联容器中元素的顺序取决于键值（key value）

容器适配器(container adaptors )

• 与容器显著区别：容器适配器是没有迭代器的，也就是说STL中的算法模板是无法对容器适配器使用的。

二、顺序容器

2-1 顺序容器简介

顺序容器的特点：

共同点：

• 顺序访问容器中的元素都非常快

不同点：

• 在容器中插入与删除元素时间
• 随机的访问容器中元素的时间

使用方法：包含与容器名称一样的头文件名

vector(动态数组):大部分时间尾部增删元素具有较佳性能（O（1）），序列变长由于内部空间不够，重新分配

deque(双端队列):大部分时间二端增删元素具有较佳性能。

list(双端链表)：任何位置增删元素都是常数时间

2-2 顺序容器的容器适配器

? 适配器是库中一个通用的概念，除了容器适配器，还有函数适配器以及函数适配器以及迭代器适配器等。

简单讲，适配器使得某种东西表现的像另外一个东西。

例：stack adaptor takes a sequential container (other than array or forward_list) and makes it operate as if it were a stack.

three sequential container adaptors （3种顺序容器适配器）

• stack（栈）
• queue（队列）
• priority_queue (优先队列)
  • 在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 的行为特征。

注意点：

• 默认stack与queue适配器使用的容器时deque, priority_queue使用的容器时vector，当然也可以自己改变容器适配器的第二个参数指定使用的顺序容器，比如下面stack容器适配器使用的是vector，而不是默认的deque。
  • stack<string, vector>
• 与容器相比，容器适配器是没有迭代器的，也就是说STL中的算法模板是无法对容器适配器使用的。

2-3 顺序容器的用法查询

std::array

std::deque

三、关联容器

3-1 关联容器简介

关联容器与顺序容器的主要区别：

• 关联容器中元素的检索与存储都是通过key实现。

关联容器的特点：

共同点：

• 通过key能够实现高效的查找

不同点：

• 关联容器是 set 或者map

  • set是只有key，没有value。可以理解为只有单词表没有单词的解释的的字典。
  • map则是既有key，也有value。可以理解为一个字典既有单词也有每个单词的解释

• 关联容器的key是唯一或者key是可以重复的(multiple keys)

• 关联容器的元素是有序的 或者无序的

从表格中可以看到

• 关联容器只能是map或者key
• 通过名称中是否带有multi可以看出key是否重复
• 默认的关联容器元素是按照key进行排序的，但是如果名称中带有unordered时，则元素存储是无序的。

注意点：

• 有序的关联容器再使用时，指定的key的类型必须时可比较的。如果使用个对象作为key,那么必须去重载<使得key是可比较的。

参考资料

C++ primer 5th charpter9 & charpter 10

cplusplus

吐槽：时间过得真快，上次看C++的还是2年前。好多东西都忘光了。

-----20200704

C++顺序容器与关联容器的部分基础知识

原文：https://www.cnblogs.com/kfcuj/p/13235684.html