一、STL六大部件为：
（1）容器（Containers）
（2）分配器（Allocators）
（3）算法（Algorithm）
（4）迭代器（Iterators）
（5）适配器（Adapters）
（6）仿函数（Functors）
其相互之间的关系如下图：
通过一个例子了解这六大部件的基本用法：
在上例中，分配器可以不写，编译器会自动添加分配器。
二、复杂度的概念
在上述所介绍的复杂度中，只有n足够大时，不同复杂度之间的区别才能够被察觉。
三、前闭后开区间
从上图可以看出：end指的是最后一个元素的下一个元素。
四、C++11中的for循环的新的形式
上述代码中红色部分说明：{}也会形成一个数据聚合体。
五、C++11中的auto
六、容器的分类
容器大致可以分为序列式容器与关联式容器两大类。
（1）array
array的数据结构是一个两端封闭的数据空间，所以对于array必须指定其尺寸。这也就是说array是一个静态空间，一旦配置了就不能再改变了。
测试代码：
timestart = clock(); // 开始计时
qsort(c.data(),ASIZE,sizeof(long),compareLongs); // 快速排序，利用仿函数来指定排序规则
long* pItem = (long*)bsearch(&target,(c.data()),ASIZE,sizeof(long),compareLongs); // 二分法查找，利用二分法查找的前提是所查找的对象必须经过排序处理。
利用clock()-timestart就能够得到所耗费的时间。
（2）vector
vector的数据结构是允许在一侧进行数据操作的后进先出的数据结构。
array是一个静态空间，所以如果要扩充array的空间就必须执行以下操作：
<1>配置一个新的更大的空间；
<2>将旧的空间中的数据依次迁移至新的空间中；
<3>将旧的数据空间释放。
vector则会动态的扩充vector空间。vector以两个迭代器start和finish分别指向配置的连续空间中的已经使用的范围，并以迭代器end_of_storage指向整块连续空间（包括备用空间）的尾端。一般vector中配置的空间可能比实际需要的空间更大一些，以备将来可能的扩充。动态增加大小，并不是在原空间之后接续新的空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原空间中的数据拷贝至新的空间，然后再在新的空间上构造新的元素，并释放原有空间。所以对于vector中的操作，一旦其配置空间发生重新设置，指向原有vector的所有迭代器就会全部失效。
vector的常用函数：begin、end、size、capacity、empty、front、back、push_back、erase、resize、insert等。
vector的迭代器：vector的迭代器应能够提供*、->、++、--、+、-、+=、-=操作。普通的指针就能够提供上述操作，同时还能够满足vector对于随机存取的需求，所以普通的指针都可以作为vector的迭代器。vector提供的Random Access iterators。
vector::iterator vciterator1; 其类型就是int*
vector::iterator vciterator2; 其类型就是X*
注意以下auto的使用：
auto所指代的实际是一种迭代器类型。
利用find算法得到vetor容器中与target相同的字符串，返回其在容器中的位置。
（3）list
list的数据结构相对于vector所采用的数据结构更加复杂，其优势在于每次插入或删除一个元素，就会配置或释放一个元素空间，因此list对于空间的运用绝对的精准，一点也不浪费。
list数据结构可以看做是一个双向链表，其链表节点分别指向起一个节点和后一个节点。因为list节点不能保证在存储空间上是连续存在的，所以不能够像vector一样用普通指针作为迭代器。list迭代器必须有能力进行正确的operator==、operator!= 、operator*(取的是节点的数据值,reference)、operator->（取用的是节点的成员，pointer）、operator++（节点前移）、operator--（节点后退）。list是一个双向链表，所以其迭代器必须具备前移、后移能力。list提供的是一个Bidirectional iterators。
list的一个重要的性质：插入insert和接合操作splice都不会造成原有的list迭代器失效；list的元素删除操作（erase）只有使指向被删除元素的迭代器失效，其余不受影响。
常用函数：
void push_back(const T& x) // 插入要素作为尾节点
void push_front(const T& x) // 插入要素作为头结点
iterator erase(iterator position) // 删除迭代器所指向的节点
void pop_back() // 移除尾节点
void pop_front() // 移除头结点
void clear() // 清空
void remove(const T& value) // 将数值为value的所有元素移除
void unique() // 移除数值相同的连续元素。注意：只有“连续且相同的元素”，才会被移除只剩一个
void splice(iterator position,list& x) // 将x接合于position所指位置之前
void splice(iterator position, list&, iterator i) // 将i所指向的元素结合于position所指向的元素之前，position和i可以指向同一个list
void merge(list& x) //将x合并到*this身上。两个list的内容都必须首先经过增序排列。
void reverse() // 将this中的内容逆向重置
void sort() // list 不使用STL算法sort(),使用自身定义的sort函数。因为STL中的sort算法只接受Random Access iterators。
看一下以下例子：
int iv[5] = {5,6,7,8};
listilist2{iv,iv+5};
// 一个ilist中存放0 2 99 3 4
ite = find(ilist.begin(),ilist.end(),99);
ilist.splice(ite,ilist2); // 0 2 5 6 7 8 99 3 4
ilist.reverse(); // 4 3 99 8 7 6 5 2 0
ilist.sort(); // 0 2 3 4 5 6 7 8 9 99
（4）forward-list
（5）slist
slist是一种单向链表。slist与list的区别在于：slist的迭代器属于单向的Forward iterator。list的迭代器属于双向的Bidirectional iterator。因此slist的功能会受到一定的限制，但是单向链表所占用的空间更小，一些操作的效率更高。
slist与list相似，其插入（insert）、移除（erase）、接合（splice）等操作不会造成原有迭代器的失效。在STL中，插入操作都会将新的元素插入到指定位置之前。作为一个单向链表，slist没有办法可以回头定位之前的要素，必须从头开始。所以除非slist起点处附近的区域之外，在其他位置进行插入或移除操作都会比较复杂。
slist不提供push_back操作，提供push_front操作，因此slist的元素次序会和元素插入进来的次序相反。
（6）deque
deque是一个双向开口的连续线性空间，可以在头尾两端分别进行元素的插入与删除操作。
deque和vector的最大差异，一在于deque允许在头部进行元素的插入或删除操作；二是deque是没有容量capacity的观念的。deque是动态地以分段连续空间组合而成的，随时可以添加一段新的空间并将其链接起来。所有deque没有必要提供空间保留(reserver)功能。
deque的中控器：
deque在逻辑上看来是一个连续空间，由此可以联想到array与vector。其中，array无法成长；vector只能够在尾部增长，而且其在尾部增长也是一个表面的假象，其过程实际是：<1>另外寻觅更大的存储空间；<2>将原数据复制到新的存储空间；<3>释放原有空间。如果vector在分配空间时都会留有一定的余量，那么vector的成长的代价就太大了！
deque是由一段一段的定量连续空间组成，一旦有必要在deque的前端或尾端进行增加新的空间，便会配置一段定量连续空间，并将此空间串接在整个deque的头端或尾端。
deque的最大任务在于在这些分段的定量连续空间上，维护其整体连续的假象，并且能够提供一个随机存取的接口，避免vector的三部曲。为了能够实现以上，deque需要一个复杂的迭代器架构。deque使用一块map（不是STL中的map容器）作为主控。此处的map是一小块连续空间，其中每一个中元素(node，节点)都是一个指针，指向另外一段较大的连续线性空间（缓冲区）。缓冲区才是deque的存储主体。
deque的迭代器应当具有的结构：（1）必须能够指出缓冲区在哪儿;（2）必须能够判断迭代器是否已经处于其所在缓冲区的边缘。如果位于边缘，那么一旦前进或者后退就会跳至下一个或者上一个缓冲区中。为此deque必须能够实现对map中控的控制。迭代器结构：cur、first、last、node
deque的常用操作：
void push_back(const T& x) // 插入要素作为尾节点
void push_front(const T& x) // 插入要素作为头结点
iterator erase(iterator position) // 删除迭代器所指向的节点
void pop_back() // 移除尾节点
void pop_front() // 移除头结点
void clear() // 清空
(7)stack
stack是一种先进后出的数据结构，只有一个出口。stack允许新增元素、移除元素、取得最顶端元素。但是除了最顶端之外，没有任何办法可以存取stack中的其他元素。也就是说stack不允许存在遍历行为。这意味着stack是没有迭代器的。
stack是以某种现有容器作为底部结构，将其接口改变，使其符合“先进后出”的特性，以此形成一个stack。deque是一个双开口的数据结构，如果以deque作为底部结构并将其头端开口封闭，就形成了一个stack。STL在缺省情况下就是采用deque作为其底部容器。由于stack是以其底部容器完成所有功能，因此被称之为adapter（配接器）。STL stack往往不被归类为容器，而被归类为container adapter。
（8）queue
queue是一个先进先出的数据结构，有两个出口。queue允许新增元素、移除元素、从最低端加入元素、取出最顶端元素，但是除了最底端可以加入元素、最顶端可以取出元素外，没有任何其他方法可以存取queue中的其他元素。queue不存在遍历行为。
queue是以某种现有容器作为底部结构，将其接口改变，使其符合“先进先出”的特性，以此形成一个queue。deque是一个双开口的数据结构，如果以deque作为底部结构并将其头端入口和底端出口封闭，就形成了一个queue。STL在缺省情况下就是采用deque作为其底部容器。queue同样是一种适配器。queue没有迭代器。
以上介绍的都是序列式容器，关联式容器与序列式容器的本质区别是：序列式容器通过元素在容器中的位置顺序存储和访问元素；关联式容器通过键（key）来存储与访问容器中的元素。
常见的关联式容器包括：map、set、multimap以及multiset。
map：关联数组，元素通过键值对来存储和读取。
set：大小可变的集合，支持通过键实现的快速读取。
multimap：支持同一个键多次出现的map类型。
multiset：支持同一个键多次出现的set类型。
关联容器共享大部分序列容器的操作，不提供：front、push_front、pop_front 、back、push_back、pop_back。
（9）Map/Multimap
map容器的定义：
map<k,v>a
map<k,v>m(m2) 创建m2的副本，m与m2必须具有相同的键类型和值类型
map<k,v>m(b,e) 创建map类型的对象m，存储迭代器b和e标记的范围内的所有元素的副本。
map定义的类型：
map<k,v>::key_type 在map容器中，用作索引的键的类型
map<k,v>::mapped_type 在map容器中，键所关联的值得类型
map<k,v>::value_type 一个pair类型，其first元素具有Map::key_type类型，second元素则为map<k,v>::mapped_type类型
使用下标访问map对象：
map<string,string>A;
A[“aa”] = 1；
将会如下执行：
(1)在A中查找键为aa的元素，未找到;
(2)将新的键值对插入A中;
(3)读取新插入的元素，将该值赋值为1。
由此可见：如果该键已经存在与容器中，则map的下标运算与vector的下标运算是相同的，返回该键所关联的值。当所查找的键不存在时，map容器会为该键创建一个新的元素。
利用下标进行map元素的读取是非常不可取的，如果该键不存在与map容器中，那么下标操作将会插入一个新的要素。如何判断某一个键值是否存在与map容器中？
方法一：使用count方法
使用count获取map中K值的出现次数。在map中，K值出现的次数只能是0或1，所以可以利用该方法判断map中某个值是否存在。
int num = 0;
if(Wordcount.count(“AAA”))
{
// 插入
num = Wordcount[“AAA”];
}
方法二：使用find方法
int occurs = 0;
map<string,int>::iterator it = Wordcount.find(“AAA”);
If(it != Wordcount.end())
{
num = it->second;
}
map要素的插入：
（1）wordcount.insert(map<string,int>::value_type(“A”,1));
（2）wordcount.insert(make_pair(“A”,1));
（3）typedef map<string,int>::value_type valType;
wordcount.insert(valType(“A”,1));
map元素的删除：
m.erase(k)：删除m中键为k的元素，返回size_type类型的值，表示删除的元素的个数。
m.erase(p)：删除m中迭代器p所指向的元素，p不能为m.end()，返回值为void。
m.erase(b，e) ：一定范围内的元素的删除，b需在e的前方，返回值为void。
multimap的特性与用法与map完全相同，唯一的差别在于multimap允许存在重复的键值。
(10)set/multiset
set不支持下标[]操作符，而且没有定义mapped_type类型。在set容器中，value_type不是pair类型，而是key_type相同的类型，其指的都是set中存储的元素类型。set中存储的元素仅仅是键，而没有所关联的值。在set中插入元素：
(1)set<string> strset1;
strset1.insert(“A”);
(2)set<int> niset2;
niset2.insert(nivec.begin(),nivec.end());
在set中查找元素：
niset.find(1); // 返回值1存在，0不存在
(11)unordered_multiset/unordered_multimap
上述两种容器都是用到hash table。hash table将一个key映射到一个数组的下标，数组的每一个元素都是一个链表，链表中存放的是value值。数组中存放的value的个数除以数组的长度就是load factor，表示hash table已经加载的程度。load_factor()返回当前的加载因子。max_load_factor为最大加载因子，如果加载因子超过这个值将会引起rehash。
unordered_multiset与set相似，都不支持下标操作。
(11)分配器
默认的分配器:
直接使用分配器：
不建议直接使用分配器。
网友评论