文章目录
问题
如果我们想给一个list排序，无法使用C++标准库中全局的sort函数，而要使用list自定义的sort函数。
#include <list>
#include <iostream>
int main()
{
std::list<int> li = { 2, 3, 52, 10, -1, 2, 4 };
sort(li.begin(), li.end()); // 编译出错
li.sort(); // 编译执行正常
for (auto x : li) {
std::cout << x << std::endl; // 升序打印
}
return 0;
}
那为什么不能用全局sort给list排序呢？
分析
在cppreference里查了一下，全局sort的声明是这样的：
模板参数是RandomAccessIterator，表明它接受的是随机访问迭代器，而list迭代器的类型是BidirectionalIterator类型的。
根据《STL源码剖析》里的内容，下面简单说一下调用函数是如何区分迭代器型别的。
迭代器型别
根据移动特性和实施操作，迭代器大概分为五种。详见【迭代器】迭代器相应型别
使用如下类型标识迭代器的分类属性：
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_tag : public bidirectional_iterator_tag {};
STL容器的迭代器都是定义在容器里的，list的迭代器属于Bidirectional Iterator：
template <class T>
class List {
public:
class Iterator {
public:
typedef bidirectional_iterator_tag iterator_category; // bidirectional iterator
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
struct ListNode {
T data;
ListNode *prev;
ListNode *next;
};
private:
ListNode *node;
};
而vector使用原生指针作为迭代器，属于Random Access Iterator。
template <class T>
class Vector {
public:
typedef T *Iterator; // 原始指针是可随机访问迭代器
private:
Iterator first;
Iterator finish;
Iterator end_of_storage;
};
为了屏蔽两种迭代器的差异，引入了iterator_traits类萃取迭代器的特性：
对list而言，使用泛化版本：
template <class Iterator>
class iterator_traits {
public:
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;
};
对vector而言，使用原生指针的偏特化版本：
template <class T>
class iterator_traits<T*> {
public:
typedef random_access_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T *pointer;
typedef T &reference;
};
使用迭代器类型重载
当调用MySort时，会萃取迭代器的类型，并调用对应的_MySort版本。
template <class Iterator>
inline void _MySort(Iterator first, Iterator last, random_access_tag)
{
std::cout << "random access iterator sort" << std::endl;
}
template <class Iterator>
inline void _MySort(Iterator first, Iterator last, bidirectional_iterator_tag)
{
std::cout << "bidirectional iterator sort" << std::endl;
}
template <class Iterator>
inline void MySort(Iterator first, Iterator last)
{
_MySort(first, last, typename iterator_traits<Iterator>::iterator_category());
}
测试一下：
int main()
{
List<int>::Iterator ite1;
List<int>::Iterator ite2;
MySort(ite1, ite2);
Vector<int>::Iterator ite3;
Vector<int>::Iterator ite4;
MySort(ite3, ite4);
return 0;
}
运行结果：
同时由于迭代器都是定义在使用它们的容器里的，因此不同的迭代器之间无法强转，由此在_MySort的各重载版本里可以安心地使用迭代器。
List<int>::Iterator ite1;
List<int>::Iterator ite2;
MySort(Vector<int>::Iterator(ite1), Vector<int>::Iterator(ite2));
编译出错：
结论
C++标准库中全局的sort只给random_access迭代器使用，由于其他类型的迭代器不支持-=运算，因此当把list的迭代器传给全局sort时会这样报错：