Question

c++的STL容器中的end()具体机制是怎么样

每次调用一个容器的成员函数end()的时候，就返回超出末位的迭代器，这里的时间复杂度是多少的。
因为这个容器不一定的vector,还可能是list之类的嘛。
是不是容器中有一个变量把end()的值记录下来，调用的时候直接返回就可以了呢，还是从begin()开始，自增size()个位置作为返回呢。
希望了解到它的具体实现，谢谢!

Answer 1

STL中为我们提供的最重要的两个内容是容器（vector，list等）和一系列的算法。在这些算法中有许多需要遍历容器中的所有元素，如search，sort等算法。STL的设计者希望将算法和容器分离开来，一个算法可以帮不同的容器实现功能。为此目的，STL应用到了《设计模式》中提到的迭代器模式。
《设计模式》中将迭代器模式定义为：提供一种方法，使之能依序遍历容器中的每个元素，而不需要暴露容器内部的信息。在面向对象的设计里，实现迭代器，我们会为所有的迭代器提供一个统一的接口，然后更个容器的迭代器继承这个接口，然后在使用处通过接口来实现对不同迭代器的调用。但STL是采用泛型思维，利用摸版来实现的类库，所以它的迭代器的实现和面向对象稍有不同，但原理类似。在此将通过例子来具体看看STL中迭代器的实现。
我们先来看看find()函数的实现：
//摘自stl_algo.h
template<typename _InputIter, typename _Tp>
inline _InputIter
find(_InputIter __first, _InputIter __last,
const _Tp& __val,
input_iterator_tag)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}

find()函数的功能是在一个容器中查找一个元素，需要遍历两个迭代器对象_first和_last所在的区间。在此我们看到它对区间的遍历是通过++__first来实现的。也就是说迭代器需要重载++运算符来实现对容器的遍历。来具体看看vector和list中的迭代器实现。
我们知道vector中的元素是连续存放的，类似于数组，在数组中可以通过指针很容易的实现对数组的遍历，在vector中也一样，并不需要提供给它专门的迭代器类，通过指针就可以实现迭代器的功能。看看例子：
#include<iostream>
#include<vector>
using namespace std;

template<typename _InputIter, typename _Tp>
inline _InputIter
myfind(_InputIter __first, _InputIter __last,
const _Tp& __val)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}

