C++标准库——顺序容器

容器是容纳特定类型对象的集合。顺序容器将单一类型元素聚集起来,并且根据位置来存储和访问这些元素。顺序容器中元素排列顺序与元素值无关,而是根据元素值添加到容器中的次序决定的。

标准库中有三种顺序容器,分别是vector,list与deque。其中vector支持随机的快速访问,因为vector中存放数据是在内存中连续存放的。在实际的实现中,vector会提前申请一块较大的内存空间(如果指定了大小,一般是指定大小的两倍),这样每次加入新的元素时不用再申请新的内存空间,提高效率。list容器是类似于链表的存储方式,因此插入元素效率较高,查找元素效率低,因为必须从头开始查找。deque是双端队列,也支持快速访问,同时在两端插入时有高效率。除了三种顺序容器以外,还有三种适配器,分别是stack,queue,priority_queue。适配器在基础的顺序容器基础上提供更高级的数据结构的行为,栈,队列,有优先级的队列。容器都是类模板,支持泛型编程,提供多种数据类型的支持。

容器有多种初始化的方式,包括初始化为另一个相同类型容器(容器类型与容器元素类型都需要相同)的副本,指定容器大小与内容的初始化,初始化为一段元素的副本等。其中初始化为一段元素的副本可以用另一个容器类型不同但是容器元素类型相容的容器来初始化。容器的元素类型有限制,必须可以赋值和复制。由于引用赋值与一般的赋值含义不同,因此引用不可以作为容器元素。IO对象不可以赋值和复制,也不可以作为容器对象。容器中都有迭代器,不同容器的迭代器可以支持的操作不同,一般迭代器都支持自增自减解引用判断是否相等(==和!=)等操作,vector与deque的迭代器支持加减n,迭代器相加减,比较等操作。迭代器一般是左闭合区间,表示左边的迭代器使用其指向的对象,右迭代器使用其前一个对象。容器中删除增加元素的操作都有可能导致迭代器失效,因此不要缓存(在一个变量中存放值)迭代器,具体失效与否与容器实现方式相关,迭代器实现与指针密切相关。

容器中定义了多个需要的类型,常用的有size_type,iterator,const_iterator等。此外容器提供了多种多样的操作,包括插入数据:push_back(),push_front(),insert()等。其中只用list和deque支持push_front()操作,vector不支持。Insert操作有多种调用方式。容器提供关系操作符的支持,但是具体的操作取决于容器元素类型。其他的删除,定义大小,赋值等操作都有支持。其中vector容器由于器特殊的实现,提供capacity和reserve函数,capacity返回容器可以存放的最大数据元素的个数,reserve可以指定可以存放的元素的个数。具体的容器选择可以根据应用的需求来确定,但是一般使用vector。因为其特殊的实现方式保证其高效率。string对象可以看做一个字符容器,支持顺序容器支持的很多操作,同时提供了很多自己独特的接口。

原文地址:https://www.cnblogs.com/libs5510/p/4814689.html