c++学习网址 http://www.cplusplus.com/

源代码参考 http://www.cnblogs.com/lfsblack/archive/2012/11/10/2764334.html

stl 6大组件

vector

vector的工作原理是系统预先分配一块CAPACITY大小的空间，当插入的数据超过这个空间的时候，这块空间会让某种方式扩展，但是你删除数据的时候，它却不会缩小。

vector为了防止大量分配连续内存的开销，保持一块默认的尺寸的内存，clear只是清数据了，未清内存，因为vector的capacity容量未变化，系统维护一个的默认值。

vector动态增加大小，相对于array(array是静态空间，一旦配置了就不能改变)

下面是vs2013运行的情况，注意size 和 capacity的大小，可以再写各种例子

vector erase（）例子

*

#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <iterator> using namespace std; int main() { vector<int>array; array.push_back(100); array.push_back(300); // 删 array.push_back(300); array.push_back(300); // 删 array.push_back(300); array.push_back(300); // 删 array.push_back(500); vector<int>::iterator itor; for (itor = array.begin(); itor != array.end(); itor++) { if (*itor == 300) { itor = array.erase(itor); } } for (itor = array.begin(); itor != array.end(); itor++) { cout << *itor << " "; } return 0; }

---

有什么方法可以释放掉vector中占用的全部内存呢? 标准的解决方法如下 template < class T > void ClearVector( vector< T >& vt ) { vector< T > vtTemp; veTemp.swap( vt ); } 事实上，vector根本就不管内存，它只是负责向内存管理框架acquire/release内存，内存管理框架如果发现内存不够了，就malloc，但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存，因为内存分配在stl的底层：stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存)，所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <iterator> using namespace std; template <class T> void ClearVector(vector<T> &vt) { vector<T> vtTemp; // 局部变量，capacity=0,会被释放 vtTemp.swap(vt); // swap } int main() { vector<int> v; for (int i = 1; i < 5; i++) { v.push_back(i); //cout << v.size() << "," << v.capacity() << endl; } cout << v.size() << "," << v.capacity() << endl; cout << "-----clear-------" << endl; v.clear(); cout << v.size() << "," << v.capacity() << endl; cout << "-----释放内存-------" << endl; ClearVector(v); cout << v.size() << "," << v.capacity() << endl; return 0; } 一般的STL内存管理器allocator都是用内存池来管理内存的，所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量，而不是真的把内存归还给系统。这样做一是为了避免内存碎片，二是提高了内存申请和释放的效率——不用每次都在系统内存里寻找一番。

list

vector 采用连续线性空间，而list则不是，list每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。

list的一个重要性质：插入（insert）和结合（splice）操作不会使原list的迭代器失效，这在vector是不成立的。list的删除操作（erase）也只有“指向被删除元素”的那个迭代器失效，其它迭代器不受任何影响。

参考 http://blog.csdn.net/longshengguoji/article/details/8520891

deque

vector是连续的内存空间，只能尾端变长，所谓的增长也是个假，vector调整空间大小 经历一般是如下的三个步骤 （1） 寻觅更大的连续内存空间 （2）将原数据赋值过去 （3） 释放原空间

deque是逻辑上的连续（实际上的元素的内存空间并不连续），deque由一段一段的定量连续空间构成。当deque前端后后端要增加新空间是，便需要配置一段定量的连续空间，串接在deque的头或尾端，维持整体连续的假象，并提供随机存取的接口。避开了“重新配置，复制，释放”的轮回，代价则是复杂的迭代器构架。

stack

stack FIFO 底层可采用deque，也可采用list实现 stack 不提供迭代器，所有元素符合“先进后出”

queue

queue 类似 stack ，符合 “先进先出”，不提供迭代器

底层可采用deque，也可采用list实现

heap

heap 分为 min-heap , max-heap ,可以采用array实现 i位置的左孩子（2*i）,右孩子（2*i+ 1）

binary heap 采用完全二叉树

#include <algorithm> #include <vector> #include<iostream> using namespace std; int main() { int ia[] = {0,1,2,3,4,8,9,3,5}; vector<int> ivec(ia, ia + 9); make_heap(ivec.begin(), ivec.end()); // 建立堆 for (int i = 0; i < 9; i++) { cout << ivec[i] << " ";// 9 5 8 3 4 0 2 3 1 } cout << endl; ivec.push_back(7); push_heap(ivec.begin(), ivec.end()); // push_heap for (int i = 0; i < 9; i++) { cout << ivec[i] << " ";// 9 7 8 3 5 0 2 3 1 4 } cout << endl; pop_heap(ivec.begin(), ivec.end()); // pop_heap cout << ivec.back() << endl; // 9 ivec.pop_back(); for (int i = 0; i < 9; i++) { cout << ivec[i] << " ";// 8 7 4 3 5 0 2 3 1 } cout << endl; sort_heap(ivec.begin(), ivec.end()); // 排序 for (int i = 0; i < 9; i++) { cout << ivec[i] << " ";// 0 1 2 3 3 4 5 8 } cout << endl; return 0; }

priority_queue

大根堆的建立过程

---

priority_queue 以底部容器为根据，再加上heap处理规则，缺省情况下以vector为底部容器，所以stl可以 归为 container adapter.

priority_queue的使用： http://blog.csdn.net/qq_26437925/article/details/47864641 http://blog.csdn.net/qq_26437925/article/details/49529757

---

关联式容器：set 和 map 两大类，底层用红黑树实现。

RB-tree

https://github.com/forhappy/rbtree

二叉查找树，红黑树，AVL树，B~/B+树(B-tree)，伸展树——优缺点及比较 http://blog.csdn.net/bytxl/article/details/40920165

set

set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序

set总结：http://www.jb51.net/article/41682.htm

（1）为何map和set的插入删除效率比用其他序列容器高？ 大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下： 　　A 　 / \ 　 B C 　/ \ / \ D E F G 因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

（2）为何每次insert之后，以前保存的iterator不会失效？ iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

（3）当数据元素增多时，set的插入和搜索速度变化如何？ 如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。

set使用实例

#include <algorithm> #include <set> #include <iterator> #include<iostream> using namespace std; int main() { set<int> se; se.insert(1); se.insert(2); se.insert(2); se.insert(3); se.insert(1); set<int>::iterator it = se.begin(); // 使用stl算法find() 来搜寻元素，可以有效运作，但不是好办法 it = find(se.begin(), se.end(), 2); if (it != se.end()) cout << "2 found" << endl; // 关联式容器提供的find 效率更高 it = se.find(2); if (it != se.end()) cout << "2 found" << endl; //*it = 3; // 通过迭代器改变set元素是不被允许的，read-only it = se.begin(); while (it != se.end()) { cout << *it << " "; ++it; } cout << endl; return 0; }

map

map 键值对，不允许两个元素拥有相同的键值。 map依据key在红黑树中排序，所以改变map元素的实值并不影响map的排列规则。因此，map iterators既不是一种constant iterators,也不是一种mutable iterators.

map迭代器问题

map<int, int> _map; for (int i = 0; i < 10; i++) { _map.insert(make_pair(i, i + 1)); // 0-9 -> 1-10 } for (map<int, int>::iterator iter = _map.begin(); iter != _map.end();) { if (iter->first % 3 == 0) { iter = _map.erase(iter); // 删除iter之后 iter就失效了，返回iter的下一个 } else { iter++; } } for (map<int, int>::iterator iter = _map.begin(); iter != _map.end(); ++iter) { cout << iter->first << endl; // 打印1 2 4 5 7 8 删掉了 0 3 6 9 }

multiset

multiset的特性与用法和set完全相同，唯一的差别在于它允许键值重复，在底层实现上，一个是RB-tree的insert_equal，一个是insert_unique

#include <algorithm> #include <set> #include <iterator> #include<iostream> using namespace std; int main() { multiset<int> mset; mset.insert(3); mset.insert(1); mset.insert(2); mset.insert(1); mset.insert(2); multiset<int>::iterator it = mset.begin(); while (it != mset.end()) { cout << *it << " "; ++it; } cout << endl; mset.erase(1); // 删除所有的 1 it = mset.begin(); while (it != mset.end()) { cout << *it << " "; ++it; } cout << endl; it = mset.find(2); // 找到第一个2 while (it != mset.end()) { cout << *it << " "; ++it; } cout << endl; return 0; }

multimap

与map类似，可以允许相同的key

相关使用参考 http://www.cnblogs.com/music-liang/archive/2013/04/08/3007017.html

---

hashtable

hash 基础

采用二叉搜索树相关结构具有平均对数时间的表现。hash结构在插入，删除，搜寻等操作具有“常数平均时间”的表现，这种表现是以统计为基础的，不需依赖元素的随机性。

hash函数：关键字与存储地址之间的一种直接映射。当多个不同的关键字通过hash函数计算得到相同的存储数组小标是，称其发生了冲突；另一方面，这种冲突总是不可避免的，所有需要设计好处理冲突的方法。

典型的hash算法：MD4,MD5,SHA-1,（MD5和SHA-1，安全哈希算法可以说事目前应用最为广泛的hash算法），hash算法可能是不可逆的，所以不一定能用来加密。

处理hash冲突的一些方法 1.链地址法 2 再哈希法 3 开放地址法 4 建立一个公共的溢出区

http://blog.csdn.net/cws1214/article/details/9842709

http://blog.csdn.net/yzhang6_10/article/details/51337672

rbtree 具有对数平均时间 hashtabl 具有在插入，删除，搜索上的“常数平均时间”的表现

hash table（散列表）是一种在插入，删除，搜索等操作“常数平均时间”完成的数据结构。它是一种字典结构。哈希函数是一种映射函数，它能够将大数映射为小数。负责将某一元素映射为一个“大小可接受之索引”。哈希函数使用过程中可能会出现不同的元素被映射到相同的位置（相同的索引），称为哈希碰撞。解决哈希碰撞的方法：线性探测，二次探测，开链等等。

Hashtable底层实现是通过开链法来实现的，hash table表格内的元素称为桶（bucket),而由桶所链接的元素称为节点（node),其中存入桶元素的容器为stl本身很重要的一种序列式容器——vector容器。之所以选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。而节点元素为自定义的结构体：

