Question

C++的STL是如何实现算法和数据结构分离的？

Answer 1

STL看起来是使用了面向对象，但实际上是大部分都是面向过程了。

STL的很多算法，就拿sort函数来说吧。

void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp);

只要数据结构的跌代器是随机访问的就可以使用。比如vector, list，同时也兼容普通数组int[]。

这里说到跌代器，STL有一整套跌代器的实现标准：

1、实现begin和end函数，是要全局的

如vecotr：

vecotr<T>::Iterator begin(vecotr<T>);

而不是 vecotr<T>的成员函数begin，这点要区分。

2、跌代器实现前至++运算

3、跌代器实现 * 运算

4、跌代器实现 != 运算

基本这四点就可以完成了，可以根据这个规则自己实现一个跌代器。

有了跌代器后，那么对于算法来说他们基本就一样了，开头，结尾，自增，以次访问就可以了。

所以一个sort就可以

vecotr<int> a;
string b;
list<float> c;

sort(a.begin(), a.end());
sort(b.begin(),b.end());
sort(c.begin(),c.end());

static bool less(int a1, int a2)
{
    return a1 < a2;
}

sort(a.begin(), a.begin()+5, less); // 对前5个排序
sort(a.begin(), a.end(), less);
sort(a.begin(), a.end(), [](int a1, int a2) {
    return a1 <= a2; // 匿名函数
});

结论就是算法跟数据结构是通过跌代器进行沟通的，所以学好跌代器，STL才算学好，要会用，也要懂为原理。

Answer 2

自然是通过泛型编程的模板来实现的。