STL(标准模板库)容器

数组 ([])

这里说的数组是，内置数组，即C/C++中本身提供的一种集合，用于存储多个相同类型对象。在STL出现之前就有了。
即如: char arr[元素个数] = {‘c’,‘b’,‘d’,…}; int arr[元素个数] = {3,5,6,…};
int arr1[] = {1,2,3,4,5,6};//通过右边的元素来推导出内置数组的元素个数
int arr2[5] = {1,};//首元素为1，其他元素被初始化为0。
int arr3[5];//数组中的5个元素都是随机值
内置数组：特点，
1.1声明定义时必须确定数组的长度，即在编译期数组长度要确定。即内置数组都是定长数组。不能随着元素的增加而自动进行动态扩容。
1.2数组名表示的是数组元素的首地址。
1.3内置数组是数据结构中的线性表下的顺序表。即分配的内存是连续的。
1.4查询及修改效率高，（非尾部的）插入和删除效率低（因为牵扯到其他元素的移动）。
1.5 数组类型是C/C++语言内置类型。
1.6 可以存储多个相同类型的对象。

内置数组的遍历方法

int arr[] = {9,8,8,8,5};
int lenth = sizeof(arr)/sizeof (arr[0]);//内置数组长度 获取方式
for(int i = 0; i < lenth; ++i)
{
   cout << arr[i] << endl;//可以，通过下标索引方式访问
   cout << *(arr + i) << endl;//可以，数组名arr是一个常量，表示数组首地址
   cout << *arr++ << endl;//编译报错，数组名arr是一个常量，表示数组首地址

}

int* arrPtr = arr;//arrPtr是一个数组指针
for(int i = 0; i < lenth; ++i)
{
   cout << *arrPtr++ << endl;//可以通过这个方式使用自增遍历打印元素
}

注意： 一般在使用内置数组时，内置数组的长度设置为，预计将要被存储元素的实际个数。如 int arr[5];声明定义完后，数组中就已经有5个元素了，只不过每个元素的值，是系统随机分配的。此时数组长度（元素个数）就是5。我们再往相应位置里存数据就会覆盖掉系统里随机分配的值。所以申请的内置数组的长度要和预计将要被存储元素的实际个数相等，否则数组长度过长。多余的部分就会出现垃圾数据了（随机分配的值）。所以使用数组时，在不确定预计需要的实际数组长度时，一般建议使用不定长数组 （向量vector）。

也可以通过在堆中申请一块连续内存存储数组元素，通过。

void test (int n){
	//int *ptr = new int[5]{9,8,8,8,5};//返回一个指向堆中数组首地址的指针，堆中生成的数组返回的是一个数组指针，而不是数组类型。
	int *ptr = new int[n];//返回一个指向堆中数组首地址的指针,这里数组长度写成变量n,只有在程序运行期才能确定堆中数组的长度。这样方式可以实现动态数组。
	
	//cout << ptr << endl;
	int arr[5] = {9,8,8,8,5};
	for(int i = 0; i < n; ++i)
	{
	   ptr[i] = arr[i];//通过下标索引的方式，给堆中数组赋值。
	}
	for(int i = 0; i < n; ++i)
	{
	   cout << *ptr++ << endl;//遍历打印,ptr先做解引入操作，传入cout中待输出显示， 然后 ptr再自增1。打印结果为：9,8,8,8,5
	   cout << *(ptr++) << endl;//遍历打印,ptr先做解引入操作， 然后 ptr再自增1。打印结果为：9,8,8,8,5
   	   cout << (*ptr)++ << endl;//错误方式，这种方式会 ptr先做解引入操作， 然后对解引用后的值自增1。 打印结果为 10,11,12,13,14
	}
	delete [] ptr;//清空堆中数组内存
}
int main(int argc, char *argv[]){
	test (5);	
}	

C++11 提供了另一种方式来 遍历内置数组：

int* beg = begin(arr);//返回指向数组首元素的指针。类似于vector中的获取指向首元素的迭代器
int* last = end(arr);//返回指向数组尾元素的下一个位置的指针。类似于vector中的获取指向尾元素的下一位置的迭代器
for(;beg != last; ++beg)
{
   cout << *beg << endl;
}
void myPrint(int val){
	cout << val << endl;	
}
for_each(beg,last,myPrint);//通过for_each,这里的myPrint传入的是一个全局函数名（函数地址）

for_each的祥解可以看：这里面的

向量 (vector)

