内容简介: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容器总结》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- Spring Boot Tomcat 容器化部署实践与总结
- 容器技术之容器镜像篇
- 多线程六 同步容器&并发容器
- 容器技术第一讲:容器入门篇
- Docker容器Centos容器安装openssh
- 房多多容器化和容器云实践
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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》 这本书的介绍吧!