❤️算法程序设计——算法程序设计工具（STL）欢迎关注❤️_stl的开发工具

1.1 STL（Standard Template Library）

1.1.1 STL概述

        STL是一个功能强大的基于模板的容器库，通过直接使用这些现成的标准化组件可以大大提高算法设计的效率和可靠性。它是由很多代的大牛程序员修改完善过的。其实简单的说就是它是程序员们为了方便和效率而创造出来的东西。而对于算法设计者而言，“尽可能使用STL，而不自己实现”的原则。

STL主要有container（容器）、algorithm（算法）、iterator（迭代器）三大部分构成。容器用于存放数据对象（元素），算法用于操作容器中的数据对象，算法和容器之间的中介就是迭代器。

1.1.2 什么是STL容器

        简单说，STL容器就是一种数据结构，例如链表，栈，队列等等，这些数据结构在STL中都已经存在了，当我们在编程的时候，就可以直接按照相应的规则使用即可。

STL容器常用的数据结构和相应的头文件：

1. vector（向量）：（连续的空间存储，可以使用[]操作符）快速的访问随机的元素，快速的在末尾插入元素，但是在序列中间的插入，删除元素要慢，而且如果一开始分配的空间不够的话，可能重新分配更大空间，拷贝的性能开销较高。头文件：<vector>
2. deque（双端队列）：（小片的连续，小片间用链表相连，实际上内部有一个map的指针，因为知道类型，所以还是可以使用[]，只是速度没有vector快）快速的访问随机的元素，快速的在开始和末尾插入元素，但随机的插入，删除元素要慢，空间的重新分配要比vector快，重新分配空间后，原有的元素不需要拷贝。对deque的排序操作，可将deque先复制到vector，排序后在复制回deque。头文件<deque>
3. list（链表）：（每个元素间用链表相连）访问随机元素不如vector快，随机的插入元素比vector快，对每个元素分配空间，所以不存在空间不够，重新分配的情况。头文件<list>
4. set（集合）/multimap（多重集合）：内部元素唯一，用一棵平衡树结构来存储，因此遍历的时候就排序了，查找也比较快的哦。set中的元素有序且课重复，multimap中的所有元素有序但是不重复。头文件<set>
5. map（映射）：一对一的映射的结合，key不能重复。头文件<map>
6. stack（栈）：栈，必须结合其他的容器使用，stl中默认的内部容器是deque。先进后出，只有一个出口，不允许遍历。头文件<stack>
7. queue（队列）：是受限制的deque，内部容器一般使用list较简单。先进先出，不允许遍历。头文件<queue>
8. unordered_set、unordered_map：散列表，Hash表。快速查找，快速插入，但不能随机访问，另外空间消耗大（这里依赖于散列函数）。头文件<map>
9. priority_queue（优先队列）：优先队列，用于实现最大堆（默认），最小堆。最终在队列里总是top出最大的元素。头文件<queue>
10. string（字符串）：字符串处理容器。头文件<string>

        在我们编写代码的过程中，我们给我们所要写的函数起名字，但是STL当中的函数也是有名字的，那么会不会重复呢，我们这要说一说命名空间，就好比sort（），我们可能也要定义一个sort（），但是STL中有sort（）的算法，所以我们为了避免混淆，STL的sort（）以及标识符都封装在命名空间的std中。STL的sort（）算法编译为：std::sort(),避免名字起冲突。当我们使用STL时我们需要把这句话加在文件的开头：using namespace std;

1.1.3 什么是STL算法

        算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。
       <algorithm>是所有STL头文件中最大的一个，其中常用到的功能范围涉及到比较、 交换、查找、遍历操作、复制、修改、反转、排序、合并等等。
       <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加 法和乘法在序列上的一些操作。
       <functional>中则定义了一些模板类，用以声明函数对象。
       STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大 大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率。 
       #include <algorithm>
       #include <numeric>
       #include <functional>

        简单的说就是，现在我们有一个文件库，当我们需要这个文件库里面的文件的时候，我们就使用文件库来解决问题，过程我们不需要知道如何进行的，结果是正确的。

1.1.4 什么是迭代器

要访问顺序容器和关联容器中的元素，需要通过“迭代器（iterator）”进行，迭代器是一个变量，相当于容器和操作容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类型。

迭代器按照定义方式分为以下四种：
正向迭代器，定义方式：

1. 容器类名::iterator 迭代器名;

常量正向迭代器，定义方式：

1. 容器类名::const_iterator 迭代器名;

反向迭代器，定义方式：

1. 容器类名::reverse_iterator 迭代器名;

常量方向迭代器，定义方式：

1. 容器类名::const_reverse_iterator 迭代器名;

迭代器用法示例：
通过迭代器可以读取它指向的元素，*迭代器名就代表迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。

迭代器都可以进行++操作。方向迭代器和正向迭代器的区别在于：