int main()
{
vector<int> vec;

for( int i = 0; i < 10 ; i ++ )
vec.push_back(i);

int *p0 = &vec[0];
int *p1 = &vec[10];

int *p2 = myfind(p0,p1,6);

if ( p2 != &vec[10])
cout << *p2 << endl;

system("pause");
return 0;
}
例子中，我对find做了改动，改成了myfind，这是因为3.3.1的源代码中加入了traits技巧（在VC中我们是可以直接用find的），稍后我们将讲到该问题。但这里可以看到，通过指针就可以实现对vector的遍历。一般我们对迭代器的使用是如下的方式：
vector<int>::iterator it;
这里需要借助vector来定义迭代器，这里主要是为容器的使用提供一种统一的方式。因为list容器不能通过指针来实现遍历，它们需要实现自己的迭代器。我们来看看在vector中对于iterator的实现：
template<typename T,class Alloc = alloc >
class vector
{
public:
typedef T value_type;
typedef value_type* iterator;

...
};
在此可以看到iterator在vector中也只是简单的被定义成了我们传入的类型参数T的指针（在3.3.1的代码中与这里的代码并不一样，还是traits的原因）。我们使用迭代器的一般方式是如下：
find(vec.begin(),vec.end,6);
再简单看看begin和end函数的实现：
template<typename T,class Alloc = alloc >
class vector
{
proteted:
iterator start;
iterator finist;
public:
iterator begin(){return start;}
iterator end(){return end;}
...
};
这里可以看到，只是为vector设置一个头指针和尾指针，然后通过begin和end来得到这两个指针。
list就不可以直接通过指针来实现迭代器了，因为它里面的元素是不连续的。需要我们自己去实现，我们先把list的定义抽出来看看。
template <class _Tp >
struct _List_node {
_List_node< _Tp>* _M_next;
_List_node< _Tp>* _M_prev;
_Tp _M_data;
};
template <class _Tp, class Alloc = alloc>
class list {
protected:
_List_nod<_Tp>e* node;
....
public:
void push_front(const _Tp & x);
void push_back(const _Tp & x);
....
};
为了便于理解，我将代码进行了简单的修改，事实上3.3.1里的代码要比这个要复杂一些。一般来说设计一个链表，我们会把它分成两部分：_List_node用来存放数据，list用来操作链表。这样，迭代器实际传回的应该是_List_node，当它向前遍历的时候，传回的应该是它的下一个结点。按着这个结构，为链表来设计一个迭代器，如下：
template<class T>
struct __list_iterator {
_List_node<T>* node;
__list_iterator(_List_node<T>* x) : node(x) {}
__list_iterator() {}

bool operator==(const __list_iterator<T>& x) const { return node == x.node; }
bool operator!=(const __list_iterator<T>& x) const { return node != x.node; }

T& operator*() const { return (*node)._M_data; }

__list_iterator<T>& operator++() {
node = (_List_node<T>*)((*node)._M_next);
return *this;
}

__list_iterator<T> operator++(int) {
__list_iterator<T> tmp = *this;
++*this;
return tmp;
}

};
我们可以看到，迭代器中重载了==，！=，*，++等操作符，这是因为这些操作是在算法中经常要用到的操作符。看看myfind中实现，就可以明白：
while (__first != __last && !(*__first == __val))
++__first;
这里要用到两个迭代器的比较（__first != __last），所以我们需要重载等于运算符；迭代器中值的比较（*__first == __val），这时候比较的不再是迭代器，而是迭代器所包含的内容（这里是_List_node的对象），所以我们需要重载*来得到它；最重要的就是遍历的实现，需要重载++运算符，这里是通过node = (_List_node<T>*)((*node)._M_next);将迭代器中的_List_node对象改为它的下一个对象来实现的。这样我们就完成了迭代器的设计。再来看看它的用法：
int main(int argc, char *argv[])
{
list<int> mylist;

for(int i = 0;i <= 10; i++ )
{
mylist.push_back(i);
}
// mylist.begin()得到的是STL本身提供的迭代器，所以我们需要得到它所包含的_List_node<T>对象指针。
_List_node<int>* p1 = (_List_node<int>*)mylist.begin()._M_node;
_List_node<int>* p2 = (_List_node<int>*)mylist.end()._M_node;

//这里用我们得到的指针来生成我们自己的迭代器
__list_iterator<int> it1(p1);
__list_iterator<int> it2(p2);

__list_iterator<int> it3 = myfind(it1,it2,6);

if ( it3 != it2 )
cout << *it3 << endl;

system("PAUSE");
return 0;
}
实际的迭代器的设计中，还会重载--和->运算符，感兴趣的可以自己看看源代码。还是和vector一样，STL会把迭代器的定义绑定到list类中去，我们来看看它的具体做法：
typedef _list_iterator<_Tp> iterator;
其实和vector一样，只要把以上的定义放到list类中，就可以了，然后，我们就可以通过list<int>::iterator ite 来定义list的迭代器了，事实上它生成的就是一个_list_iterator<int>对象。
从此可以看到迭代器就是为各个容器生成一个可以迭代自身的类，而再通过typedef来把该迭代类绑定到容器类中，这样就给了外部一个形式统一的使用方法。
除了遍历，迭代器中还用到了一个重要的技巧——traits。我们先来看看traits的用处。

