map的特性: – 所有元素都会根据元素的键值自动排序. – 所有的元素都是pair,同时拥有实值和键值,pair的第一元素被视为键值,第二元素被视为实值,map不允许两个元素有相同的键值. multimap和map的操作类似,唯一区别multimap键值可重复. map和multimap都是以红黑树为底层实现机制. map的使用 //构造 map<T1, T2> mapTT;//map默认构造函数 map(const map &mp);//拷贝构造函数 //赋值 map& operator=(const map &mp);//重载等号操作符 swap(mp);//交换两个集合容器 //大小 size();//返回容器中元素的数目 empty();//判断容器是否为空 max_size();//容器最大数目 //迭代器 begin();//返回set容器迭代器的第一个 end();//返回set容器迭代器的最后一个 rbegin();//返回反向迭代器,以反向开始 rend();//返回反向迭代器到反向结束 cbegin();//同begin(),但属性为const cend();//同end(),但属性为const crbegin();//同rbegin(),但属性为const crend();//同rend(),但属性为const at();//访问元素 … “STL之map和multimap”

set set的特性: – 所有元素都会根据元素的键值自动被排序。 – set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。 – set不允许两个元素有相同的键值。 不可以通过set的迭代器改变set元素的值，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator. set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。 set的使用 //构造 set<T> setT; set(const set &st);//拷贝构造函数 //赋值 set& operator=(const set &st);//重载等号操作符 //迭代器 begin();//返回set容器迭代器的第一个 end();//返回set容器迭代器的最后一个 rbegin();//返回反向迭代器,以反向开始 rend();//返回反向迭代器到反向结束 cbegin();//同begin(),但属性为const cend();//同end(),但属性为const crbegin();//同rbegin(),但属性为const crend();//同rend(),但属性为const //大小 empty();//判断set容器是否为空 max_size();//返回set容器可能包含的元素最大个数 size();//返回当前set容器中的元素个数 … “STL之set和multiset”

queue 如同 stack 一般,在 STL 中队列也是作为一种适配器出现的. queue的特点: queue是队列,而队列是一种先进先出 (FIFO) 的数据结构.它允许在一端插入数据,在另一端删除数据.最先进入队列的数据最先出队列.除此之外,队列还允许访问队头元素和队尾元素,获取队列长度和判断空列队等操作. 队列不提供遍历的方法,也不提供迭代器. 几乎所有的序列式容器都支持在两端插入和删除数据元素的操作,若以某种序列式容器为底部结构,只保留其一端的插入接口和另一端的删除接口,使其符合先进先出的特性,便轻而易举的形成了一个队列. queue的使用 //构造 queue<T> queT; queue(const queue &que);//拷贝构造函数 //赋值 queue& operator=(const queue &que);//重载等号操作符 //存取 push(elem);//在末尾加入一个元素 pop();//删除第一个元素 front();//返回第一个元素 back();//返回最后一个元素 //大小 empty();//如果队列空则返回真 size();//返回队列中元素的个数

list容器是一个双向链表,而且还是一个循环的双向链表. 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相较于vector的连续线性空间，list显得复杂许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。 list的特点: – 采用动态存储分配，不会造成内存浪费和溢出 – 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素 – 链表灵活，但是空间和时间额外耗费较大 list有一个重要的性质,插入操作和删除操作都不会造成原有list迭代器的失效.这在vector是不成立的,因为vector的插入操作可能造成迭代器重新配置,导致原有的迭代器全部失效;甚至list元素的删除,也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。 list的使用 //构造 list<T> lstT;//list采用采用模板类实现,对象的默认构造形式： list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。 list(n,elem);//构造函数将n个elem拷贝给本身。 list(const list &lst);//拷贝构造函数。 //插入和删除 push_back(elem);//在容器尾部加入一个元素 pop_back();//删除容器中最后一个元素 push_front(elem);//在容器开头插入一个元素 pop_front();//从容器开头移除第一个元素 insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。 insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。 insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。 clear();//移除容器的所有数据 erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。 erase(pos);//删除pos位置的数据，返回下一个数据的位置。 remove(elem);//删除容器中所有与elem值匹配的元素。 //大小 size();//返回容器中元素的个数 … “STL之list”