• 对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素
• 反向迭代器进行++操作时，迭代器会指向容器中的前一个元素

 实例一：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<int> v;//v是存放int类型变量的可变长数组，开始时没有元素 
	for(int n=0;n<5;n++)
	{
		v.push_back(n);//push_back成员函数在vector容器尾部添加元素 
	}
	vector<int>::iterator i;//定义正向迭代器 
	for(i=v.begin();i!=v.end();++i)//使用迭代器遍历容器 
	{
		cout<<*i<<" ";//*i就是迭代器i指向的元素 
		*i *=2;
	}
	cout<<endl;
	//反向迭代器输出容器 
	for(vector<int>::reverse_iterator j=v.rbegin();j!=v.rend();++j)
	{
		cout<<*j<<" ";
	}
	return 0;
 } 

 

 实例二：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<int>myv;//定义vector容器 
	myv.push_back(1);//push_back()在末尾插入元素 
	myv.push_back(2);
	myv.push_back(3);
	vector<int>::iterator it;//定义正向迭代器 
	for (it=myv.begin();it!=myv.end();++it)// 正向输出 
		printf("%d ", *it);
	printf("\n");
	vector<int>::reverse_iterator iit;	//定义反向迭代器 
	for(iit=myv.rbegin();iit!=myv.rend();++iit)//反向输出 
	{
		cout<<*iit<<" ";
	 } 
	return 0;
 } 

 1.2 常用STL容器（直接上代码理解）

1.2.1 vector（向量容器）

定义vector容器的几种方式：

vector<int> v1;//定义元素为int的向量v1
vector<int> v2(10);//指向向量v2的初始大小为10个int元素
vector<int> v3(10.1.23);//指定v3的十个初始元素初值为1.23
vector<int> v4(a,a+5);//用数组a[0..4]共五个元素初始化v4

1.2.2vector提供的一些成员函数

1.构造和复制构造函数

 2.析构函数~vector()

销毁容器对象并回收了所有分配的内存

3.重载了=符号

vector<int> E;

E = B; //使用=符号

B = vector<int>(); //将B置为空容器

4. vector::begin()  返回第一个元素的迭代器

  函数原型：

  iterator begin ();  //返回一个可变迭代器

const_iterator begin () const; //返回一个常量的迭代器，不可变

5.vector::end()  返回的是越界后的第一个位置，也就是最后一个元素的下一个位置

  iterator end ();

const_iterator end () const;

6.vector::rbegin() 反序的第一个元素，也就是正序最后一个元素

  reverse_iterator rbegin();

const_reverse_iterator rbegin() const;

7.vector::rend() 反序的最后一个元素下一个位置，也相当于正序的第一个元素前一个位置

  reverse_iterator rend();

const_reverse_iterator rend() const;

和vector::end()原理一样

8.vector::size() 返回容器中元素个数

  size_type size() const;

  注意与vector::capacity()的区别

9.vector::max_size()

  size_type max_size () const;

  返回容器的最大可以存储的元素个数，这是个极限，当容器扩展到这个最大值时就不能再自动增大

10. vector::resize()

  void resize ( size_type sz, T c = T() );

  重新分配容器的元素个数，这个还可以改容器的容量，如果重新分配的元素个数比原来的小，将截断序列，后面的部分丢弃，如果大于原来的个数，后面的值是c的值，默认为0

11. vector::capacity()

   size_type capacity () const;

   返回vector的实际存储空间的大小，这个一般大于或等于vector元素个数，注意与size()函数的区别

12. vector::empty()

   bool empty () const;

   当元素个数为0时返回true，否则为false，根据的是元素个数而不是容器的存储空间的大小

13. vector::reserve()

   void reserve ( size_type n );

重新分配空间的大小，不过这个n值要比原来的capacity()返回的值大，不然存储空间保持不变，n值要比原来的实际存储空间大才能重新分配空间，但是最大值不可以大于max_size的值，否则会抛出异常

14. vector::operator[]  //重载了[]符号

   reference  operator[] ( size_type n );

const_reference  operator[] ( size_type n ) const;

实现了下标访问元素

15. vector::at()

   const_reference at ( size_type n ) const;

   reference at ( size_type n );

   在函数的操作方面和下标访问元素一样，不同的是当这个函数越界时会抛出一个异常out_of_range

16. vector::front()

   reference front ( );

const_reference front ( ) const;

返回第一个元素的值，与begin()函数有区别，begin()函数返回的是第一个元素的迭代器

17. vector::back()

   reference back ( );

const_reference back ( ) const;

同样，返回最后一个元素的值，注意与end()函数的区别

18. vector::assign()

   template <class InputIterator> void assign ( InputIterator first, InputIterator last );

void assign ( size_type n, const T& u );

将丢弃原来的元素然后重新分配元素，第一个函数是使用迭代器，第二个函数是使用n个元素，每个元素的值为u。

19. vector::push_back()

   void push_back ( const T& x );

   在容器的最后一个位置插入元素x,如果size值大于capacity值，则将重新分配空间

20. vector::pop_back()

   void pop_back ( );

   删除最后一个元素

21. vector::insert()

   iterator insert ( iterator position, const T& x );

   void insert ( iterator position, size_type n, const T& x );