vector也叫向量，是STL（标准模板库）下提供的一个模板类容器，需要在编译期进行其模板类的实例化。
vector的底层数组和内置数组存储方式一样，vector也是数据结构中的线性表下的顺序表，即分配的内存是连续的。vector是一个标准模板库中的容器之一。
2.2 vector与内置数组最大的区别，就是vector支持动态扩容。故vector也叫变长数组，或动态数组。而内置数组是定长数
组。
2.3 因为vector是模板类，所以在使用时，需要指明元素类型，才能在编译期进行其模板类的实例化。

vector的定义和初始化：

使用前必须引入 #include <vector> 头文件。
所有的容器都是类模板（string类型是已经被实例化后的只能储存char类型），要定义存储某种类型元素的容器，必须在
容器后的加一对尖括号，尖括号里面提供容器中存放的元素的类型。
vector<int> vtr; //会调用默认构造函数，此时元素的实际个数size为0，容量capacity为0。
vector<int> vtr(10);//会调用有参构造函数，此时元素的实际个数size为10，每个元素被初始化为0。容量capacity为10。
vector<int> vtr(10，-1);//会调用有参构造函数，此时元素的实际个数size为10，每个元素被初始化为-1。容量capacity为10。
vector<int> vtr = {1,2,3,4,5,6};//和内置数组的初始化方式类似，此时元素的实际个数size为6，容量capacity为6。元素值为1到6
如果想在定义vector时，只想指定容量大小。不存储元素。
可以这样：
vector<int> vtr;
vtr.reserve(10);//这样vector中元素的实际个数size为0，容量capacity为10，此时size为0时如果通过下标获取向量元素，vtr[0]会返回一个意外值，向量下标越界也不会报错，所以vtr的数据有效范围也需要程序员自己来控制。
注意：其实vector的成员属性capacity是vector的底层数组的实际长度。而向vector中每添加一个元素，vecotr的成员属性size就增加1，并将
元素存储到底层数组的指定位置。
故而获取vector中实际元素个数，是通过size的大小来记录的。当size的大小大于capacity时，此时再插入元素。就会生成一个新底层
数组，并将旧的底层数组的元素一一拷贝到新的底层数组里。然后再插入新元素。
注意：vector的底层数组其实就是一个普通的定长数组。它的扩容机制，就是通过创建一个长度扩容后的新数组，把旧数组数据拷贝到新
数组里，剩余的空间再用来插入新元素。
vector中常见方法：
size(); //获取向量中实际的元素个数，返回值类型为 vector<元素类型>::size_type。
capacity(); //获取向量中当前的容量，返回值类型为 vector<元素类型>::size_type。
empty(); //如果向量为空(指的就是size为0时)，则返回true, 否则返回false。
begin(); // 获取向量的迭代器，指向容器中第一个元素。返回值类型为 vector<int>::iterator。
end(); // 获取向量的迭代器，指向容器中最后一个元素的下一个位置。 返回值类型为 vector<int>::iterator。
max_size(); //vector可以保存的最大元素数，此值取决于系统或库实现。
reserve(int capacity); //设置向量的容量大小,一般用于刚声明完向量后，紧接着进行设置容量大小。
push_back(值) //在向量尾部添加元素。
insert(): //向向量的指定位置插入元素。
注意：通过向量对象[下标值]的方式，可以获取向量中已存在的元素值，以及修改此下标位置处已存在元素的值。但是不能用于添加元素，
这一点和内置数组不同。也就是说 当前下标处无元素，通过 向量对象[下标值] = 值；的方式是错误的。只能通过push_back(值)的方
式添加元素。

向向量中插入数据

方式一：通过push_back

	vector<int> vtr;
	vtr.reserve(10);

	for(vector<int>::size_type ix = 0 ; ix < vtr.capacity(); ix++)
	{
		vtr.push_back(ix+1);
	}
	//或
	for(decltype(vtr.capacity()) ix = 0 ; ix < vtr.capacity(); ix++)
	{
		vtr.push_back(ix+1);
	}

方式二：通过insert()函数插入：
insert（）函数有三个函数原型，也就是有三个重载函数。

1. iterator insert( iterator pos, const TYPE &val); //pos：指定位置的iterator，val：被插入的数据
2. void insert( iterator pos, size_type num, const TYPE &val); //pos：指定位置的iterator，num：被插入的数据重复的次数，val：被插入的数据
3. void insert( iterator pos, input_iterator start, input_iterator end);//将[start,end)之间的数据，插入到pos的位置。

//原型一：iterator insert( iterator pos, const TYPE &val); 
//比如现在已有一个向量
vector<int> v1= {1,2,3,4,5};
//获取指向首元素的迭代器
auto iter = v1.begin();
//使用insert在元素中插入数据
v1.insert(iter,2);//此时v1中元素为：{2,1,2,3,4,5}，使用insert在首元素位置插入时，那么下标为[0,size)之内的元素都向右移一位。

