C++|通俗理解STL c++常用stl

“存储程序”是电子计算机技术一个很重要的概念。程序能在计算机上运行，必须先让程序代码从其他的一些存储介质（如光盘或硬盘）读入到内存，然后才能由控制器从内存读取、解释并产生控制信号，协调其它部件完成程序功能。不但要在内存中存储程序代码，而且还需要额外的空间来动态、静态、或自动存储相关的数据。也就是说，程序的全部代码和相关的数据都需要存储到内存中并能被存储器随机访问到。

代码和相关数据如何存储就是一个很重要的问题，需要知道的是，内存单元在内存中只是线性相关，也就是说，内存单元地址是一种线性关系。数据在内存中的物理存储有三种方式：顺序存储、链式存储、地址映射。

容器是一个存储和组织其他对象的类对象。序列容器用一个序列（如数组）存储对象。关联容器存储键/值（对象）对的元素，其中键确定值存储在容器中的何处。

数据的物理存储有一个很重要的原则，就是“存得进去，取得出来”，且要考虑效率。

也就是“增、删、改、查”其元素的效率问题，不同存储方式的选择在“增、删、改、查”的某一方面更有优势，因为任何一种存储方式都不能做到“增、删、改、查”的全面效率最优，这也是多种容器存在的原因。

容器由怎样操作容器元素来定义，如怎样访问？怎样增加元素？怎样删除元素？怎样遍历元素（定义迭代器）？怎样附加内存来增大容量由分配器来定义，存储何种类型由类型参数泛化来定义（泛型），除此以外，如何对这些元素应用一些常用（或叫通用）的一些操作，如排序，则由算法来定义。

如何访问？容器元素排列的前面、后面、中间任意位置？如顺序存储的vector<T>、array<T,N>、deque<T>就可以随机访问，链式存储的List<T>却只能顺序访问，而对顺序存储且有操作功能限制的stack<T>却只能在顶端访问，queue<T>能在两端访问；

怎样增加、删除元素？容器元素排列的前面、后面、中间任意位置？vector<T>定义在容器的末尾增、删元素，deque<T>定义在容器的一端插入、另一端删除，而链式存储的list<T>却可以在任意位置插入，且效率很高。queque<T>则是在定义在头部弹出、尾部插入，而stack<T>则是定义在顶部删除。

怎样遍历元素？定义和使用不同的迭代器。不同类的迭代器的差别在于重载了不同的操作符：iter++、*iter、iter+n、iter-n、iter+=n、iter1-iter2、iter<=iter2、iter[n]等。

怎样增大容量？定义和使用分配器来给容器附加内存。

怎样应用一些常用（或叫通用）的一些操作，如排序、查找？算法，且通过迭代器让算法能独立于具体的容器。（也就是同样的算法可以应用到不同的容器）

有时需要对一些容器的功能进行适当限制，以适应一些实际问题的需要，如stack<T>、queue<T>，在STL中，这种对容器的重新定义称为适配器。

所以STL包括容器、迭代器、算法、适配器、分配器等内容，迭代器就是容器与算法的接口：

此外STL还包括仿函数（函数对象，functor）这一概念，也就是在类中重载函数调用运算符()，函数对象是重载()运算符（函数调用运算符）的类类型的对象，即该类实现operator()()函数。如果操作符是一对括号，操作数是函数的参数时，一个对象的操作符重载是不是不就像是函数的调用呢？既然把对象“伪装”成了函数，那么函数对象就有了一些新的特性。函数对象可以有成员数据和成员函数，它们都是被封装起来的。当“调用”函数对象时，只是调用该对象的一个操作符重载。只要这个对象没有被析构，其成员数据可以保存这个函数的各种状态，其成员函数能够提供接口，让外部了解其内部状态。

Vector容器表示一个在必要时可自动增加容量的数组，该数组存储T类型的元素。只能在矢量容器的末尾添加新元素。

array容器表示一个数组N，它存储指定数量的T类型元素。与普通数组相比，这个容器的一个优点是它知道其大小，所以把array<>容器传递给函数时，它仍知道所存储元素的个数。array<>容器优于vector<>的一个优点是，它可以完全在栈上分配内存，而vector<>总是需要访问堆。

