c++ || STL序列容器

• STL
• • STL组成结构
• STL序列式容器
• • 迭代器（iterator）
  • 顺序容器
  • • array< T, N > 数组
    • vector< T > 向量
    • list< T > 链表
    • deque< T > 双端队列
    • forward_list 正向链表

Standard Template Library,标准模板库；STL借助模板吧常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。
vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

容器用于存放数据的类模板

1. 不同容器的迭代器不同，功能强弱也不同
   迭代器的功能是遍历容器，在遍历的同时可以访问（修改）容器中的元素，但是不能初始化空的容器。

空容器的begin(),end()指向同一个位置，无法循环赋值

//array::iterator i;
//逐个输出元素
vector::iterator i;//指针
	for (i = ar.begin(); i != ar.end(); i++)
	{
		cout << *i << " ";
	}
	cout << endl << "第三种" << endl;
	for (i = ar.begin(); i < ar.end(); i++)
	{
		cout << *i << " ";
	}
	cout << endl << "第四种" << endl;
	i = ar.begin();
	while (i < ar.end())
	{
		cout << *i << " ";
		i += 2;
	}

2. 定义
   

迭代器名：表示迭代器指向的元素

反向迭代器和正向迭代器的区别在于：
对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；
而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。

int main()
{
	list s{ 13,24,35,65,98 };
	list::reverse_iterator i; //反向迭代器
	list::const_iterator m;   //返回的是const属性 不能修改
	//逆向输出链表中的数据
	for (i = s.rbegin(); i != s.rend(); i++)
	{ 
		//rbegin() 最后一个元素 rend()第一个元素的前一个位置
		//i++   每次向左移动一个位置
		cout << *i << "  ";
	}
	i = s.rbegin();
	*i = 11;              //可以通过反向迭代器修改数据
	cout << endl;
	list::iterator p;    //正向迭代器
	for (p = s.begin(); p != s.end(); p++)
	{
		cout << *p << "  ";
	}
	cout << endl;
	m = s.begin();
	 //*m = 00;   不能通过迭代器修改链表中的数据
	cout << *m << endl;
	return 0;
}

不会对存储的元素进行排序，元素排序的顺序取决于存储它们的顺序

• 表示可以存储N个T类型的元素，长度固定不变，不能删除或增加元素，只能修改元素的值。
• array在定义后不会默认初始化操作

#include
using namespace std;
std::array value;//各元素值是不确定的（不会做默认初始化操作）
//T：容器中存储的具体数据类型
//N：容器的大小，常量
std::array value {};//默认初始化为0.0
	//if (!ar.empty())
	//{//非空  输出
	//	array::iterator i;         //正向迭代器
	//	for (i = ar.begin(); i < ar.end(); i++)
	//	{
	//		cout << *i << " "; //7123
	//	}
	//	cout << endl;
	//}

	if (!ar.empty())
	{//非空  输出
		array::reverse_iterator i;      //反向迭代器
		for (i = ar.rbegin(); i != ar.rend(); i++)
		{
			cout << *i << " ";  //3217
		}
		cout << endl;
	}

  arrayvalues;
    int h = 1;
    //使用auto关键字可以使编译器自动判断出该迭代器的类型
    auto first = values.begin();
    auto last = values.end();
    //初始化 values 容器为{1,2,3,4,5}
    while (first != last)
    {
        *first = h;
        ++first;
        h++;
    }

//返回const类型的正向迭代器，可以访问 不能修改
    auto first = values.cbegin();
    auto last = values.cend();
    //由于 *first 为 const 类型，不能用来修改元素
    //*first = 10;   X

• 访问单个元素

v.at(4) = v.at(3)+v.at(2)*2.0;//会提供越界检查
get<3>(v);
*v.data();  //data（）->第一个元素的指针
*(v.data()+2); //

• 存放T类型的元素，长度可变的序列容器，存储空间不足时，会自动申请更多的内存
• 尾部增加、删除元素效率最高（O(1)）
• 其他位置插入或删除元素效率较差（O(n)）
• vector在重新增加容量之后，之前定义的迭代器会失效所以每当vector容器的容量发生变化时，都要对之前创建的迭代器重新初始化一遍
• 空的容器不能使用迭代器进行初始化 要使用push_back()或resize()函数进行初始化

	vector v{ 12,23,34,45,57,68 };
	vector::iterator i; //正向迭代器
	for (i = v.begin(); i < v.end(); i++)
	{
		cout << *i << "  ";
	}
	cout << endl;
	v.push_back(00);//空的容器不能使用迭代器进行初始化 要使用push_back()或resize()函数进行初始化
	v.insert(v.begin() + 2, 99);

	vector::reverse_iterator p; //反向迭代器
	for ( p = v.rbegin(); p != v.rend(); p++)
	{
		cout << *p << "   ";
	}
	cout << endl;


    cout << "values 容器首个元素的地址：" << values.data() << endl;
    auto first = values.begin();
    auto end = values.end();
    //增加 values 的容量
    values.reserve(20);//容量变化后要重新对迭代器赋值
    cout << "values 容器首个元素的地址：" << values.data() << endl;
    first = values.begin();
    end = values.end();
    while (first != end) {
        cout << *first ;
        ++first;
    }