//原型二：void insert( iterator pos, size_type num, const TYPE &val);
vector<int> v2= {1,2,3,4,5};
//获取指向首元素的迭代器
auto iter = v2.begin();
//使用insert在元素中插入数据
iter++;//此时iter指向了v2的第二个元素的位置
v2.insert(iter,3,4);//此时v2中元素为：{1,4,4,4,2,3,4,5}  //下标[1,size)之内的元素都向右移动三位。

//原型三：
vector<int> v3= {1,2,3,4,5};
vector<int> anotherVector(2,100);//创建一个新向量
v3.insert(inter,anotherVector.begin(),anotherVector.end()); //此时：v3中的元素{200,200,1,2,3,4,5}
//所以只有在尾元素下一位置，或数组中元素个数为0时使用insert方法，才不会发生元素移动。

注意： 这里vtr.capacity()的返回值类型不能直接用int来接收,而是 vector<int>::size_type，如果不确定vtr.capacity()返回值什么类型
可以通过decltype关键字，decltype(有返回值的表达式)。它在编译期可以获取到表达式里的返回值类型。在C/C++中有很多这种情
况，返回值不直接用内置类型来接收，而用一个别名，这里size_type也是一个别名。因为不同的编译器或平台size_type实际类型可
能不同。这样通过别名可以兼容不同的平台。

遍历向量的常见方法

对上方已插入元素的向量进行遍历。

方式一：

//C++11中提供的方式，可以对数组，向量等容器进行遍历打印
for(const auto &value: vtr) 
{
	cout << value << endl;
}

方式二：

for(decltype(vtr.size()) ix = 0; ix < vtr.size(); ++ix)
{
	cout << vtr[ix] << endl;
}
//或者
//vector<int>::size_type ix = vtr.size(); //显示的写出了ix的类型
auto ix = vtr.size();//通过auto自动推导ix的类型
for(ix = 0; ix < vtr.size(); ++ix)
{
	cout << vtr[ix] << endl;
}

方式三：

//使用auto关键字自动推导iter的类型
for(auto iter = vtr.begin(); iter != vtr.end() ; ++iter)
{
	cout << *iter << endl;	
}

//或者 使用 decltype关键字自动推导vtr.begin()表达式的返回值类型
for(decltype(vtr.begin()) iter = vtr.begin(); iter != vtr.end() ; ++iter)
{
	cout << *iter << endl;	
}
//或者
typedef vector<int>::iterator iter_type;// 给复杂类型起别名
for(iter_type iter = vtr.begin(); iter != vtr.end() ; ++iter)
{
	cout << *iter << endl;	
}

方式四：

#include<algorithm>
class Print
{
public:
	void operator()(int value)
	{ 
		cout << value+1 << endl;
	};
};

//全局函数
void myPrint(int value)
{
	cout << value+1 << endl;
}

int main(int argc, char *argv[]){
	for_each(vtr.begin(),vtr.end(),Print()); //第三个参数 传递的是函数对象
	//或者
	for_each(vtr.begin(),vtr.end(),myPrint); //第三个参数 传递的是函数指针
	//或者
	for_each(vtr.begin(),vtr.end(),[=](int val)-{cout << val+1 << endl;});//第三个参数 传递的是lambda函数
}

注意：使用for_each函数需要引入#include<algorithm> （STL中的算法头文件）
for_each的详解可以看：这里面的
labmda函数的使用可以参考 labmda函数的使用

向量的扩容

默认情况下可以发现向vector中每添加一个元素都发生了容量的变更即扩容。
这样会严重影响其性能。一般是在声明vector类对象时，传递指定参数，即vector<int> vtr(50);//表明创建vtr对象时，并初始化其属性capacity值为50。
或者通过vtr.reserve(50);//使capacity值为50。
这样在开始存储数据前，先分配一定的容量。只有元素个数size大于容量capacity时才会开始进行扩容操作。
vector的源码中，当容量size大于capacity时就要发生扩容。
扩容时，按照编译器平台的规则根据确定后的capacity大小会生成一块连续的新内存，把旧数据一一拷贝到连续的新内存中，然后释放旧内存。

reserve(int);方法 ，为给向量扩容到指定的大小，参数为扩容后的容量大小。
注意底层会比较传入的容量与当前向量的实际容量.
若传入的容量大小 < 当前向量实际容量，则不会执行缩容操作。
若传入的容量大小 > 当前向量实际容量，则会执行扩容操作。

