C++ STL容器总结

栏目: 编程工具 · 发布时间: 6年前

内容简介:Hints:在本文中,重点总结的是各个容器中增删查的算法时间复杂度。在c++中,容器指的是能够容纳各种数据类型的通用数据数据结构,是类模板。 比如set类模板:C++的容器主要分为三种:

Hints:在本文中,重点总结的是各个容器中增删查的算法时间复杂度。

在c++中,容器指的是能够容纳各种数据类型的通用数据数据结构,是类模板。 比如set类模板:

template <class _Key, class _Compare = less<_Key>,
          class _Allocator = allocator<_Key> >
class _LIBCPP_TYPE_VIS_ONLY set

C++的容器主要分为三种:

  • 顺序容器
  • 关联容器
  • 容器适配器

而访问容器元素我们需要迭代器(引入容器头文件就可以了,不需要单独因为头文件),迭代器有以下几个属性:

  • 用于指向顺序容器和关联容器的元素
  • 用法和指针类似
  • 有const(容器类名::iterator 变量名)和非const两种(容器类名::const_iterator 变量名)
  • 通过迭代器可以读取它指向的元素
  • 非const迭代器和可以修改其指向的元素

顺序容器

何为顺序容器,也就是说元素的位置是顺序插入的,插入位置与元素的值无关,核心是容器没有排序。 顺序容器都具有以下10个成员函数:

#返回迭代器
begin
end
rbegin  //返回指向最后一个元素的迭代器
rend
#返回元素引用
front
back
#其他
erase(删除区间时返回被删除元素后面的迭代器;也可删除一个或几个元素)
clear
push_back
pop_back

顺序容器有以下三种:

1.vector动态数组 头文件 <vetor>

元素在内存中是连续存放的。

随机存取时间:常数时间(因为可以通过下标直接访问到地址)。

在尾部增删元素通常是常数时间(正常是常数时间,如果超出了默认分配的元素个数,会重新分配存储空间,此时会消耗更多时间)。

在中间或者头部增删元素:o(n)(会移动其他元素的位置)。

迭代器类型:随机访问(支持下标访问、随机移动,例:a[i])。

查询时间:o(n)(因为没有排序,只能现行查找,效率较低)。

可见vector在中间或者头部增删元素性能较低。

优点:内存和C完全兼容、高效随机访问、节省空间

缺点:内部插入删除元素代价巨大、动态大小查过自身容量需要申请大量内存做大量拷贝。

构造函数:

vector();
 vector(int n);
 vector(int n, const T &a); //把n个元素初始化为a
 vector(iterator first,iterator last); //初始化为其他容器上区间[first,last)一致的内容

常用成员函数

void pop_back();
void push_back(const T &val);
int size();
T & font();
T & back();

deque[读:dek,之前经常读dkju:]双向队列 头文件 <deque>

元素在内存中连续存放(连续内存的容器有个明显的缺点,就是有新元素插入或老元素删除的时候,为了给新元素腾出位置或者填充老元素的空缺,同一块内存中的其他数据需要进行整体的移位,这种移位的拷贝代价有时是非常巨大的。deque实际上是分配到不同内存块,通过链表把内存块连在一起,再进行连续存放,是list与vector的折中)。

随机存取时间:常数时间(仅次于vector,因为有可能存在尾部的内存位置在头部之前的场景)。

在两端增删元素通常是常数时间。(deque不像vector没有容量,不需要重新分配内存空间。这是因为deque由动态分配的连续空间,即缓冲区,组合而成,随时可以增加一段新的空间链接起来。它没有必要像vector那样“因旧空间不足而重新分配2倍的空间,然后复制元素,再释放旧空间”。当重新分配缓冲区时,耗时增加)。

在中间插入:时间复杂度较高。

迭代器类型:随机访问(效率低于vector)。

查询时间:o(n)(原因同上)。

**优点:高效随机访问、内部插入删除元素效率方便、两端push、pop效率很高 **

**缺点:内存占用比较高 **

list双向链表 头文件 <list>

元素在内存中不连续分配(因为指针可以获取前后元素的地址), 所以不支持随机存取

在任何位置增删元素时间:常数时间。

查询时间:o(n)(原因同上)。

迭代器类型:双向(不支持下标访问,不支持迭代器的比较运算符,和+-运算符)

优点:任意位置插入删除元素常量时间复杂度、两个容器融合是常量时间复杂度

缺点:不支持随机访问、比vector占用更多的存储空间

常用成员函数:(注意这些在顺序容器中都是 list独有 的)

push_front
pop_front
sort   //不支持STLsort算法
remove
unique
merge
reverse
splice

特别说明,list的sort函数有无参和compare两个版本

list<T> classname
classname.sort(compare);  //compare自定义
classname.sort();

关联容器(迭代器类型:双向)

关联的意思就是元素是 排序 的。

插入与检索元素时间: o(log(N))(因为通过红黑二叉树实现,时间与平衡二叉树一致)。

需要注意的是,STL中有些算法比如sort,binary_search需要通过 随机访问 迭代器访问容器中的元素,因此list以及关联容器就不能支持该算法!

主要包括以下4种:

  • set
  • multiset
  • map
  • multimap

除了个容器都有的成员函数外,它们都有以下成员函数

find
lower_bound
upper_bound
equal_range
count
insert

map与set的不同点在于,map中存放的元素有且仅有两个成员变量,first(类似于key),second(类似于value),map可以根据first对元素排序和检索。

set与multiset的不同在于,后者允许存在相同值的元素。 map与multimap的不同在于,后者允许存在相同的first值的元素。

容器适配器(不支持迭代器)

这个概念听起来有点抽象,其实就是STL帮我们抽象了实际工作中所需要的数据操作方式。举个栗子,交流电可以有任意的传输电压,但是实际生活中我们只需要220v就够了,变压器帮我们实现了这个基本的功能。同理,容器的操作方式多种多样,但是其实我们只需要他们按照实际的一些规范来操作即可。

他们都有以下3个成员函数:

push
top
pop

STL中的排序,查找,变序算法都不适合容器适配器(因为容器适配器的元素位置不可随意改变,并且访问有一定的访问规则,不支持随机访问)。

stack 栈 头文件 <stack>

是一个有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项(栈顶项)。也即, 先进先出LIFO

可以用vector,deque,list(性能最差)实现,编译器缺省是用deque实现的。

比如,在程序调试中,错误堆栈就是一种应用。

queue 队列 头文件 <queue>

插入只可以在尾部进行,删除、检索和修改只允许从头部进行。 先进先出FIFO

queue由于pop,push发生在对头,所以不能用vector实现,可以用list,deque实现,编译器缺省用deque实现。

比如,应用于需要保证消息顺序性的场景,如消息队列。

priority_queue 优先级队列 头文件 <queue>

最高优先级元素总是第一个出列。

它需采用堆排序来保证元素总是在最前面,因此要求随机访问,所以不能使用list实现,可以用vector和deque实现,编译器缺省情况下用vector实现。

比如,操作系统的线程的调度算法,有的是按照优先级来调度的。


以上所述就是小编给大家介绍的《C++ STL容器总结》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Computing Patterns in Strings

Computing Patterns in Strings

Bill Smyth / Addison Wesley / 2003 / $ 75.00

The computation of patterns in strings is a fundamental requirement in many areas of science and information processing. The operation of a text editor, the lexical analysis of a computer program, the......一起来看看 《Computing Patterns in Strings》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具