• 访问vector容器中元素

	vector v{ 12,23,34,45,57,68 };
	cout << v[3] << endl;
	*(v.data()) = 44;
	cout << *(v.data()) << endl; //data()返回指向第一个元素的指针
	cout << v.at(5) << endl;   //at()越界时会抛出out_of_range异常
	v.front() = 99;
	cout << v.front() << endl; //首元素的引用
	cout << v.back() << endl;  //尾元素的引用
	for(int i=0;i
		cout< 
capacity(容量)和size(大小)区别
 
 
 
capacity，指在不分配更多内存的情况下，容器可以保存的最多元素个数；
size，指容器实际包含的元素个数；
容器的大小不能超出他的容量，在大小等于容量的基础上，只要增加一个元素，就必须分配更多的内存。（不止1个，一次性申请多个存储空间，减少申请空间的次数，节省申请空间时消耗的时间）
 
 
 
 
注意：一旦 vector 容器的内存被重新分配，则和 vector 容器中元素相关的所有引用、指针以及迭代器，都可能会失效，最稳妥的方法就是重新生成。
 
 
v.reserve(49); //修改容器的容量
v.resize(30);  //修改容器的大小，可能间接导致容量的增加  默认初始化值为0
v.resize(30,1);//修改容器的大小，默认初始化为1
v.resize(20);  //从30-20，容器大小减少 会自动移除多余的元素
 
push_back 和 emplace_back区别
 
v.push_back(0);   //尾部插入0
v.emplace_back(9);//尾部插入9
 
 
 
push_back：先创建元素，在将元素移动或拷贝到容器中（如果是拷贝后会自动销毁创建出的元素）（底层实现时，会优先选择移动构造函数，没有才会调用拷贝构造函数）
emplace_back：直接在尾部创建元素，省去拷贝或移动元素的过程
 
 
insert
 
语法格式
用法说明
iterator insert(pos,elem)
在迭代器pos 指定的位置之前插入—个新元素elem，并返回表示新插入元素位置的迭代器。
iterator insert(pos,n,elem)
在迭代器pos指定的位置之前插入n个元素elem，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,first,last)
在迭代器pos指定的位置之前，插入其他容器（不仅限于vector）中位于[first,last)区域的所有元素，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,initlist)
在迭代器pos 指定的位置之前，插入初始化列表(用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。
注：emplace函数 指定位置前插入一个新元素；只能插入一个
 
    std::vector d{ 1,2 };
    //第一种格式用法
    d.insert(d.begin() + 1, 3);//{1,3,2}
    //第二种格式用法
    d.insert(d.end(), 2, 5);//{1,3,2,5,5}
    //第三种格式用法
    std::arraytest{ 7,8,9 };
    d.insert(d.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
    //第四种格式用法
    d.insert(d.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}
 
pop_back
 
函数
功能
pop_back()
删除 vector 容器中最后一个元素，该容器的大小（size）会减 1，但容量（capacity）不会发生改变。
erase(pos)
删除 vector 容器中 pos 迭代器指定位置处的元素，并返回指向被删除元素下一个位置元素的迭代器。该容器的大小（size）会减 1，但容量（capacity）不会发生改变。
swap(beg)、pop_back()
先调用 swap() 函数交换要删除的目标元素和容器最后一个元素的位置，然后使用 pop_back() 删除该目标元素。
erase(beg,end)
删除 vector 容器中位于迭代器 [beg,end)指定区域内的所有元素，并返回指向被删除区域下一个位置元素的迭代器。该容器的大小（size）会减小，但容量（capacity）不会发生改变。
remove()
删除容器中所有和指定元素值相等的元素，并返回指向最后一个元素下一个位置的迭代器。值得一提的是，调用该函数不会改变容器的大小和容量。
clear()
删除 vector 容器中所有的元素，使其变成空的 vector 容器。该函数会改变 vector 的大小（变为 0），但不是改变其容量。
不要使用vector < bool>,严格意义来说不是一个STL容器，底层存储的不是bool类型值
 
list< T > 链表 
 
长度可变，由T类型元素组成的序列，双向链表形式组织元素，高效增加或删除元素（O(1)）
访问元素速度慢，必须从第一个元素或最后一个元素开始访问，沿着链表移动
分散存储在内存空间里
list配备的迭代器类型为双向迭代器
list 容器在进行插入（insert()）、接合（splice()）等操作时，都不会造成原有的 list 迭代器失效，甚至进行删除操作，而只有指向被删除元素的迭代器失效，其他迭代器不受任何影响。
 
 
 
优点：可以在已知的任何位置快速插入或删除元素，移动元素比其他容器效率高
 缺点：不能通过位置直接访问元素，必须要遍历容器直到找到该位置
 
 
 
 
假设 p1 和 p2 都是双向迭代器，则它们支持使用 ++p1、 p1++、 p1–、 p1++、 *p1、 p1==p2 以及 p1!=p2 运算符，但不支持以下操作（其中 i 为整数）：
 
 
p1[i]：不能通过下标访问 list 容器中指定位置处的元素。
p1-=i、 p1+=i、 p1+i 、p1-i：双向迭代器 p1 不支持使用 -=、+=、+、- 运算符。
p1p2、 p1<=p2、 p1>=p2：双向迭代器 p1、p2 不支持使用 <、 >、 <=、 >= 比较运算符。
 
 
    //使用begin()/end()迭代器函数对输出list容器中的元素
    for (std::list::iterator it = values.begin(); it != values.end(); ++it) {
        std::cout << *it;
    }
    cout << endl;
    //使用 rbegin()/rend()迭代器函数输出 lsit 容器中的元素
    for (std::list::reverse_iterator it = values.rbegin(); it != values.rend();++it) {
        std::cout << *it;
    }
 
splice()
 功能：将其他list容器的元素添加到当前list容器中指定位置处
 
将存储该元素的节点从 list 容器底层的链表中摘除，然后再链接到当前 list 容器底层的链表中。这意味着，当使用 splice() 成员方法将 x 容器中的元素添加到当前容器的同时，该元素会从 x 容器中删除。
 
语法格式
功能
void splice (iterator position, list& x);
position 为迭代器，用于指明插入位置；x 为另一个 list 容器。此格式的 splice() 方法的功能是，将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator i);
position 为迭代器，用于指明插入位置；x 为另一个 list 容器；i 也是一个迭代器，用于指向 x 容器中某个元素。此格式的 splice() 方法的功能是将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator first, iterator last);
position 为迭代器，用于指明插入位置；x 为另一个 list 容器；first 和 last 都是迭代器，[fist,last) 用于指定 x 容器中的某个区域。此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处。
    //创建并初始化 2 个 list 容器
    list mylist1{ 1,2,3,4 }, mylist2{10,20,30};
    list::iterator it = ++mylist1.begin(); //指向 mylist1 容器中的元素 2
   
    //调用第一种语法格式
    mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                 // mylist2:
                                 // it 迭代器仍然指向元素 2，只不过容器变为了 mylist1
    //调用第二种语法格式，将 it 指向的元素 2 移动到 mylist2.begin() 位置处
    mylist2.splice(mylist2.begin(), mylist1, it);   // mylist1: 1 10 20 30 3 4
                                                    // mylist2: 2
                                                    // it 仍然指向元素 2
   
    //调用第三种语法格式，将 [mylist1.begin(),mylist1.end())范围内的元素移动到 mylist.begin() 位置处                  
    mylist2.splice(mylist2.begin(), mylist1, mylist1.begin(), mylist1.end());//mylist1:
                                                                             //mylist2:1 10 20 30 3 4 2
 