对于vector：(Linux GNU)g++是2倍扩容，MSVC是1.5倍扩容, (MinGW)g++是2倍扩容。
也就是GNU下是按2倍扩容，MSVC下按1.5倍扩容。push_back(),insert()函数增加数据时，都有可能会引起扩容。
例如：定义一个向量：vector<int> vtr;//此时size和capacity都为0

MinGW下：
没有添加怎么元素时//此时元素的实际个数size将为0，容量capacity为0
vtr.push_back(1); //此时元素的实际个数size将为1，容量capacity为1
vtr.push_back(2); //此时元素的实际个数size将为2，此时size>capacity,发生扩容capacity = capacity2 = 2
vtr.push_back(3); //此时元素的实际个数size将为3，此时size>capacity,发生扩容capacity = capacity2 = 4
vtr.push_back(4); //此时元素的实际个数size将为4，此时size==capacity,不发生扩容
vtr.push_back(5); //此时元素的实际个数size将为5，此时size>capacity,发生扩容capacity = capacity*2 = 8

MSVC下：
没有添加怎么元素时//此时元素的实际个数size将为0，容量capacity为0
vtr.push_back(1);//此时元素的实际个数size将为1，容量capacity为1
vtr.push_back(2);//此时元素的实际个数size将为2，此时size>capacity,发生扩容capacity = capacity1.5 = 1.5 实际为 2 因为capacity是整形，如果向下取整能够容纳当前元素个数，则优先选择向下取整, 否则向上取整。
vtr.push_back(3);//此时元素的实际个数size将为3，此时size>capacity,发生扩容capacity = capacity1.5 = 3
vtr.push_back(4);//此时元素的实际个数size将为4，此时size>capacity,发生扩容capacity = capacity1.5 = 4.5 实际为 4 因为capacity是整形，如果向下取整能够容纳当前元素个数，则优先选择向下取整。
vtr.push_back(5);//此时元素的实际个数size将为5，此时size>capacity,发生扩容capacity = capacity1.5 = 6
vtr.push_back(6);//此时元素的实际个数size将为6，此时size==capacity,不发生扩容
vtr.push_back(7);//此时元素的实际个数size将为7，此时size>capacity,发生扩容capacity = capacity*1.5 = 9

字符串 (string)

string是C++中提供的字符串类型，与其他的STL模板类容器不同的时，它是一个STL下模板类（ template <class T> class basic_string）的实例化。只能存储char类型的元素。

typedef basic_string<char> string; //string是basic_string<char>类类型的别名。

string是一个变长字符序列。它的底层数据存储是一个字符串数组，所以它的存储内存也是一块连续的内存，也是一个线性表下的顺序表。

众所周知C语言中没有专门的类型来表示字符串。
而是使用尾部元素为’\0’的字符数组来表示字符串，即C语言风格的字符串
例如：char str1[] = {‘a’,‘b’,‘c’,‘d’,‘\0’};
char* str2 = “abcd”;//右值字符串字面值，实际在数据区是 {‘a’,‘b’,‘c’,‘d’,‘\0’} 的格式存储，返回首元素的地址。

C++中的string支持动态扩容。而C语言风格的字符串（说白了和内置数组一样，只是尾部的元素是’\0’）是定长的，是不支持扩容的。

对于string：
如果字符串没有超过15个字节，都是分配在栈上（short string optimization,i.e. SSO）即短字符串优化，capacity都是15；
一旦超过了15个字节，则分配在堆上，
扩容机制： (MinGW)g++和 (Linux) g++都是2倍。msvc是首先约2倍扩容，扩容后是31，然后是1.5倍扩容；

g++下演示：
定义一个string对象
string str;
没有添加怎么元素时 //此时元素的实际个数size将为0，容量capacity为15 默认状态下string对象的容量会分配为15个字节。
str.push_back(‘0’);
str.push_back(‘1’);
str.push_back(‘2’);
str.push_back(‘3’);
str.push_back(‘4’);
str.push_back(‘5’);
str.push_back(‘6’);
str.push_back(‘7’);
str.push_back(‘8’);
str.push_back(‘9’);
str.push_back(‘a’);
str.push_back(‘b’);
str.push_back(‘c’);
str.push_back(‘d’);
str.push_back(‘e’);//此时元素的实际个数size将为15，容量capacity为15 也就是size个数在从1增加到15时，没有发生扩容。
str.push_back(‘f’);//此时元素的实际个数size将为16，新容量capacity = 旧容量capacity * 2 = 30
str = str + “0123456789abcde”;//这种方式不会使string容量按2倍增加，即使size超过现有容量，也只会保持capacity和size大小相等。
C++的string 更详细的内容请参看C++的 string详解
注意： 向量vector中的函数也同样适用string,应为它们在数据结构上都是线性表下的顺序表。