c++ stl标准库(标准C++中的STL容器类简介)
SGI -- Silicon Graphics[Computer System] Inc.硅图[计算机系统]公司.
STL -- Standard Template Library 标准模板库 。
容器的概念
所谓STL容器 ,即是将最常运用的一些数据结构(data structures)实现出来 。
容器是指容纳特定类型对象的集合。根据数据在容器中排列的特性 ,容器可概分为序列式(sequence)和关联式(associative)两种 。
迭代器是一种检查容器内元素并遍历元素的数据类型 。它提供类似指针的功能 ,对容器的内容进行走访 。
#include<iterator>
例如:
std::vector<int> IntVector;
std::vector<int>::iterator first=IntVector.begin();
// begin()得到指向vector开头的Iterator,*first得到开头一个元素的值
std::vector<int>::iterator last=IntVector.end();
// end()得到指向vector结尾的Iterator,*last得到最后一个元素的值
序列式容器
所谓序列式容器 ,其中的元素都可序(ordered) ,但未必有序(sorted) 。数组为C++语言内置的序列容器 ,STL另外提供vector 、list 、deque(double-ended queue) 。它们的差别在于访问元素的方式 ,以及添加或删除元素相关操作的运行代价 。
标准库还提供了三种容器适配器(adapter) ,所谓适配器是根据原始的容器类型所提供的操作 ,通过定义新的操作接口,来适应基础的容器类型 。顺序容器适配器包括stack 、queue 、priority_queue等序列式容器 。其中stack和queue由于只是将deque改头换面而成 ,技术上被归类为一种配接器(adapter) ,priority_queue是有优先级管理的队列 。
一. Vector
1.vector的基本概念
vector是标准C++建议替代C数组的动态数组模型,它维护的是一个连续线性空间。
vector所采用的数据结构非常简单:线性连续空间 。它以两个迭代器start和finish分别指向配置得到的连续空间中目前已被使用的范围 ,并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端 。
vector的实现技术 ,关键在于其对大小的控制以及重新分配时的数据移动效率。一旦vector原有空间用完,如果客户端每新增一个元素 ,vector内部就只扩充一个元素的空间 ,实为不智 。因为所谓扩充控件(不论多大) ,是“配置新空间(malloc)/拷贝移动数据(memcpy)/释放旧空间(free) ”的大工程 ,时间成本很高 ,应该采用某种未雨绸缪的空间配置策略 。
注意 ,所谓动态增加大小 ,并不是在原空间之后接续新空间(因为无法保证之后尚有可供配置的空间) ,而是每次再分配原大小两倍的内存空间。因此 ,对vector的任何操作,一旦引起控件重新配置 ,指向原vector的所有迭代器就都失效了 。
由于vector维护的是一个连续线性空间 ,因此vector迭代器具备普通指针的功能,支持随机存取 ,即vector提供的是Random Access Iterators 。
2.向量类模板std::vector的成员函数
#include<vector>
std::vector<type> vec;
std::vector<type> vec(size);
std::vector<type> vec(size,value);
std::vector<type> vec(myvector);
std::vector<type> vec(first,last);
Operators:== 、!= 、<= 、>= 、< 、>、[]
assign(first,last):用迭代器first,last所指定的元素取代向量元素
assign(num,val):用val的num份副本取代向量元素
at(n):等价于[]运算符 ,返回向量中位置n的元素,因其有越界检查 ,故比[]索引访问安全
front():返回向量中第一个元素的引用
back():返回向量中最后一个元素的引用
begin():返回向量中第一个元素的迭代器
end():返回向量中最后一个元素的下一个迭代器(仅作结束游标 ,不可解引用)
max_size():返回向量类型的最大容量(2^30-1=0x3FFFFFFF)
capacity():返回向量当前开辟的空间大小(<= max_size ,与向量的动态内存分配策略相关)
size():返回向量中现有元素的个数(<=capacity)
clear():删除向量中所有元素
empty():如果向量为空 ,返回真
erase(start,end):删除迭代器start end所指定范围内的元素
erase(i):删除迭代器i所指向的元素
erase()返回指向删除的最后一个元素的下一位置的迭代器
insert(i,x);把x插入到迭代器i所指定的位置之前
insert(i,n,x):把x的n份副本插入到迭代器i所指定的位置之前
insert(i,start,end):把迭代器start和end所指定的范围内的值插入到迭代器i所指定的位置之前
push_back(x):把x推入(插入)到向量的尾部
pop_back():弹出(删除)向量最后一个元素
rbegin():返回一个反向迭代器 ,该迭代器指向的元素越过了向量中的最后一个元素
rend():返回一个反向迭代器 ,该迭代器指向向量中第一个元素
reverse():反转元素顺序
resize(n,x):把向量的大小改为n,新元素的初值赋为x
swap(vectorref):交换2个向量的内容
3.动态字符串类std::string
string是标准C++建议替代C字符串(以零结束的字符数组)的动态字符串模型 ,可以简单的看做vector<char> 。
#include<string>
std::string str1;
std::string str3(str2);
std::string str2("this is a string");
以下未列出与vector相同的通用操作 。
Operators:+ 、+=
length():和size()函数功能相同
data():取得字符串指针
c_str():取得C风格字符串指针
c_str()的流程是先调用terminate() ,然后再返回data() 。因此如果你对效率要求比较高 ,而且你的处理又不一定需要以/0的方式结束,最好选择data() 。但是对于一般的C函数中 ,需要以const char*为输入参数 ,要使用c_str()函数 。
operator=:赋值操作符
append():追加字符串
replace():替换字符
copy():拷贝自己的num个字符到str中(从索引index开始) 。
find():在字符串中查找指定字符,返回基于0的索引号
rfind():反向查找
find_first_of():查找包含子串中的任何字符,返回第一个位置
find_first_not_of():查找不包含子串中的任何字符 ,返回第一个位置
find_last_of():查找包含子串中的任何字符 ,返回最后一个位置
find_last_not_of():查找不包含子串中的任何字符,返回最后一个位置
substr(n1,len):得到字符串从n1开始的长度为len的子串
比较字符串(支持所有的关系运算符)
compare 比较字符串
operator+字符串衔接
operator+= 增加操作符
operator== 判断是否相等
operator!= 判断是否不等于
operator< 判断是否小于
operator>> 从输入流中读入字符串
operator<< 字符串写入输出流
getline 从输入流中读入一行
二.list
1.list的基本概念
相对于vector的连续线性空间 ,list就显得复杂许多 ,与向量(vector)相比, 它允许快速的插入和删除 ,且每次插入或删除一个元素 ,就配置或释放一个元素空间 。因此 ,list对于空间的运用绝对的精准 ,一点也不浪费。而且 ,对于任何位置的元素插入或元素移除 ,list永远是常数时间 。
list不再能够像vector那样以普通指针作为迭代器 ,因为其节点不保证在储存空间中连续存在 。list迭代器必须有能力指向list的节点,并有能力进行正确的递增 、递减、取值 、成员存取等操作。所谓“list迭代器正确的递增 、递减、取值 、成员取用 ”操作是指 ,递增时指向下一个节点 ,递减时指向上一个节点,取值时取的是节点的数据值 ,成员取用时取用的是节点的成员 。
list不仅是一个双向链表 ,而其还是一个环状双向链表 。所以它只需要一个指针,便可以完整实现整个链表。由于list是一个双向链表(double linked-list) ,迭代器必须具备前移 、后移的能力 ,所以list提供的是Bidirectional Iterators 。
list有一个重要性质:插入操作(insert)和合并操作(splice)都不会造成原有的list迭代器失效 。这在vector是不成立的 ,因为vector的插入操作可能造成记忆体重新配置 ,导致原有的迭代器全部失效 。甚至list的元素删除操作(erase)也只有“指向被删除元素 ”的那个迭代器失效 ,其他迭代器不受任何影响 。
2.链表类模板std::list成员函数
#include<list>
std::list<type> lst;
std::list<type> lst(size);
std::list<type> lst(size,value);
std::list<type> lst(mylist);
std::list<type> lst(first,last);
以下未列出与vector相同的通用操作 。
push_front(x):把元素x推入(插入)到链表头部
pop_front():弹出(删除)链表首元素
merge(listref):把listref所引用的链表中的所有元素插入到链表中 ,可指定合并规则
splice():把lst连接到pos的位置
remove(val):删除链表中所有值为val的元素
remove_if(pred):删除链表中谓词pred为真的元素
(谓词即为元素存储和检索的描述 ,如std::less<> ,std::greater<>那么就按降序/升序排列 ,你也可以定义自己的谓词)
sort():根据默认的谓词对链表排序
sort(pred):根据给定的谓词对链表排序
unique():删除链表中所有重复的元素
unique(pred):根据谓词pred删除所有重复的元素,使链表中没有重复元素
注意:vector和deque支持随机访问 ,而list不支持随机访问 ,因此不支持[]访问!
三.deque
1.deque的基本概念
vector是单向开口的连续线性空间,deque则是以中双向开口的连续线性空间 。所谓双向开口 ,意思是可以在头尾两端分别做元素的插入和删除操作 。从技术的角度而言 ,vector当然也可以在头尾两端进行操作,但是其头部操作效率奇差 、令人无法接受 。
deque和vector的最大差异 ,一在于deque允许于常数时间内对头端进行元素的插入或移除操作 ,二在于deque没有所谓容量(capacity)观念 ,因为它是动态地以分段连续空间组合而成 ,随时可以增加一段新的空间并链接起来 。换句话说 ,像vector那样“因旧空间不足而重新配置一块更大空间 ,然后复制元素 ,再释放旧空间 ”这样的事情在deque中是不会发生的。也因此 ,deque没有必要提供所谓的空间预留(reserved)功能 。
虽然deque也提供Random Access Iterator ,但它的迭代器并不是普通指针,其复杂度和vector不可同日而语 ,这当然涉及到各个运算层面 。因此 ,除非必要,我们应尽可能选择使用vector而非deque。对deque进行的排序操作 ,为了最高效率 ,可将deque先完整复制到一个vector身上,将vector排序后(利用STL的sort算法) ,再复制回deque 。
deque是由一段一段的定量连续空间构成 。一旦有必要在deque的前端或尾端增加新空间 ,便配置一段定量的连续空间 ,串接在整个deque的头端或尾端。deque的最大任务 ,便是在这些分段的定量连续空间上 ,维护其整体连续的假象 ,并提供随机存取的接口 。避开了“重新配置 、复制 、释放 ”的轮回 ,代价则是复杂的迭代器架构 。
2.双端队列类模板std::deque成员函数
#include<deque>
std::deque<type> deq;
std::deque<type> deq(size);
std::deque<type> deq(size,value);
std::deque<type> deq(mydeque);
std::deque<type> deq(first,last);
其成员函数如下:
Operators:[]用来访问双向队列中单个的元素
front():返回第一个元素的引用
push_front(x):把元素x推入(插入)到双向队列的头部
pop_front():弹出(删除)双向队列的第一个元素
back():返回最后一个元素的引用
push_back(x):把元素x推入(插入)到双向队列的尾部
pop_back():弹出(删除)双向队列的最后一个元素
四.基于deque的顺序容器适配器stack 、queue(priority_queue)
stack
1.stack的基本概念
stack是一种后进先出(First In Last Out ,FILO)的数据结构 ,它只有一个出口 。stack允许新增元素 、移除元素 、取得最顶端元素 。但除了最顶端外,没有任何其他方法可以存取stack的其他元素 ,换言之 ,stack不允许随机访问 。
STL以deque作为stack的底层结构,对deque封闭期头端开口 ,稍作修改便形成了stack 。
将元素插入stack的操作称为push ,将元素弹出stack的操作称为pop 。stack所有元素的进出都必须符合“后进先出 ”的条件,只有stack顶端的元素 ,才有机会被外界取用 。stack不提供走访功能 ,也不提供迭代器 。
2.容器适配器堆栈类std::stack成员函数
#include<stack>
stack实现后进先出的操作
std::stack<type,container> stk;
type为堆栈操作的数据类型
container为实现堆栈所用的容器类型 ,默认基于deque ,还可以为std::vector和std::list
例如std::stack<int,std::list<int>> IntStack;
其成员函数如下:
top():返回顶端元素的引用
push(x):将元素压入栈(顶)
pop():弹出(删除)顶端元素
queue
1.queue的基本概念
queue是一种先进先出(First In First Out ,FIFO)的数据结构 ,它有两个出口。queue允许新增元素 、移除元素、从最底端加入元素 、取得最顶端元素 。但除了最底端可以加入 、最顶端可以取出 ,没有任何其他方法可以存取queue的其他元素 。换言之 ,queue不支持随机访问。
STL以deque作为queue的底层结构 ,对deque封闭其底端的出口和前端的入口,稍作修改便形成了queue 。
2.容器适配器队列类std::queue成员函数
#include<queue>
queue实现先进先出的操作
std::queue<type,container> que;
type为队列操作的数据类型
container为实现队列所用的容器类型 ,只能为提供了push_front操作的std::deque或std::list ,默认基于std::deque
其成员函数如下:
front():返回队首元素的引用
back():返回队尾元素的引用
push(x):把元素x推入(插入)到队尾
pop():队首元素出列(弹出(删除)队首元素)
priority_queue
1.priority_queue的基本概念
priority_queue为优先级队列,它允许用户为队列中存储的元素设置优先级 。这种队列不是直接将新元素放置在队列尾部 ,而是放置在比它优先级低的元素前面 ,即提供了一种插队策略。标准库默认使用<操作符来确定他们之间的优先级关系 。即权重大的排在队首 。
使用priority_queue时,包含<queue>文件 。
2.容器适配器队列类std::priority_queue成员函数
#include<queue>
priority_queue实现先进先出的操作
std::priority_queue<type, container, comp> pri_que;
type为队列操作的数据类型
container为实现队列所用的容器类型 ,可以为std::vector,std::deque ,默认基于deque
comp为排队策略 ,默认为std::less<> ,即插到小于它的元素前
例如std::priority_queue<int,std::vector<int>,std::greater<int> > IntPriQue;
其成员函数如下:
top():返回队首(优先级最高)元素的引用
push(x):将元素推入(按插队策略插排)队列(尾部)
pop():弹出(删除)队首(优先级最高)元素
关联式容器
所谓关联式容器 ,概念上类似关联式数据库(实际上则简单许多):每项数据(元素)包含一个键值(key)和一个实值(value) 。当元素被插入到关联式容器中时 ,容器内部数据结构(可能是RB-tree ,也可能是hash-table)便依照其键值大小 ,以某种特定规则将这个元素放置于适当位置 。关联式容器没有所谓头尾(只有最大元素和最小元素) ,所以不会有push_back(),push_front() ,pop_back() ,pop_front(),begin() ,end()这样的操作 。
一般而言 ,关联式容器的内部结构是一个balanced binary tree(平衡二叉树),以便获得良好的搜索效率 。balanced binary tree有很多种类型 ,包括AVL-tree、RB-tree 、AA-tree ,其中广泛运用于STL的是RB-tree(红黑树) 。
标准的STL关联式容器分为set(集合)和map(映射类)两大类 ,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表) 。这些容器的底层机制均以RB-tree完成(红黑树)。RB-tree也是一个独立容器 ,但并不开放给外界使用 。
此外 ,SGI STL还提供了一个不在标准规格之列的关联式容器:hash table(散列表 ,哈希表) ,以及以此hash table为底层机制而完成的hash_set(散列集合) 、hash_map(散列映射表)、hash_multiset(散列多键集合) 、hash_multimap(散列多键映射表) 。
map
关联式容器std::map成员函数
#include<map>
map建立key-value映射
std::map<key, value> mp;
std::map<key, value, comp> mp;
key为键值
value为映射值
comp可选 ,为键值对存放策略 ,例如可为std::less<>,键值映射对将按键值从小到大存储
其成员函数如下:
count():返回map中键值等于key的元素的个数
equal_range():函数返回两个迭代器——一个指向第一个键值为key的元素 ,另一个指向最后一个键值为key的元素
erase(i):删除迭代器所指位置的元素(键值对)
lower_bound():返回一个迭代器 ,指向map中键值>=key的第一个元素
upper_bound():函数返回一个迭代器,指向map中键值>key的第一个元素
find(key):返回键值为key的键值对迭代器 ,如果没有该映射则返回结束游标end()
注意map的[]操作符 ,当试图对于不存在的key进行引用时,将新建键值对 ,值为空。
通用算法(对以上STL均适用)
#include<algorithm>
1.非修正序列算法:
2.修正序列算法:
3.排序算法:
4.数值算法:
参考:
《Standard C++ Bible》
《The C++ Standard Library》
《The annotated STL sources》
创心域SEO版权声明:以上内容作者已申请原创保护,未经允许不得转载,侵权必究!授权事宜、对本内容有异议或投诉,敬请联系网站管理员,我们将尽快回复您,谢谢合作!