template <class ForwardIterator1, class ForwardIterator2, class T>
inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {
T tmp = *a;
*a = *b;
*b = tmp;
}
该方法是用来实现两个迭代器中内容的交换，我们可以看到此处需要一个临时变量tmp，而tmp所对应的类型是它所包含的对象的类型。这样我们就需要传入一个类型参数T*进去，如果我们不想传这个参数进去可不可以呢？这时候就需要用到traits技巧了。事实上traits并没有什么太难理解的部分，还是看看例子：
template<class T>
struct __list_iterator {
typedef T value_type;
….
};
现在我们在__list_iterator头部加typedef T value_type;这么一句话，然后我们重新写一下迭代器的交换函数，如下：
template <class ForwardIterator1, class ForwardIterator2>
inline void myiter_swap(ForwardIterator1 a, ForwardIterator2 b) {
typename ForwardIterator1::value_type tmp = *a;
*a = *b;
*b = tmp;
}
此时，就可以通过typename ForwardIterator1::value_type来定义临时变量了，看看它的效果：
int main(int argc, char *argv[])
{
list<int> mylist;

for(int i = 0;i <= 10; i++ )
{
mylist.push_back(i);
}
_List_node<int>* p1 = (_List_node<int>*)mylist.begin()._M_node;
_List_node<int>* p2 = (_List_node<int>*)mylist.end()._M_node;

__list_iterator<int> it1(p1);
__list_iterator<int> it2(p2);

__list_iterator<int> it3(p2);
//交换第一个和最后一个元素的内容
myiter_swap(it1,--it3);
//打印所有的元素
for( ;it1 != it2;it1++)
cout << *it1 << endl;
system("PAUSE");
return 0;
}
事实上，在迭代器中还会包括指针，引用，还有就是两个迭代器之间距离的类型。所以迭代器的中的实际代码应该如下：
template<class T>
struct __list_iterator {
typedef bidirectional_iterator_tag iterator_category; //迭代器的类型，稍后解释
typedef T value_type; // 对象类型
typedef value_type*pointer; // 指针类型
typedef value_type& reference; // 引用类型
typedef ptrdiff_t difference_type; // 迭代器距离类型，关于这个参数，我也搞不明白为什么需要
…
};
这样具体的算法中就可以根据这些内容来定义自己所需要的类型了（STL的实际定义中和这里有些不同，在容器类（vector,list）中已经定义了这些类型，迭代器是再通过容器类定义，不过原理是一致的）。另外，STL中还提供了一个自己的萃取机，如下：
template<typename _Iterator>
struct iterator_traits {
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
有了它，我们的myinter_swap函数就可以变成以下的内容：
template <class ForwardIterator1, class ForwardIterator2>
inline void myiter_swap(ForwardIterator1 a, ForwardIterator2 b) {
typedef typename iterator_traits<ForwardIterator1>::value_type _ValueType1;
_ValueType1 tmp = *a;
*a = *b;
*b = tmp;
}

似乎这段代码并没有使代码变的方便？想想，我们的vector中并没有定义迭代器类，只是直接把指针当作了迭代器。如果直接用以上的代码明显是会出问题的，因为指针根本没有value_type这些信息。为了这种情况，STL中提供了萃取机中针对指针的偏特化版本：

template<typename _Tp>
struct iterator_traits<_Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
这样vector对象就可以使用myiter_swap了，不然肯定编译不过去。还有一些针对其它类型（如常量指针）的偏特化版本，可以自己看看源码。
在以上的代码中，我们看到了typedef random_access_iterator_tag iterator_category;这样的语句。iterator_category代表的是迭代器的分类，迭代器分为五种类型：
1， Input Iterator 这种类型的迭代器不允许外界改变，是唯读的。
2， Output Iterator 是唯写的。
3， Forard Iterator 可以读写，但它只能向前移动。
4， Bidirectional Iterator 可以读写，可以前后移动。
5， Random Access Iterator 可以读写，前后移动，并且支持p+n型的操作，也就是说可以前后移动多位，而不是一个一个的移动。
在STL中，它们被定义为如下的形式：
/// Marking input iterators.
struct input_iterator_tag {};
/// Marking output iterators.
struct output_iterator_tag {};
/// Forward iterators support a superset of input iterator operations.
struct forward_iterator_tag : public input_iterator_tag {};
/// Bidirectional iterators support a superset of forward iterator operations.
struct bidirectional_iterator_tag : public forward_iterator_tag {};
/// Random-access iterators support a superset of bidirectional iterator operations.
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

可以看到它们并没有实际的代码，只是作为一个标记来用的。具体作用的话，还是通过函数来看看。STL的算法中提供了这样一个函数distance，它的作用是求出两个迭代器之间的距离，为了统一，函数可能写成这样：
template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last)
{
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last) {
++__first; ++__n;
}
return __n;
}
这样的话，vector和list都可以使用这个函数，但这样一来，vector也需要遍历两个迭代器之间的所有内容了。但事实上，我们知道vector是连续的区间，完全可以通过两个迭代器之间的相减操作来完成这个计算。如果采用以上的操作，会降低它的效率。有什么办法来区分这两种操作呢？通过迭代器类型就可以完成，还是看看代码：
template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last) {
++__first; ++__n;
}
return __n;
}

template<typename _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag)
{
return __last - __first;
}
template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last)
{
typedef typename iterator_traits<_InputIterator>::iterator_category category;
return __distance(__first, __last, category ());
}
可以看到，STL提供了__distance的两个重载函数：一个针对input_iterator_tag，使用的我们上面提到的遍历的方法；一个针对random_access_iterator_tag，采用的直接相减的方法。并提供了distance函数，在该函数里通过
typedef typename iterator_traits<_InputIterator>::iterator_category category;来得到迭代器的类型，并通过category ()生成一个对象传入到__distance中，经过C++的重载机制实现了不同类型的调用。