stack是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。 有元素推入栈的操作称为:push,将元素推出stack的操作称为pop. 需要注意的是,stack没有迭代器.stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供遍历功能，也不提供迭代器。 stack的用法 //构造 stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式 stack(const stack &stk);//拷贝构造函数 //赋值 stack& operator=(const stack &stk);//重载等号操作符 //存取 push(elem);//向栈顶添加元素 pop();//从栈顶移除第一个元素 top();//返回栈顶元素 //大小 empty();//判断堆栈是否为空 size();//返回堆栈的大小 //C++11中添加 emplace(elem,…);//emplace直接传入Node的构造函数的参数,并将构造的元素加入栈中;省去了构造临时对象,减少了内存开销 swap();//swap将两个 stack的内容交换.这两个 stack的模板参数 T和 Container必须都相同

deque是一种双向开口的连续线性空间。 所谓的双向开口,就是可以在头尾两端分别做元素的插入和删除操作.当然,vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差,无法被接受. deque容器和vector容器最大的差异,一在于deque允许使用常数项时间对头端进行元素的插入和删除操作,二在于deque没有容量的概念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,像vector那样,”旧空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间”这样的事情在deque身上是不会发生的.也因此,deque没有必须要提供所谓的空间保留(reserve)功能. 虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针,其复杂度和vector不是一个量级.这当然影响各个运算的层面.因此,除非有必要,我们应该尽可能的使用vector,而不是deque.对deque进行的排序操作,为了最高效率,可将deque先完整的复制到一个vector中,对vector容器进行排序,再复制回deque. deque是由一段一段的定量的连续空间构成,一旦有必要在deque前端或者尾端增加新的空间,便配置一段连续定量的空间,串接在deque的头端或者尾端.deque最大的工作就是维护这些分段连续的内存空间的整体性的假象,并提供随机存取的接口,避开了重新配置空间/复制/释放的轮回,代价就是复杂的迭代器架构. 既然deque是分段连续内存空间,那么就必须有中央控制,维持整体连续的假象,数据结构的设计及迭代器的前进后退操作颇为繁琐.deque代码的实现远比vector或list都多得多. deque采取一块所谓的map(注意,不是STL的map容器)作为主控,这里所谓的map是一小块连续的内存空间,其中每一个元素(此处成为一个结点)都是一个指针,指向另一段连续性内存空间,称作缓冲区.缓冲区才是deque的存储空间的主体. ## deque的使用 //构造 deque<T> deqT;//默认构造形式 deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。 deque(n, elem);//构造函数将n个elem拷贝给本身。 deque(const deque &deq);//拷贝构造函数。 //赋值 assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。 assign(n, elem);//将n个elem拷贝赋值给本身。 deque& operator=(const deque &deq); //重载等号操作符 swap(deq);// 将deq与本身的元素互换 … “STL之deque”

vector: 向量容器,是一个能够存放任意类型(可以是char,int,double,string,或是自定义类)的动态数组,能够增加和压缩数据. 要使用vector前,需要包含头文件<vector>,并且由于vector 属于 std 命名域,因此需要通过命名限定. vector的容量 vector是一个动态增长数组. vector容量增长的本质：每次空间不够时，容器适配器会在另一个内存空间将待用空间多次的两倍扩张（1.2.4.8……..），安排好扩张内存后将所有值复制过去。 vector 对象的大小就是3个指针的大小。所有对于 vector 的操作都是基于这三个指针的。除了*与long随操作系统子长变化而变化外，其他的都固定不变(32位为4字节、64位为8字节) 。 vector的使用 //构造 vector<T> v; //采用模板实现类实现，默认构造函数 vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。 vector(n, elem);//构造函数将n个elem拷贝给本身。 vector(const vector &vec);//拷贝构造函数。 //如 使用第二个构造函数 我们可以… int arr[] = {2,3,4,1,9}; vector<int> … “STL之vector”

STL简介 STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。 STL它是由Alexander Stepanov、Meng Lee和David R Musser在1992年惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。 STL的版本很多，常见的有HP STL、PJ STL、 SGI STL等版本，主要流行的是SGI STL的版本。但它们的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。 在C++标准中，STL 被组织为下面的 13 个头文件：<algorithm>、<deque><functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。 算法 大家都能取得的一个共识是函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。 STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。 算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。 <algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。 <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。 <functional>中则定义了一些模板类，用以声明函数对象。 容器 在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。 经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模版类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。 容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>,<queue>组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。 向量(vector)：连续存储的元素<vector> 列表(list)：由节点组成的双向链表，每个结点包含着一个元素<list> … “关于C++的STL认知”