标准库-容器浅析-1-概述
- 2021-04-25
概述
容器的理解
容器被定义为：在数据存储上，有一种对象类型，它可以持有其他对象或者指向其他对象的指针，这种对象类型就叫做容器。容器就是保存其他对象的对象，还包含了一系列处理其他对象的方法，因为这些方法在程序设计上经常被用到，所以容器也体现出了一个好处，就是“容器类是一个对特定代码重用问题的良好的解决方案”[1]
容器是随着面向对象的诞生而提出的，容器类在面向对象中特别重要，甚至被认为是面向对象的基础。在现在几乎所有的面向对象语言中都伴随着一个容器集。[1]
容器必须提供某种访问元素的方式，便于其他代码使用其中的元素。容器应提供一种能够遍历元素的方式，保证它不会周而复始地访问同一个元素。从单一职责原则来看，为了避免模糊容器高效存储数据的主要职责，把容器的遍历行为抽取为单独对象可能是比较好的解决方案。
迭代器模式[2]
迭代器介绍
迭代器是一种行为设计模式，能让你在不暴露底层表现形式的情况下遍历集合种所有的元素。
迭代器模式适用的场景
-
当集合背后为复杂的数据结构， 且你希望对客户端隐藏其复杂性时 （出于使用便利性或安全性的考虑）， 可以使用迭代器模式。
迭代器封装了与复杂数据结构进行交互的细节， 为客户端提供多个访问集合元素的简单方法。 这种方式不仅对客户端来说非常方便， 而且能避免客户端在直接与集合交互时执行错误或有害的操作， 从而起到保护集合的作用。
-
使用该模式可以减少程序中重复的遍历代码。
重要迭代算法的代码往往体积非常庞大。 当这些代码被放置在程序业务逻辑中时， 它会让原始代码的职责模糊不清， 降低其可维护性。 因此， 将遍历代码移到特定的迭代器中可使程序代码更加精炼和简洁。
-
如果你希望代码能够遍历不同的甚至是无法预知的数据结构， 可以使用迭代器模式。
该模式为集合和迭代器提供了一些通用接口。 如果你在代码中使用了这些接口， 那么将其他实现了这些接口的集合和迭代器传递给它时， 它仍将可以正常运行。
迭代器的实现方式
-
声明迭代器接口。该接口必须提供至少一个方法来获取容器的下一个元素。但是为了使用方便，可以添加一些其他方法。
- 对于C++而言，标准库的迭代器通过重载了++操作符来获取下一个元素。
- 对于Java而言，接口Iterator提供了next来获取下一个元素。
- 对于Python而言，定义了__iter__()和__next__()方法的对象被视为iterator，通过__next__获取下一个元素。
-
声明容器接口并且描述一个获取迭代器的方法。其返回值必须是迭代器接口。如果计划拥有多组不同的迭代器，可以声明多个类似的方法。
- 对于C++而言，标准库的容器提供了begin(), end(), cbegin(), cend(), rbegin(), rend()来获取迭代器
- 对于Java而言，接口Collection提供了iterator()方法获取迭代器。
- 对于Python而言，iterator对象提供了__iter__()方法获取迭代器。
-
为希望使用迭代器进行遍历的容器实现具体迭代器类。迭代器对象必须与单个容器实体链接。链接关系通常通过迭代器的构造函数建立。
-
在你的容器类中实现容器接口。其主要思想是针对特定容器为客户端提供创建迭代器的快捷方式。容器对象必须将自身传递给迭代器的构造函数来创建两者之间的链接。
-
检查客户端代码， 使用迭代器替代所有容器遍历代码。每当客户端需要遍历容器元素是都会获取一个新的迭代器。
容器框架
容器类型上的操作
容器类型上的操作形成了一种层次：
- 某些操作时所有容器都提供的
- 另外一些操作仅针对顺序容器、关联容器或无序容器
- 还有一些操作只适用于一小部分容器
C++ STL架构[3]
C++ STL有六大组件：分配器、容器、迭代器、算法、仿函数、适配器
C++ STL的基本观念是数据和操作分离。数据由容器加以管理，操作由可定制的算法定义，迭代器在两者之间充当粘合剂，使任何算法都可以和任何容器交互运作。容器数据存储的底层由分配器完成，迭代器了解容器的内部结构，可以访问容器的分配器，能够将“前进到下一个元素”的意图转换为合适的操作。
从某种意义上来看，STL将数据和算法分开对待而不是合并考虑与面向对象程序设计最初思想矛盾，但是这么做由很重要的原因，容器和各种算法结合起来在很小的框架里拥有非常大的弹性。
所有容器都提供的
| 类型 | 类型 |
|---|---|
| 类型别名 | |
| iterator | 此容器的迭代器类型 |
| const_iterator | 可以读取元素，但不能改变元素的迭代器类型 |
| size_type | 无符号整型，足够保存此种容器类型最大可能的大小 |
| difference_type | 带符号整型，足够保存两个迭代器之间的距离 |
| value_type | 元素类型 |
| reference | 元素的左值类型,与value_type&相同 |
| const_reference | 元素的const左值类型, 与const value_type& 相同 |
| 构造函数 | |
| C c | 默认构造函数, 构造空容器 |
| C c1(c2) | 拷贝构造容器 |
| C c(b, e) | 构造C， 将迭代器b和e指定范围内的元素拷贝到c |
| C c(a, b, c, d, …) | 列表初始化 |
| 赋值和swap | |
| c1 = c2 | 将从c1中的元素替换为c2中的元素 |
| c1 = {a, b, c, d, …} | 将c1替换为列表中元素 |
| a.swap(b) | 交换a和b的元素 |
| swap(a, b) | 交换a和b的元素 |
| 大小 | |
| c.size() | c中元素的数目 |
| c.max_szie() | c中可以保存的最大元素数目 |
| c.empty() | 若c中存储了元素，返回false，否则返回true |
| 关系运算符 | |
| ==, != | 所有容器都支持 |
| <, <=, >, >= | 无序容器不支持 |
| 获取迭代器 | |
| c.begin(), c.end() | 返回iterator |
| c.cbegin(),c.cend() | 返回const_iterator |
C++采用模板来处理容器，STL对定义的通用容器分为两类：顺序容器、关联式容器。
顺序容器(sequential container) 为程序员提供了控制元素存储和访问顺序的能力，这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。
主要包括: vector、deques、list，也可以把string和array归入此类。
关联容器