template <class InputIterator>

void insert ( iterator position, InputIterator first, InputIterator last );

   插入新的元素，

第一个函数，在迭代器指定的位置前插入值为x的元素

第二个函数，在迭代器指定的位置前插入n个值为x的元素

第三个函数，在迭代器指定的位置前插入另外一个容器的一段序列迭代器first到last

若插入新的元素后总得元素个数大于capacity，则重新分配空间

22. vector::erase()

   iterator erase ( iterator position );

iterator erase ( iterator first, iterator last );

删除元素或一段序列

23. vector::swap()

   void swap ( vector<T,Allocator>& vec );

   交换这两个容器的内容，这涉及到存储空间的重新分配

24. vector::clear()

   void clear ( );

   将容器里的内容清空，size值为0，但是存储空间没有改变

实例：

#include<bits/stdc++.h>
using namespace std;
int main()
{
 
        //构造函数,复制构造函数(元素类型要一致),
	vector<int> A;  //创建一个空的的容器
	vector<int> B(10,100); //创建一个10个元素,每个元素值为100
	vector<int> C(B.begin(),B.end()); //使用迭代器,可以取部分元素创建一个新的容器
	vector<int> D(C); //复制构造函数,创建一个完全一样的容器
    
          //重载=
	vector<int> E;
	E = B;
 
	//vector::begin()，返回的是迭代器
   
	vector<int> F(10); //创建一个有10个元素的容器
           for (int i = 0; i < 10; i++)
          {
		F[i] = i;
          }
 
	/*
	vector<int> F; //创建一个空容器
	for (int i = 0; i < 10; i++)
	{
		F.push_back(i);
	} 
        */
 
	vector<int>::iterator BeginIter = F.begin();
	cout << *BeginIter << endl; //输出0
 
	//vector::end() 返回迭代器
	vector<int>::iterator EndIter = F.end();
	EndIter--; //向后移一个位置
	cout << *EndIter << endl; //输出9
 
	//vector::rbegin() 返回倒序的第一个元素，相当于最后一个元素
	vector<int>::reverse_iterator ReverBeIter = F.rbegin();
	cout << *ReverBeIter << endl; //输出9
 
	//vector::rend() 反序的最后一个元素下一个位置，也相当于正序的第一个元素前一个位置
	vector<int>::reverse_iterator ReverEnIter = F.rend();
	ReverEnIter--;
	cout << *ReverEnIter << endl; //输出0
 
	//vector::size() 返回元素的个数
	cout << F.size() << endl; //输出10
 
	//vector::max_size()
	cout << F.max_size() << endl; //输出1073741823，这个是极限元素个数
 
	//vector::resize()
	cout << F.size() << endl; //输出10
	F.resize(5);
	for(int k = 0; k < F.size(); k++)
		cout << F[k] << "  "; //输出 0 1 2 3 4
         cout << endl;
	
	//vector::capacity()
	cout << F.size() << endl; //5
	cout << F.capacity() << endl; //10
 
	//vector::empty()
         B.resize(0);
	cout << B.size() << endl; //0
	cout << B.capacity() << endl; //10
	cout << B.empty() << endl; //true
 
	//vector::reserve() //重新分配存储空间大小
           cout << C.capacity() << endl; //10
	C.reserve(4);
	cout << C.capacity() << endl; //10
	C.reserve(14);
	cout << C.capacity() << endl; //14
 
	//vector::operator []
	cout << F[0] << endl; //第一个元素是0
 
	//vector::at()
	try
	{
	  cout << "F.size = " << F.size() << endl; //5
           cout << F.at(6) << endl; //抛出异常
	}
	catch(out_of_range)
	{	
	   cout << "at()访问越界" << endl;
	}
 
	//vector::front() 返回第一个元素的值
           cout << F.front() << endl; //0
 
	//vector::back()
	cout << F.back() << endl; //4
 
	//vector::assign()
	cout << A.size() << endl; //0
	vector<int>::iterator First = C.begin();
	vector<int>::iterator End = C.end()-2;
	A.assign(First,End);
	cout << A.size() << endl; //8
	cout << A.capacity() << endl; //8
 
	A.assign(5,3); //将丢弃原来的所有元素然后重新赋值
	cout << A.size() << endl; //5
	cout << A.capacity() << endl; //8
 
	//vector::push_back()
	cout << *(F.end()-1) << endl; //4
	F.push_back(100);
	cout << *(F.end()-1) << endl; //100
 
	//vector::pop_back()
	cout << *(F.end()-1) << endl; //100
	F.pop_back();
	cout << *(F.end()-1) << endl; //4
 
	//vector::swap()
	F.swap(D); //交换这两个容器的内容
	for(int f = 0; f < F.size(); f++)
		cout << F[f] << " ";
	cout << endl;
	for (int d = 0; d < D.size(); d++)
	    cout << D[d] << " ";
         cout << endl;
	//vector::clear()
	F.clear();
	cout << F.size() << endl;     //0
	cout << F.capacity() << endl; //10
 
	return 0;
}