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

456次浏览

STL看起来是使用了面向对象,但实际上是大部分都是面向过程了。
STL的很多算法,就拿sort函数来说吧。

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

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

这里说到跌代器,STL有一整套跌代器的实现标准:
1、实现begin和end函数,是要全局的
如vecotr:

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

而不是 vecotr的成员函数begin,这点要区分。
2、跌代器实现前至++运算
3、跌代器实现 * 运算
4、跌代器实现 != 运算

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

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

所以一个sort就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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才算学好,要会用,也要懂为原理。