deque容器实现一个双端队列，它存储T类型的元素。它等价于一个矢量，但增加了向容器开头添加元素的能力。

list容器是一个双向链表，它存储T类型的元素。

forward_list容器是一个单向链表，它存储T类型元素。只要以前向方式处理链表中的元素，在forward_list中插入和删除元素就比在list中快。

map是一个关联容器，用关联键（类型为K）存储T类型的每个元素。键/对象对在映射中存储为pair类型的对象，pair是另一个STL模板类型。键确定键/对象对的位置，用于检索对象。映射中的每个键必须唯一。这个头文件也定义了multimap容器，其中键/对象对中的键不需要唯一。

queue容器由deque容器中的适配器定义，但可以用list容器来定义它。只能访问队列中的第一个和最后一个元素，而且只能从后面添加元素，从前面删除元素。因此queue容器的运行过程或多或少就像我们在咖啡店排队一样。

stack容器用deque容器中的适配器定义，但可以用vector或list容器定义它。栈是一种后进先出容器，因此添加或删除元素总是发生在顶点，并且只能访问顶点的元素。（不能通过迭代器来进行访问）

所有的容器（不包括适配器）都有一些共同的方法，如size()返回元素数量，begin()、end()分别返回指向第一个元素、最后一个元素的迭代器。

总结一下，STL重点解决了三个方面的问题：

1 元素数量弹性；（分配器实现内存增加）

2 元素类型参数化；（模板技术实现泛型）

3 算法独立于容器；（迭代器技术实现元素遍历）

三方面的泛化：

1 类型的泛化：模板技术让容器不局限于具体类型；

2 迭代器的泛化：迭代器是指针的泛化，如vector可以用指针实现迭代器，list可以通过类实现迭代器。迭代器的使用除了声明有所区别以外，其它方面基本一致，如：

vector<double>::iterator pr;
//list<double>::iterator pr;
for(pr=ins.begin(); pr != ins.end(); pr++)
{cout<<*pr<<endl}

3 算法的泛化：因为迭代器的泛化，可以让算法独立于具体的容器。也就是说，算法能够独立于具体的容器、独立于具体的类型。

vector容器使用实例：

#include <iostream>
#include <vector>
int main ()
{
 std::vector<int> myvector;
 for (int i=1; i<=5; i++) myvector.push_back(i);
 std::cout << "myvector contains:";
 for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)
 std::cout << ' ' << *it;
 std::cout << '\n';
 return 0;
}
Output:
myvector contains: 1 2 3 4 5

list容器使用实例：

#include <iostream>
#include <list>
#include <vector>
int main ()
{
 std::list<int> mylist;
 std::list<int>::iterator it;
 // set some initial values:
 for (int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5
 it = mylist.begin();
 ++it; // it points now to number 2 
 mylist.insert (it,10); // 1 10 2 3 4 5
 // "it" still points to number 2
 mylist.insert (it,2,20); // 1 10 20 20 2 3 4 5
 --it; // it points now to the second 20 
 std::vector<int> myvector (2,30);
 mylist.insert (it,myvector.begin(),myvector.end());
// 1 10 20 30 30 20 2 3 4 5
 std::cout << "mylist contains:";
 for (it=mylist.begin(); it!=mylist.end(); ++it)
 std::cout << ' ' << *it;
 std::cout << '\n';
 return 0;
}
Output:
mylist contains: 1 10 20 30 30 20 2 3 4 5

map容器使用实例：

#include <iostream>
#include <map>
int main ()
{
 std::map<char,int> mymap;
 std::map<char,int>::iterator it;
 mymap['a']=50;
 mymap['b']=100;
 mymap['c']=150;
 mymap['d']=200;
 it = mymap.find('b');
 if (it != mymap.end())
 mymap.erase (it);
 // print content:
 std::cout << "elements in mymap:" << '\n';
 std::cout << "a => " << mymap.find('a')->second << '\n';
 std::cout << "c => " << mymap.find('c')->second << '\n';
 std::cout << "d => " << mymap.find('d')->second << '\n';
 return 0;
}
Output:
elements in mymap:
a => 50
c => 150
d => 200

－End－