c++ stl容器,stl容器类型
C标准中的STL容器类介绍-sabolasi-ITeye技术网站
C标准中STL容器类介绍
硅图形[计算机系统]公司硅地图[计算机系统]公司。
标准模板库标准模板库。
容器的概念
所谓STL容器就是实现一些最常用的数据结构。
容器是特定类型的对象的集合。根据容器中数据排列的特点，容器可以分为两种类型：顺序容器和关联容器。
迭代器是一种数据类型，它检查容器中的元素并遍历元素。它提供了一个类似指针的函数来访问容器的内容。
#包含迭代器
例如：
STD:vector int int vector；
STD:vector int:iterator first=int vector . begin()；
//begin()获取指向vector开头的迭代器，*首先获取第一个元素的值。
STD:vector int:iterator last=int vector . end()；
//end()获取迭代器，*last指向向量的末尾，* last获取最后一个元素的值
顺序容器
所谓的顺序容器，其中的元素可以排序，但不一定是有序的。数组是C语言内置的序列容器。STL还提供了vector、list和deque(双端队列)。两者的区别在于访问元素的方式和添加或删除元素的运行成本。
标准库还提供了三种容器适配器。所谓适配器，就是基于原容器类型提供的操作，通过定义新的操作接口来适应基本容器类型。顺序容器适配器包括堆栈、队列、priority_queue和其他顺序容器。其中，stack和queue在技术上被归类为一个适配器，因为它们只是对deque的改头换面。priority_queue是一个具有优先级管理的队列。
一.矢量
1.1 .向量的基本概念
Vector是标准C建议的一种动态数组模型，用来代替C数组，它保持了一个连续的线性空间。
vector采用的数据结构很简单：线性连续空间。它使用两个迭代器，start和finish，指向配置的连续空间中当前使用的范围，迭代器end_of_storage指向整个连续空间(包括备用空间)的结尾。
矢量实现的关键技术在于其大小控制和重分发时的数据移动效率。一旦vector的原始空间用完，如果每一个新元素都添加到客户端，只扩展vector内部一个元素的空间是不明智的。因为所谓的扩展控制(不管多大)是一个“配置新空间(malloc)/复制移动数据(memcpy)/释放旧空间(free)”的大工程，需要耗费大量的时间，所以要采取一些预防性的空间分配策略。
注意，所谓的动态增加大小并不是指原来的空间后面跟着一个新的空间(因为不能保证后面有空间可供配置)，而是指每次分配两倍于原来大小的内存空间。因此，一旦对向量的任何操作导致控件被重新配置，所有指向原始向量的迭代器都将失败。
因为向量维护了一个连续的线性空间，所以向量迭代器具有普通指针的功能，支持随机访问，也就是向量提供了随机访问迭代器。
2.向量类模板std:vector的成员函数
#包含矢量
std:矢量型vec
std:vector类型vec(大小)；
std:vector类型vec(大小，值)；
std:vector类型vec(my vector)；
std:vector类型vec(first，last)；
运算符：==、=、=、=、[]
Assign(first，last):用迭代器first，last指定的元素替换vector元素。
Assign(num，val):用val的num个副本替换向量元素。
At(n):相当于[]运算符，它返回向量中位置n的元素，由于它的越界检查，所以比[]索引访问更安全。
Front():返回向量中第一个元素的引用
Back():返回vector中最后一个元素的引用
Begin():返回向量中第一个元素的迭代器。
End():返回vector中最后一个元素的下一个迭代器(仅用作结束游标，不能解引用)。
Max_size():返回向量类型的最大容量(2 ^ 30-1=0x 3 ffffffff)
Capacity():返回向量的当前空间大小(=max_size，与向量的动态内存分配策略有关)
Size():返回向量中现有元素的数量(=容量)
Clear():删除vector中的所有元素
Empty():如果向量为空，则返回true
Erase(start，end):删除迭代器start end指定范围内的元素。
Erase(i):删除迭代器I指向的元素。
Erase()返回一个迭代器，指向删除的最后一个元素的下一个位置。
插入(I，x)；在迭代器I指定的位置前插入X。
Insert(i，N，X):在迭代器I指定的位置之前插入X的N个副本。
Insert(i，start，end):在迭代器I指定的位置之前插入迭代器start和end指定的范围内的值。
Push_back(x):将x推(插入)到向量的末尾
Pop_back():弹出(删除)向量的最后一个元素
Rbegin():返回一个反向迭代器，这个迭代器指向的元素穿过vector中的最后一个元素。
Rend():返回一个反向迭代器，指向vector中的第一个元素。
Reverse():反转元素顺序。
Resize(n，x):将vector的大小更改为n，并将新元素的初始值赋给x。
Swap(vectorref):交换两个向量的内容。
3.动态字符串类std:string
它是标准C建议的一种动态字符串模型，用来代替c string(以零结尾的字符数组)，可以简单的看成是vector char。
#包含字符串
STD:string str 1；
STD:string str 3(str 2)；
std:string str2(这是字符串)；
下面是和vector不一样的一般操作。
运算符：=
length():具有与size()函数相同的功能
Data():获取一个字符串指针
C_str():获取C风格的字符串指针。
c_str()的进程首先调用terminate()，然后返回数据()。所以，如果你对效率的要求很高，你的处理不一定要以/0结尾，那么你最好选择data()。但在一般的C函数中，应该使用const char*作为输入参数，使用c_str()函数。
运算符=:赋值运算符
Append():追加一个字符串
Replace():替换字符
Copy():将num个字符复制到str中(从index index开始)。
Find():在字符串中查找指定的字符，并返回基于0的索引号。
Rfind():反向查找
Find_first_of():查找包含子字符串中的任意字符，并返回第一个位置。
Find_first_not_of():查找子串中不包含它的任何字符，并返回第一个位置。
Find_last_of():查找包含子字符串中的任意字符，并返回最后一个位置。
Find_last_not_of():查找子串中不包含它的任何字符，并返回最后一个位置。
Substr(n1，len):从n1中获取长度为len的子字符串。
比较字符串(支持所有关系运算符)
比较比较字符串
运算符字符串内聚性
运算符=添加运算符
运算符==判断它们是否相等。
接线员！=判断是否不等于
运算符确定它是否小于
运算符从输入流中读取一个字符串。
运算符字符串被写入输出流。
Getline从输入流中读取一行。
二。目录
1.1 .列表的基本概念
与向量的连续线性空间相比，链表要复杂得多。与vector相比，它允许快速插入和删除，并且每次插入或删除一个元素时，都会配置或释放一个元素空间。所以list中空格的使用绝对准确，一点也不浪费。此外，对于在任何位置插入或删除元素，列表总是一个常数时间。
List不能再像vector一样使用普通指针作为迭代器，因为它的节点不能保证在存储空间中连续存在。列表迭代器必须能够指向列表的节点，并执行正确的操作，如递增、递减、值选择、成员访问等。所谓列表迭代器的“正确的递增、递减、取值、选成员”操作，就是递增指向下一个节点，递减指向上一个节点，取值时取节点的数据值，选成员时取节点的成员。
链表不仅是一个双向链表，还是一个循环双向链表。因此，它只需要一个指针就可以完成整个链表。由于链表是一个双向链表，迭代器必须有向前和向后移动的能力，所以链表提供了双向迭代器。
List有一个重要的属性：insert操作和splice操作都不会使原来的list迭代器失效。而在vector中则不成立，因为vector的insert操作可能会引起内存重配置，导致所有原迭代器失效。即使在list的擦除操作中，也只有指向被删除元素的迭代器失败，其他迭代器完全不受影响。
2.链表类模板std:list成员函数
#包含列表
std:列表类型lst
std:列表类型lst(大小)；
std:列表类型lst(大小，值)；
std:列表类型lst(my list)；
std:列表类型lst(名字，姓氏)；
下面是和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不支持，所以不支持[]访问！
三。双端队列
1.1 .得缺的基本概念
向量是单向开的连续线性空间，而德雀是双向开的连续线性空间。所谓双向开放，就是元素可以分别在头端和尾端插入和删除。从技术角度来说，vector当然可以在头尾两端运行，但是其头部运行效率极差，难以接受。
deque和vector最大的区别在于，deque允许在固定的时间内从头端插入或移除元素，而且deque没有所谓的容量概念，因为它是由分段的连续空间动态组成的，可以随时添加和链接一个新的空间。换句话说，像vector这种“因旧空间不足而重新配置一个更大的空间，然后复制元素，再释放旧空间”的事情，在德雀不会发生。因此，deque没有必要提供所谓的预留空间功能。
虽然deque也提供了随机访问迭代器，但是它的迭代器不是普通的指针，复杂度和vector也不一样，vector当然涉及到所有的运算层次。所以，除非必要，否则尽量选择使用vector而不是deque。对于deque的排序操作，为了达到最高的效率，可以先将deque复制到一个vector中，然后对vector进行排序(使用STL的排序算法)，再复制回deque。
德克是由一个定量的连续空间组成的。一旦需要在deque的前端或尾端增加新的空间，就会在整个deque的前端或尾端配置并串联一个定量的连续空间。deque最大的任务就是在这些分割的量化连续空间中维持整体连续的假象，并提供随机访问接口。以复杂的迭代器架构为代价，避免“重新配置、复制和释放”的循环。
2.deque类模板std:deque成员函数
#包含队列
std:deque类型deq
std:deque类型deq(大小)；
std:deque类型deq(大小，值)；
std:deque类型deq(my deque)；
std:deque类型deq(first，last)；
其成员职能如下：
运算符：[]用于访问双向队列中的单个元素。
Front():返回第一个元素的引用
Push_front(x):将元素X推(插入)到双向队列的头部。
Pop_front():弹出(删除)双向队列的第一个元素。
Back():返回最后一个元素的引用
Push_back(x):将元素X推(插入)到双向队列的末尾。
Pop_back():弹出(删除)双向队列的最后一个元素。
四。基于队列的顺序容器适配器堆栈和队列(priority_queue)
堆
1.1 .堆栈的基本概念
栈是一种先入先出(FILO)的数据结构，只有一个出口。Stack允许添加元素、移除元素和获取顶层元素。但是除了顶层，没有其他方法可以访问stack的其他元素。换句话说，堆栈不允许随机访问。
STL以deque为栈底结构，封闭期的deque前端开口稍加修改形成栈。
将元素插入堆栈的操作称为push，将元素从堆栈中弹出的操作称为pop。所有进出堆栈的元素都必须满足“后进先出”的条件。外界只能访问栈顶的元素。堆栈不提供访问函数或迭代器。
2.容器适配器堆栈类std:stack成员函数
#包括堆栈
实现堆栈的后进先出操作。
std:栈类型，容器stk
Type是堆栈操作的数据类型。
Container是用来实现栈的容器类型，默认基于deque，也可以是std:vector和std:list。
如STD: stackint，STD:listint int stack；
其成员职能如下：
Top():返回顶部元素的引用。
Push(x):将元素推入堆栈(顶部)
Pop():弹出(删除)顶部元素。
长队
1.1 .队列的基本概念
队列是具有两个出口的先进先出(FIFO)数据结构。允许queue添加元素、移除元素、从底部添加元素以及获取顶部元素。但是除了可以添加底部和取出顶部之外，没有其他方法可以访问队列的其他元素。换句话说，队列不支持随机访问。
STL以dequee作为队列的底层结构，关闭dequee底层的出口和前端的入口，经过一些修改形成队列。
2.容器适配器队列类std:queue成员函数
#包括队列
实现队列的先进先出操作。
std:队列类型，容器que
Type是队列操作的数据类型。
容器用于实现队列的容器类型只能是STD:dequee或std:list with push_front操作，默认基于STD:dequee。
其成员职能如下：
Front():返回队列头部元素的引用。
Back():返回尾部元素的引用。
Push(x):将元素X推到(插入)队列的末尾。
Pop():队列头元素出列(popup (delete)队列头元素)
优先级队列
1.1 .优先级队列的基本概念
Priority_queue是一个优先级队列，它允许用户为存储在队列中的元素设置优先级。这种队列不直接把新元素放在队列末尾，而是放在优先级比它低的元素前面，提供了一种插队策略。默认情况下，库使用运算符来确定它们之间的优先级关系。也就是权力大的人在队伍的最前面。
当使用priority_queue时，包括队列文件。
2.容器适配器队列类std:priority_queue成员函数
#包括队列
Priority_queue实现先进先出操作。
std:priority_queue类型，容器，组件优先级。
Type是队列操作的数据类型。
容器是用于实现队列的容器类型，可以是STD: vector和STD:dequee。默认值基于deque。
Comp是排队策略，缺省值是std:less，它被插入到比它小的元素之前。
例如STD: priority _ queue int，STD: vector int，STD:greater int intprique；
其成员职能如下：
Top():返回队列头部元素的引用(优先级最高)
Push(x):将元素推入队列(尾部)。
Pop():弹出(删除)队列头的元素(优先级最高)
关联容器
所谓关系容器，概念上类似于关系数据库(实际上简单得多):每一项数据(元素)都包含一个键值和一个实值。当一个元素被插入到关系容器中时，容器的内部数据结构(可能是RB-tree或hash-table)将根据其键值的大小和一些特定的规则将该元素放置在适当的位置。没有关联容器的头尾(只有最大元素和最小元素)，所以不会有push_back()、push_front()、pop_back()、pop_front()、begin()和end()这样的操作。
一般来说，关系容器的内部结构是一棵平衡二叉树，从而获得良好的搜索效率。平衡二叉树的类型有很多种，包括AVL树、RB树和AA树，其中RB树(红黑树)在STL中应用比较广泛。
的标准STL关联容器分为两类：set(集合)和map(映射类)，以及它们的派生物multiset(多键集合)和multimap(多键映射表)。这些容器的底层机制都是由RB-tree(红黑树)完成的。RB-tree也是一个独立的容器，但是不对外开放。
此外，SGI STL还提供了一个关联容器：hash table(哈希表)，以及以这个哈希表为底层机制完成的hash_set(哈希集)、hash_map(哈希映射表)、hash_multiset(哈希多键集)和hash_multimap(哈希多键映射表)。
地图
关系容器std:map成员函数
#包含地图
建立映射键-值映射
std:映射键，值
标准：映射键，值，组件
是关键值。
值是映射值。
Comp是可选的。它存储键值对的策略，比如std:less。键值映射对从小到大存储键值。
其成员职能如下：
Count():返回映射中键值等于key的元素的数量
Equal_range():函数返回两个迭代器3354，一个指向具有第一个键值的元素，另一个指向具有最后一个键值的元素。
Erase(i):在迭代器指向的位置删除元素(键-值对)。
Lower_bound():返回一个迭代器，指向映射中键值=key的第一个元素
Upper_bound():函数返回一个迭代器，指向映射中键值键的第一个元素。
Find(key):返回带有键值的键值对的迭代器，如果没有这样的映射，则返回结束游标end()。
请注意，当尝试引用不存在的键时，map的[]运算符将创建一个新的键-值对，值为null。
通用算法(适用于以上所有STL)
#包含算法
1.非修改序列算法：
2.改进的序列算法：
3.排序算法：
4.数值算法：
参考：
《Standard C++ Bible》
《The C++ Standard Library》
《The annotated STL sources》
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。