template<class Value> struct __hashtable_node｛ __hashtable_node* next; Value val; ｝;

可以看到，这本身就是一种很典型的链式列表元素的表示方法，通过当前节点，我们可以很方便地通过节点自身的next指针来获取下一链接节点元素。

hash_set

hash_set大多以RB-tree为底层机制 SGI中 提供了一种以hashtable为底层机制

RBt-tree有自动排序功能，而hashtable没有，都能快速查询到元素

hash_map

hash_map 底层用hashtable实现，没有排序功能

map用 RB-tree实现，有排序功能

unordered_map

基于hash实现的，是无序的map unordered_map的插入、删除、查找 性能都优于 hash_map，优于 map

可参考 Sam-Cen http://blog.csdn.net/blues1021/article/details/45054159

algorithm

学习 http://www.cplusplus.com/reference/algorithm/

算法泛化

find泛化过程： http://www.cnblogs.com/Rosanna/p/3457999.html

---

stl copy

仿函数

仿函数 指针的区别

http://www.cnblogs.com/lutianba/archive/2013/05/18/3086287.html

仿函数讲解

http://blog.csdn.net/tianshuai1111/article/details/7687983

红黑树

july http://blog.csdn.net/v_JULY_v/article/details/6105630

C++ STL常见面试题

http://blog.csdn.net/tianya_team/article/details/50753759

http://www.tuicool.com/articles/feyqIn

C++ STL错题