C++常用标准库

STL是Standard Template Library的简称，中文名标准模板库。
从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。STL现在是C++的一部分，因此不用安装额外的库文件。
在C++标准中，STL被组织为下面的17个头文件：
、、、、、、、<forward_list>、

1. vector的自我介绍
   vector是向量的意思，可以理解为“可变长度的数组”。
   就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
   相当于一个动态数组，在你不知道需要的数组有多大时可以使用它来节省很多空间。在ACM中常常会出现内存溢出（out of memory）的问题导致WA（wrong answer），而使用vector就能节省很多内存。
   使用vector要在程序开头加上#include来包含需要的头文件，还有加上“using namespace std;”，这样就可以在代码中使用vector了。
   2.vector的定义
   定义一个vector:
   vector vectorname;
   这个定义相当于定义了一个一维的数组vectorname[SIZE],只不过这个SIZE的长度是可以改变的，随着你“加入”进去数的个数而改变。所谓“可变长度的数组”。
   和一维的数组一样，这里的typename可以是任何的类型，如int,double,char,string，long long ,也可以是结构体，甚至是STL的容器如vector，set,queue,stack等。注意！如果typename也是一个容器的话，比如vector<vector > vectorname,要在两个’<‘符号之间加上一个空格，否则编译时会误以为是位移操作。
   3.vector的创建
   vector vec1; // 创建一个空的double向量vector vec(66); // 创建一个初始大小为66的int向量vector vec2(vec1); // 创建一个double型的vec2,并用vec1去初始化vec2vector vec(10,‘k’); // 创建一个含有10个char型数据的vector，并全部初始化为’k’vector vec(10,1);//创建一个初始大小为10的并且值都是1的vectorvector vec2(vec1.begin(),vec1.begin()+3);//用向量vec1的第0个到第2个值初始化vec2int arr[5] = {1, 2, 3, 4, 5};vector vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量,末尾指针指向结束元素//的下一个vector vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值，不包含arr[4]，//原因如上
   4.特别的，元素为vector的vector数组
   （其实就是vector的二维数组）和vector数组！ 如果typename是vector，那么就这么定义vector<vector > vectorname; 注意在相邻的’>'之间要加空格。 这个就像二维数组的定义，其中一维是一个元素是vector的vector数组。可以把vector数组 当作两个维长度都可变的二维数组理解。vector数组的定义vector Arrayname[arraySize]; 比如，vector vec[66]; 这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是vector容器。 而vector<vector > vectorname不同的地方时，前者的第一维长度已经固定为arraySize了， 后者却是两个维度都可变长的数组。哈哈哈，用你的大脑，发挥空间想象能力，出现了什么图形？ 很神奇是不是！
   5.vector容器内元素的访问形式
   vector一般有两种访问形式：通过下标访问或者是通过迭代器访问。
   (1)通过下标访问
   和访问普通数组是一样的，一个已经定义的vector vec的vector容器，直接访问vec[index]就可以了（比如 vec[0],vec[1])。需要注意的一点是，首先这个vec得有size!!!桥黑板!什么意思呢？就是如果一开始你定义了 比如vector vec1;直接使用vec[0]是不对的！因为里面还没有长度啊！开始用的时候我就经常犯这个错误（尴尬） 。所以可以通过下标访问的范围是从0~vec.size()-1.
   (2)通过迭代器访问
   啥叫迭代器啊？好可怕~就理解为指针吧，不去考虑细节，两者是一样的(包括在java中最近遇见的引用，这简直是三胞胎！）。 定义如下： vector::iterator it;(it就是变量名，一般默认都写成it) 这样it就是一个vector::iterator 型的变量了(hhh,这个名字好长啊)，其中，typename就是定义vector时 写的类型。比如： vector::iterator it; vector vec; vector::iterator it2; it2=vec.begin();(或者合成一条：vector::iterator it2=vec.begin(); ) 这样就得到了迭代器it(or it2)，并且可以通过it来访问vector里的元素。
   vector vec;vector::iterator it;for (it = vec.begin(); it != vec.end(); it++)//vector的迭代器不支持it<vec.end()写法，因此循环中只能用it!=end()cout << it << endl;//或者vector::iterator it=vec.begin();for(int i=0;i<vec.size();i++){printf("%d ",(it+i));//桥黑板！！在STL容器中，只有vector和string这两个好基友，才允许使用vev.begin()+3这种迭代器加上整//数的写法，只有这俩。//从这里可以看出，vec[i]和(vec.begin()+i)是等价的
   }//或者for (size_t i = 0; i < vec.size(); i++) {cout << vec.at(i) << endl;//见下文分解
   }
   好了，终于说完访问形式了，可以介绍基本操作啦！
   6.vector的基本操作
   (1)对容量的操作
   得到向量的大小： vec.size();
   得到向量最大可以是多大： vec.max_size();
   重新设置容器size的大小： vec.resize(num);
   重新设置容器capacity的大小： vec.reserve(num);
   向量真实大小： vec.capacity();
   判断向量是否为空： vec.empty();
   注：关于resize()和reverse(),我觉得记住一点就行了，容器调用resize()函数后， 所有的空间都已经初始化了，所以可以直接访问。比如： vector vet; vec.resize(100); vec[0]=1;//合法语句！ 而reserve()函数预分配出的空间没有被初始化，所以不可访问。 推荐一个关于resize()和reserve()写的不错的博客vector中resize()和reserve()区别
   (2)修改元素
   多个元素赋值： vec.assign(); //类似于初始化时用数组进行赋值
   末尾添加元素： vec.push_back(i)//在末尾添加元素i
   末尾删除元素： vec.pop_back();
   任意位置插入元素： vec.insert(it,x);
   1.用来向vector的任意迭代器（见上文）it处插入一个元素x,时间复杂度O(N);
   任意位置删除元素： vec.erase();
   1.erease(it)即删除迭代器为it处的元素；
   2.erase(first,last)即删除[first,last)内的所有元素；(老美的左闭右开，你懂的）
   交换两个向量的元素： vec.swap();//不多讲，用的真的很少。同样，推荐博客vector利用swap()函数进行内存的释放
   （3）惊现迭代器
   开始指针：vec.begin();末尾指针：vec.end(); //指向最后一个元素的下一个位置指向常量的开始指针： vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容，但还是可以通过其他方式修改的，而且指针也是可以移动的。（用的很少，不妨先忽略吧）指向常量的末尾指针： vec.cend();（同上，不多说）
   （4）元素的访问
   下标访问： vec[1]; //桥黑板！！并不会检查是否越界at方法访问： vec.at(1); //以上两者的区别就是at会检查是否越界，是则抛出out of range异常访问第一个元素： vec.front();访问最后一个元素： vec.back();返回一个指针： int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组，所以可以返回一个指针指向这个数组。这是是C++11的特性。（可忽略）
   （5）一些算法
   遍历元素
   Cvector::iterator it; for (it = vec.begin();it != vec.end(); it++)
   cout << *it << endl;//或者for (size_t i = 0; i < vec.size(); i++) {
   cout << vec.at(i) << endl;
   }
   元素翻转
   C#include
   reverse(vec.begin(), vec.end());
   元素排序
   C#include
   sort(vec.begin(), vec.end()); //采用的是从小到大的排序 //如果想从大到小排序，可以采用上面反转函数，也可以采用下面方法: bool Comp(const int& a, const int& b) {//固定套路，要加上const，意思是不能修改引用 return a > b;
   }
   sort(vec.begin(), vec.end(), Comp);
   7.vector的用武之地
   （1）储存数据
   vector本身可以作为数组使用，而且在一些元素个数不确定的场合可以很好的节省空间。
   有些场合需要根据一些条件把部分数据输出在同一行，数据中间用空格隔开。由于输出的数据个数是不确定的，为了跟方便的处理最后一个满足条件的数据后面不输出额外的空格，可以先用vector记录所有需要输出的数据，然后一次性输出。
   有强大的方法可以调用（妈呀，java学多了，请不要喷我，暂且就叫方法吧，介绍如上vector的基本操作（1）~（4））
   ( 2 )用邻接表存储图
   使用vector实现邻接表可以有效避免指针，而且更容易把握。