STL（Standard template Library）:c++的标准模板库
STL是算法和数据结构的软件框架，它包含了六大组件：算法、迭代器、容器、仿函数、配接器、空间配置器。
迭代器：我们可以把迭代器相当于智能指针，（其实指针也就是一个迭代器）迭代器的类型有：前向迭代器（适用于单链表），双向迭代器（适用于双向链表），随机迭代器（随机指向），反向迭代器。
容器：像vector，list，map，set这些都属于容器。分为序列式容器、关联式容器及其他容器。
序列式容器：vector、list、deque、string
关联式容器：set、map、multiset、multimap、hash_set、hash_map、hash_multiset、hash_multimap
其他容器：stack、queue、bitset
仿函数：我们之前在冒泡排序的时候用opertor()模拟实现仿函数，来实现排序的升序和降序。
配接器：是一种设计模式，它在原有类型的基础上扩展成为另一个接口，使原本因为接口不兼容而不能合作的类型可以一起工作。就类似于电源适配器一样。这里有应用于容器的适配器，应用于仿函数的适配器，应用于配接器的适配器等。
空间配置器：用户数据都是保存在内存中的，那么内存的申请释放（malloc/free）工作都是由“空间配置器”承担的。标准c++中提供了std::allocator类。
我们今天要模拟实现STL中的list:（STL库中的list是一个双向循环且带头节点的链表）
它的节点原型是这样的：
template<typename T> struct ListNode { struct ListNode* _next; //指向下一个节点，即后继节点 struct ListNode* _prev; //指向前一个节点，即前驱节点 T _data; ListNode(const T& data) :_data(data) ,_next(NULL) ,_prev(NULL) {} };
我们还要用到迭代器，重载了++、--、*、->、==、!=等操作符。主要实现了以下函数：
begin：指向的是第一个元素的位置，即头节点的下一个位置；
end：指向的是最后一个元素的下一个位置，即头节点的位置。
如图：
对于迭代器，还有一个重要的问题就是迭代器失效的问题，当然迭代器失效和指针指向未知区域的道理是一样的。存在的原因是删除的时候，在链表中，你删除一个元素后，指针必须修改位置，即保存起来以便找到下一个位置。
举个例子（迭代器失效）：
//list.cpp
#include<iostream> using namespace std; #include<list> #include<algorithm> void Print(list<int> l) { list<int>::iterator it = l.begin(); while(it != l.end()) { cout<<*it<<" "; ++it; } } int main() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); list<int>::iterator it = l.begin(); while(it != l.end()) { if(*it == 2) { l.erase(it); //it删除后不知道指向哪里 } ++it; } Print(l); return 0; }
看一下监视窗口：
删除前：
删除后：
那么怎么解决迭代器失效问题呢？
只要保存之前it的指向，以便找到下一个指向就ok啦。
list<int>::iterator it = l.begin(); while(it != l.end()) { if(*it == 2) { it = l.erase(it); //此处用it来接收解决迭代器失效问题 } ++it; }
运行结果：
再来说说list，对于库里边的list的函数，如push_back,pop_back,push_front,pop_front,Insert,Erase等函数，下面一 一实现一下哦。
//List.h
#pragma once #include<iostream> using namespace std; template<typename T> struct ListNode { struct ListNode* _next; struct ListNode* _prev; T _data; ListNode(const T& data) :_data(data) ,_next(NULL) ,_prev(NULL) {} }; template<typename T,typename Ref,typename Ptr> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T,T&,T*> Iterator; typedef ListIterator<T,const T&,const T*> ConstIterator; typedef ListIterator<T,Ref,Ptr> Self; ListIterator(Node* node) :_node(node) {} bool operator==(const Self& x) { return _node == x._node; } bool operator!=(const Self& x) { return _node != x._node; } Ref operator*() { return (*_node)._data; } Ref operator*() const { return (*_node)._data; } Ptr operator->() { return &(*_node)._data; } Self& operator++() { _node = (*_node)._next; return *this; } Self operator++(int) { Self tmp = *this; ++(*this); return tmp; } Self& operator--() { _node = (*_node)._prev; return *this; } Self operator--(int) { Self tmp = *this; --(*this); return tmp; } Node* _node; }; template<typename T> class List { public: typedef ListNode<T> Node; typedef ListIterator<T,T&,T*> Iterator; typedef ListIterator<T,const T&,const T*> ConstIterator; public: Node* BuyNode(const T& data) { return new Node(data); } public: List() :_head(BuyNode(T())) { _head->_next = _head; _head->_prev = _head; } public: Iterator Begin() { return (*_head)._next; } Iterator End() { return _head; } ConstIterator Begin() const { return (*_head)._next; } ConstIterator End() const { return _head; } public: void PushBack(const T& data) //尾插 { Node* tmp = BuyNode(data); Node* tail = _head->_prev; tail->_next = tmp; tmp->_prev = tail; tmp->_next = _head; _head->_prev = tmp; } void PopBack() //尾删 { Node* del = _head->_prev; Node* pre = del->_prev; Node* next = del->_next; pre->_next = next; next->_prev = pre; delete del; } void PushFront(const T& data) //头插 { Node* tmp = BuyNode(data); Node* next = _head->_next; _head->_next = tmp; tmp->_prev = _head; tmp->_next = next; next->_prev = tmp; } void PopFront() //头删 { Node* prev = _head->_prev; Node* next = _head->_next; prev->_next = next; next->_prev = prev; _head = next; } Iterator Insert(Iterator pos,const T& data) //某一个位置前插入 { Node* tmp = BuyNode(data); Node* prev = pos._node->_prev; Node* cur = pos._node; prev->_next = tmp; tmp->_prev = prev; tmp->_next = cur; cur->_prev = tmp; return tmp; } ConstIterator Insert(ConstIterator pos,const T& data) //某一个位置前插入 { Node* tmp = BuyNode(data); Node* prev = pos._node->_prev; Node* cur = pos._node; prev->_next = tmp; tmp->_prev = prev; tmp->_next = cur; cur->_prev = tmp; return tmp; } Iterator Erase(Iterator pos) //删除某个位置 { assert(pos._node && pos._node != _head); //判断节点是否为空，或只剩一个头节点 Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; return Iterator(next); //返回下一个位置 } bool Empty() //判断链表是否为空 { return _head == _head->_next; } T& Front() { return _head->_next->_data; } T& Back() { return _head->_prev->_data; } const T& Front() const { return _head->_next->_data; } const T& Back() const { return _head->_prev->_data; } void Swap(List<T>& l) { swap(_head,l._head); } template<typename InputIterator> void Insert(Iterator pos,InputIterator first,InputIterator last) { while(first != last) { Insert(pos,*first); ++first; } } void Insert(Iterator pos,ConstIterator first,ConstIterator last) //在pos位置插入一段区间 { for(;first != last;++first) Insert(pos,*first); } private: Node* _head; }; void PrintList(List<int>& l) { List<int>::Iterator it = l.Begin(); while(it != l.End()) { cout<<*it<<" "; ++it; } cout<<endl; }
//List.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" #include<vector> int main() { List<int> l; List<int> l1; const List<int> l3; l.PushBack(1); l.PushBack(2); l.PushBack(3); l.PushBack(4); l.PopBack(); PrintList(l); l.PushFront(0); PrintList(l); l.PopFront(); l.Insert(l.End(),4); l.Insert(l.Begin(),0); PrintList(l); cout<<"Front:"<<l.Front()<<endl; cout<<"Back:"<<l.Back()<<endl; cout<<"Empty:"<<l.Empty()<<endl; l1.Swap(l); PrintList(l1); PrintList(l); l.PushBack(10); l.PushBack(11); l.PushBack(12); l1.Insert(l1.Begin(),l.Begin(),l.End()); PrintList(l1); vector<int> v; v.push_back(55); v.push_back(66); l1.Insert(l1.Begin(),v.begin(),v.end()); PrintList(l1); char str[] = {'a','b'}; l1.Insert(l1.Begin(),str,str+2); PrintList(l1); return 0; } 运行结果：