deque< T > 双端队列 
double-ended queue
尾部增加、删除元素，头部增加、删除元素时间复杂度：（O(1)）
某一位置插入或删除元素，时间复杂度：（O(n)）
 
 
 
当向 deque 容器添加元素时，deque 容器会申请更多的内存空间，同时其包含的所有元素可能会被复制或移动到新的内存地址（原来占用的内存会释放），这会导致之前创建的迭代器失效。在对容器做添加元素的操作之后，如果仍需要使用之前以创建好的迭代器，为了保险起见，一定要重新生成。
 
 
函数成员
函数功能
swap
交换两个容器的所有元素
push_front
序列头部添加一个元素
pop_front
移除容器头部的元素
emplace
指定位置直接生成一个元素
emplace_front
在容器头部生成一个元素。和
emplace_back
在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。
 
 
如何扩容
 
 
	deque dq1;         //
	deque dq2(10);     //包含10个元素（默认值是0）的deque容器
	deque dq3(10,2);   //包含10个元素（默认值是2）的deque容器
	deque dq4(dq1);    //拷贝构造  新旧容器存储类型一致
	array arr{ 1,2,3,4,5, };
	deque dq5(arr.begin()+2, arr.end()); //用某一区间值构造
	
	//deque::iterator i;
	//	for (auto i = begin(d); i < end(d); i++)  全局函数
		for (auto i = d.begin(); i < d.end(); i++) //自身容器的函数
	{
		cout << *i << "  ";
	}
	cout << endl;
	d.swap(m);
 
访问容器中元素
 
	cout << d[1] << endl;
	cout << d.at(3) << endl;
	d.front() = 10;
	cout << d.front() << endl;
	cout << d.back() << endl;

	deque::iterator i;
	for (i = d.begin() + 1; i < d.end() - 1; i++)
	{
		cout << *i << " ";   //2345
	}
 
forward_list 正向链表 
单链表形式组织元素，只能从第一个元素开始访问
 
 
	forward_list p{ 1,2,3,4,6,7,9 };
	p.reverse(); //反转
	forward_list::iterator i;
	for (i = p.begin(); i != p.end(); i++)
	{
		cout << *i << " ";
	}