标准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另外提供vectorlistdequedouble-ended queue)。它们的区别在于訪问元素的方式,以及加入或删除元素相关操作的执行代价。

标准库还提供了三种容器适配器(adapter),所谓适配器是依据原始的容器类型所提供的操作,通过定义新的操作接口,来适应基础的容器类型。顺序容器适配器包含stackqueuepriority_queue等序列式容器。当中stackqueue因为仅仅是将deque改头换面而成,技术上被归类为一种配接器(adapter),priority_queue是有优先级管理的队列

 

. Vector

1.vector的基本概念

vector是标准C++建议替代C数组的动态数组模型,它维护的是一个连续线性空间。

vector所採用的数据结构很easy:线性连续空间。它以两个迭代器startfinish分别指向配置得到的连续空间中眼下已被使用的范围,并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端。

vector的实现技术,关键在于其对大小的控制以及又一次分配时的数据移动效率。一旦vector原有空间用完,假设client每新增一个元素,vector内部就仅仅扩充一个元素的空间,实为不智。由于所谓扩充控件(不论多大),是配置新空间(malloc/拷贝移动数据(memcpy/释放旧空间(free的大project,时间成本非常高,应该採用某种未雨绸缪的空间配置策略。

注意,所谓动态添加大小,并非在原空间之后接续新空间(由于无法保证之后尚有可供配置的空间),而是每次再分配原大小两倍的内存空间。因此,对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)valnum份副本代替向量元素

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)xn份副本插入到迭代器i所指定的位置之前

insert(i,start,end)把迭代器startend所指定的范围内的值插入到迭代器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删除全部反复的元素使链表中没有反复元素

注意vectordeque支持随机訪问list不支持随机訪问因此不支持[]訪问

 

.deque

1.deque的基本概念

vector是单向开口的连续线性空间,deque则是以中双向开口的连续线性空间。所谓双向开口,意思是能够在头尾两端分别做元素的插入和删除操作。从技术的角度而言,vector当然也能够在头尾两端进行操作,可是其头部操作效率奇差、令人无法接受。

dequevector的最大差异,一在于deque同意于常数时间内对头端进行元素的插入或移除操作,二在于deque没有所谓容量(capacity)观念,由于它是动态地以分段连续空间组合而成,随时能够添加一段新的空间并链接起来。换句话说,像vector那样“因旧空间不足而又一次配置一块更大空间,然后复制元素,再释放旧空间”这种事情在deque中是不会发生的。也因此,deque没有必要提供所谓的空间预留(reserved)功能。

尽管deque也提供Random Access Iterator,但它的迭代器并非普通指针,其复杂度和vector不可同日而语,这当然涉及到各个运算层面。因此,除非必要,我们应尽可能选择使用vector而非deque。对deque进行的排序操作,为了最高效率,可将deque先完整拷贝到一个vector身上,将vector排序后(利用STLsort算法),再复制回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的顺序容器适配器stackqueuepriority_queue

stack

1.stack的基本概念

stack是一种后进先出(First In Last OutFILO)的数据结构,它仅仅有一个出口。stack同意新增元素、移除元素、取得最顶端元素。但除了最顶端外,没有不论什么其它方法能够存取stack的其它元素,换言之,stack不同意随机訪问。

STLdeque作为stack的底层结构,对deque封闭期头端开口,稍作改动便形成了stack   

将元素插入stack的操作称为push,将元素弹出stack的操作称为popstack全部元素的进出都必须符合“后进先出”的条件,仅仅有stack顶端的元素,才有机会被外界取用。stack不提供走訪功能,也不提供迭代器。

2.容器适配器堆栈类std::stack成员函数

#include<stack>

stack实现后进先出的操作

std::stack<type,container> stk;

type为堆栈操作的数据类型

container为实现堆栈所用的容器类型,默认基于deque,还能够std::vectorstd::list

比如std::stack<int,std::list<int>> IntStack;

其成员函数例如以下:

top()返回顶端元素的引用

push(x):将元素压入栈(顶)

pop()弹出(删除)顶端元素

 

queue

1.queue的基本概念

queue是一种先进先出(First In First OutFIFO)的数据结构,它有两个出口。queue同意新增元素、移除元素、从最底端增加元素、取得最顶端元素。但除了最底端能够增加、最顶端能够取出,没有不论什么其它方法能够存取queue的其它元素。换言之,queue不支持随机訪问。

STLdeque作为queue的底层结构,对deque封闭其底端的出口和前端的入口,稍作改动便形成了queue

2.容器适配器队列类std::queue成员函数

#include<queue>

queue实现先进先出的操作

std::queue<type,container> que;

type为队列操作的数据类型

container为实现队列所用的容器类型,仅仅能为提供了push_front操作的std::dequestd::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-treeRB-treeAA-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

C++模板的编译问题

标准C++中的STL容器类简单介绍,布布扣,bubuko.com

标准C++中的STL容器类简单介绍

上一篇:教你用Java安全有效的实现两星期内自动登陆功能-Session


下一篇:Java 二进制表示整负数算法