数据结构
研究数据的特定排序方式，以利于搜索、排序或者其他特殊目的，这样的一门学科我们称为数据结构。
任何数据结构都不是平白无故的被创造出来，而是为了实现某种特定的算法来才被创造出来的。
算法，问题之解法也
以有限的步骤，解决逻辑或者数学上的问题，这样一门学科我们称之为算法。
算法是为了解决问题而设计出来的方法。要解决的问题就是我们要实现的特定目的。
就像在操作系统中一样，文件时管理数据的基本单位，一个文件在存储时被分为两部分，文件属性和数据。文件属性真正决定了这个文件是否存在，而这个文件存在的意义在于管理和存放文件中的数据。就像一个装着米粒的碗，碗是我们的文件，但是碗中的米才是我们的数据。碗是容器，是为了我们能够存放和管理数据。
而在这里也相同，数据结构是容器，容器中存放的数据是我们关心的对象。容器中的数据都是按照特定的排列方式来存放的，之所以将容器中的数据按照不同的特定顺序来放置为了实现特定的目的，可能是排序，可能是搜索等。所以任何数据结构都不是平白无故的被创造出来的，数据结构的产生都是为了实现一定的算法。
容器主要分为两大类，序列式容器和关联式容器。
STL
STL从广义上可以分为三个组成部分：容器、算法和迭代器。
所以stl的一个重要特性就是实现了数据和操作之间的分离。数据按照特定的排列方式存放在数据结构中，也就是容器之中（不同的容器内的数据具有不同的排序方式，就是为了实现不同的算法）。而操作就是指操作数据的函数，也就是我们所说的算法。我们前面说过，数据结构，也就是不同的容器被设计出来都是为了实现不同的算法，所以算法是要用来操作数据的。容器与算法之间通过迭代器来实现无缝衔接，充当两者之间的粘合剂，以便算法和容器交互运作。
所以，stl的中心思想就是将容器和算法分开，彼此独立设计，最后再用一贴胶着剂将两者沾和再一起。
STL具有高性能、高移植性、跨平台和高可重用性的特点。在这里我们重点解释一下高可重用性。
高可重用性：STL中几乎多有的代码都是通过模板了和模板函数的方法来实现的，这相比于传统的由类和函数组成的库来说提供了更好的代码重用机会。
这个点在编写代码上的影响：
因为stl中几乎所有的代码都是使用模板类和模板函数来实现的，所以在编写程序的时候第一步一定要传入的参数就是数据类型。粘合不同的容器和算法的迭代器是专用的，所以在声明迭代器的时候要加上作用域运算符，表明迭代器的类型。如下
vector<int> vec; vector<int>::iterator it1;
上述两行代码无论是在声明迭代器还是在声明vector容器都传入了类型参数int型。
注意：
这里声明的迭代器其实就是int* it1，也就是说vector容器的迭代器就是普通指针，同义不同名而已。其迭代器和指针的用法完全相同。
vector容器
vector容器又称动态数组，其数据安排和操作方式与数组非常相似。两者之间唯一的差别在于空间运用的灵活性。
数组array是静态空间，一旦配置了之后空间大小就不再发生变化。当数组空间不足时就会产生溢出，如果想要换大点的或者小一点的空间，一切操作都要我们自己手动操作进行，具体过程为1.首先申请一块新的内存空间，2.将原来内存空间中的数据拷贝到新的内存空间中，3.释放掉旧的内存空间。
而vector容器是动态数组，当数组空间不足时，vector容器会自动配置更大的内存空间。在vector容器动态增加内存空间时并不是在原有的内存空间尾部添加新的内存空间（无法保证原有的内存空间尾部还有空闲的内存空间），而还是“配置新的内存空间-拷贝数据-释放原空间”过程，但是这些过程不再需要我们来手动操作，由其内部算法自动实现。
vector容器的数据结构非常简单，仍然是线性连续空间。但是分别以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中已经使用的范围，即指向vector中第一个元素和最后一个元素，并以_Myend指向整块连续内存空间的尾端，就是指向最后一个元素的下一个位置。
vector容器的示意图如下
注意：
1.观察vector容器的逻辑示意图可知，这是一个单向开口的容器，类似于栈的逻辑。但是与栈的逻辑不同的是vector容器是可以在vector容器的中部和底部插入数据的，但是在底部操作效率奇差，无法被接受；而栈只能在栈顶插入和删除元素。
2.图中所示的v.rend(), v.begin(), v.rbegin(), v.end()都是迭代器，指的是vector中的位置；而front(), back(), pop_back(), push_back()是方法，也就是操作。
deque容器
deque是一种双向开口的连续线性空间。双向开口是一种逻辑结构，就是指可以在头尾两端分别做元素的插入和删除操作。而vector容器是一种单向开口的容器，但是也可以在头尾两端插入元素，但是在头部做插入和删除操作的效率奇差。
deque的逻辑图如下
1.如图所示，deque容器是一个双向开口的容器，可以通过push_front(), pop_front()方法在头部操作元素，通过push_back(), pop_back()方法在尾部操作元素。
2.deque容器允许常数项时间对头部进行元素的插入和删除操作，但是vector容器在头部插入和删除元素的效率奇差。
3.vector容器在内存中占据一块连续的内存空间，是真正意义上的连续线性空间，有容量的概念，在内存空间不足时则配置一段新的内存空间-复制元素-释放旧的空间来实现扩充；而deque容器则是分段连续空间组合而成，没有容量概念，可以随时增加一段新的空间并衔接起来，具体看实现原理部分。
4.deque容器也提供了迭代器，但是他的迭代器并不是普通的指针。与可以作为普通指针使用的vector容器迭代器相比，其复杂度不是在一个两量级。因此，我们应该尽可能使用vector，而不是deque。
deque容器的实现原理
deque容器在逻辑上看是连续线性空间，但是在物理空间上并不是连续的，而是由一段段的定量的连续空间构成。一旦有必要在deque容器的前端或者尾端添加新的空间，便配置一段连续定量的空间，串接在deque的头部或者尾端。原理示意图如下
1.Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。
2.deque容器的最大工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间、复制、释放的轮回，但代价就是复杂的迭代器架构。
1 deque<int> deq; 2 push_front(ele); 3 pop_front(ele); 4 push_back(ele); 5 pop_back(ele);
stack容器
stack容器，又称栈，是一种先进后出的数据结构，它只有一个出口，逻辑结构如图所示。
如图所示，栈的所有操作都在栈顶进行，除了栈顶位置，其他任何位置不允许进行操作。也就是栈容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有其他任何方法可以取得stack的其他元素。换言之，stack不允许由遍历行为，只能操作栈顶元素。
有元素推入栈的操作叫做入栈，使用方法push()实现；将元素推出栈的操作称为出栈，通过方法pop()实现。获得位于栈顶位置的元素通过方法top()来实现。
注意：
1.栈容器只能操作栈顶的元素和进行出栈、入栈操作，而不能够获得其他位置的元素，所以不支持遍历行为，也。
2.stack不提供遍历功能，也不提供迭代器。
stack<int> stk; stk.push(ele); stk.top(); stk.pop();
queue容器
queue容器，又称队列，是一种先进先出的数据结构。队列和dequeue相同，都有两个开口，但是与dequeue不同的是queue容器只允许从一端增加元素，而从另一端删除元素。queue的逻辑图如下
1.队列是一种先进先出的数据结构，数据元素只能从队列容器的尾部进入队列，而只能从对头出队。那么也就是说，只能访问获得队尾的元素和队头的元素，而在队尾向队列中添加元素，称为入队，从队头中移除元素，称为出队。
2.我们通过方法back()访问队尾的元素， front()方法访问队头的数据元素， push()从队尾向队列添加元素， pop()方法从对头移除元素。
3.对于一个队列而言，除了队头元素和队尾元素之外，我们无法操作其他任何元素，所以队列容器也不提供遍历功能，不能够访问队列中间的数据元素。换言之，队列中部的元素对我们来说是黑匣子，所以队列容器也不提供迭代器。
1 queue<int> que; 2 pop(); 3 push(); 4 back(); 5 front();
List容器
List容器就是我们所说的链表，链表容器在逻辑上是一种顺序和连续的数据结构，但是链表在物理空间上是非连续和非顺序的。物理空间上的非连续表现为逻辑空间上的连续是通过链表中的指针实现的，链表结点中的指针依次衔接起来表现为逻辑上的顺序表。
链表由一系列结点组成，结点可以在运行时动态生成。每个结点由两部分构成：一是存放数据元素的数据域，一是存储下一个结点实现衔接作用的指针域。
而在c++的STL库中list容器是双向链表，在链表每个结点的指针域都存放了两个指针，分别是prev和next。除了第一个结点和最后一个结点，其他结点的prev指针都指向该节点的前一个结点，next指针都指向该节点的下一个结点。而第一个结点的prev指针置为NULL，next指针指向第二个节点，最后一个结点的next指针置为NULL，prev指针指向倒数第二个结点。其逻辑图如图所示
1.List容器每次插入和删除一个元素都是配置或者释放一个元素的空间，因此，list容器具有优秀的内存空间利用率。
2.list容器采用动态存储分配内存空间，不会造成内存的溢出和浪费。
3.list容器执行插入和删除操作只需修改前后结点中指针的指向即可，不需要移动大量的数据元素。所以，对于任何位置的元素的插入和移除操作，list永远都是常数项时间。
list容器的迭代器
list容器的迭代器必须能够指向list容器内的数据元素，也就是list的结点上，并且能够支持递增、递减、取值、成员存取等操作。但是list容器在内存中并不是连续的，所以这就决定了list容器的迭代器不能够像ector容器那样以普通指针作为迭代器。
由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.
list容器和vector容器的对比
1.vector容器是动态数组，在内存空间不足时，会按照一定的算法来扩展内存空间，扩展的内存空间是按照原来内存空间的一定倍率扩展的；而List容器则是按照逐渐增加结点数，使用多说就增加多少个结点。
2.vector容器具有容量和存储存储量的概念，而list容器没有。
3.vector容器在插入数据元素时，当存储数量达到vector容器的容量而继续向迭代器中添加元素时，就会导致vector容器重新配置一块更大的内存空间，那么这个重新配置的操作很可能就会改变vector容器中内存空间的改变而使原来的迭代器失效。但是list容器在增加元素时，只是创建了一个新的结点改变前后结点中指针的指向将这个结点添加到list中去，并不会导致原有结点的内存地址的改变，所以不会引起原有迭代器的失效。甚至在list容器删除元素时，也只是会导致指向删除结点的迭代器失效，而不会对其他迭代器造成任何影响。
原文：https://www.cnblogs.com/hxhlrq/p/13577019.html