Maine

纵有疾风起,人生不言弃

C++ STL容器

容器是用来管理某一类对象的集合。其实就是用于存放数据的类模板。可变长的数组、链表、平衡二叉树等数据结构在 STL 中都被实现为容器。

容器中既可以存放基本类型的变量,也可以存放对象。当我们将一个容器类模板实例化为具体的容器类时,需要指明容器中存放的元素是什么类型的。对象或基本类型的变量被插入容器中时,实际插入的是对象或变量的一个复制。

STL 中的许多算法(即函数模板),如排序、查找等算法,在执行过程中会对容器中的元素进行比较。这些算法在比较元素是否相等时通常用运算符进行,比较大小通常用<运算符进行,因此,被放入容器的对象所属的类最好重载==<运算符,以使得两个对象用==<进行比较是有定义的。

还有一个值得注意的地方是:容器类会自动开辟和释放内存,我们无需new和delete操作。

c++ 中有两种类型的容器:顺序容器和关联容器:

顺序容器

顺序容器主要有:vector(可变长数组)、list(双向链表)、deque(双端队列)等。

其中 vector 表示一段连续的内存地址,基于数组实现,list 表示非连续的内存,基于链表实现。dequevector 类似,但是对于首元素提供删除和插入的双向支持。

顺序容器的特点是元素在容器中的位置与元素的值无关。将元素插入容器时,指定在什么位置插入,元素就会位于什么位置。

关联容器

关联容器主要有 mapsetmapkey:value 形式保存的,set 是单值。当然还有 multimapmultiset,区别在于 mapset 只能存放唯一的key值,multimapmultiset可以存放多个相同的key值。

再向关联容器插入元素时,容器会按一定的排序规则将元素放到适当的位置上,因此插入元素时不能指定位置。

默认情况下,关联容器中的元素是从小到大排序(或按关键字从小到大排序)的,而且用<运算符比较元素或关键字大小。因为是排好序的,所以关联容器在查找时具有非常好的性能。

除了以上两类容器外,STL 还在两类容器的基础上屏蔽一部分功能,突出或增加另一部分功能,实现了三种容器适配器:栈 stack、队列 queue、优先级队列 priority_queue

一些概念:

容器都是类模板。它们实例化后成为容器类。用容器类定义的对象称为容器对象

例如,vector 是一个容器,属于类模板, vector<int> 是一个容器类,就像我们之前说到的:

当我们将一个容器类模板实例化为具体的容器类时,需要指明容器中存放的元素是什么类型的。

在这里,我们指定了 int 类型。而 vector<int> a; 则定义了一个容器对象 aa 代表一个长度可变的数组,数组中的每个元素都是 int 类型的变量;vector<double> b; 定义了另一个容器对象 bab 的类型是不同的。

容器对象的运算

任何两个容器对象,只要它们的类型相同,就可以用 <、<=、>、>=、==、!= 进行词典式的比较运算。假设 a、b 是两个类型相同的容器对象,这些运算符的运算规则如下:

  • a == b :若 a 和 b 中的元素个数相同,且对应元素均相等,则a == b的值为 true,否则值为 false。元素是否相等是用==运算符进行判断的。
  • a<b: 规则类似于词典中两个单词比较大小,从头到尾依次比较每个元素,如果发生 a 中的元素小于 b 中的元素的情况,则a<b的值为 true;如果没有发生 b 中的元素小于 a 中的元素的情况,且 a 中的元素个数比 b 少,a<b的值也为 true;其他情况下值为 false。元素比较大小是通过<运算符进行的。
  • a != b:等价于 !(a == b)。
  • a > b:等价于 b < a。
  • a <= b:等价于 !(b < a)。
  • a >= b:等价于 !(a < b)。

成员函数

  • int size():返回容器对象中元素的个数。
  • bool empty():判断容器对象是否为空。

顺序容器和关联容器还有以下成员函数:

  • begin():返回指向容器中第一个元素的迭代器。
  • end():返回指向容器中最后一个元素后面的位置的迭代器。
  • rbegin():返回指向容器中最后一个元素的反向迭代器。
  • rend():返回指向容器中第一个元素前面的位置的反向迭代器。
  • erase(...):从容器中删除一个或几个元素。该函数参数较复杂,此处省略。
  • clear():从容器中删除所有元素。

如果一个容器是空的,则 begin()end() 的返回值相等,rbegin()rend() 的返回值也相等。

顺序容器还有以下常用成员函数:

  • front():返回容器中第一个元素的引用。
  • back():返回容器中最后一个元素的引用。
  • push_back():在容器末尾增加新元素。
  • pop_back():删除容器末尾的元素。
  • insert(...):插入一个或多个元素。该函数参数较复杂,此处省略。

具体容器类的使用我们后面会再细说。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注