本文預(yù)覽：
- 迭代器的分類
- 不同迭代器對算法的影響
- 算法舉例及源碼剖析
- 仿函數(shù)
- 適配器
概覽
前面說的都是關(guān)于容器的東西烤蜕，容器占到了STL大概百分之八十的內(nèi)容，數(shù)據(jù)結(jié)構(gòu)的地位是如此重要讽营，程序只有數(shù)據(jù)結(jié)構(gòu)還是不夠的，這次來說說算法橱鹏。STL提供了大概八九十個算法，包含在<algrithms>頭文件里莉兰，數(shù)據(jù)結(jié)構(gòu)是算法的底層基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)提供了算法操作的對象杉辙，而算法怎么去操作數(shù)據(jù)結(jié)構(gòu)，這個是由迭代器來完成的蜘矢。也就是說迭代器在算法和容易之間起到了一個粘合劑的作用泉孩。
迭代器的分類
迭代器分為五個類型：
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_iterator_tag : public bidirectional_iterator_tag {}; //隨機訪問型县耽，連續(xù)內(nèi)存vector镣典、array等
每一種迭代器都是一個class
我們可以通過代碼來測試每一種容器對應(yīng)迭代器的類型：
void _display_category(random_access_iterator_tag)
{
cout<<"random_access_iterator_tag"<<endl;
}
void _display_category(bidirectional_iterator_tag)
{
cout<<"bidirectional_iterator_tag"<<endl;
}
void _display_category(forward_iterator_tag)
{
cout<<"forward_iterator_tag"<<endl;
}
void _display_category(output_iterator_tag)
{
cout<<"output_iterator_tag"<<endl;
}
void _display_category(input_iterator_tag)
{
cout<<"input_iterator_tag"<<endl;
}
template <typename T>
void display_category(T ite) {
typename iterator_traits<T>::iterator_category cagy;
_display_category(cagy);
cout<<"typeid(ite).name() = "<<typeid(ite).name()<<endl;
};
int main(int argc, const char * argv[]) {
display_category(array<int, 1>::iterator());
display_category(vector<int>::iterator());
display_category(list<int>::iterator());
display_category(map<int, int>::iterator());
display_category(set<int>::iterator());
display_category(istream_iterator<int>());
display_category(ostream_iterator<int>(cout, ""));
return 0;
}
不同迭代器對算法的影響
舉一個簡單的例子：
算法distance計算迭代器的距離唾琼，如果是random_acess_iterator_tag類型的，我們看到锡溯，直接一次計算，時間復(fù)雜度O(1)祭饭，可忽略不計；但是如果是input_iterator_tag類型的倡蝙，那么時間復(fù)雜度是O(n)，也就是說猪钮，迭代器對算法實現(xiàn)復(fù)雜度是有影響的。
再舉一個例子advance：
算法advance對迭代器執(zhí)行遷建或者后退操作烤低。都是根據(jù)迭代器類型笆载，來決定進行那種類型的操作拂玻。
算法舉例及源碼剖析
1宰译、 count_if()
返回滿足條件的元素個數(shù)
vector<int> a = {1,3,2,8,7,4,6};
cout<<count_if(a.begin(), a.end(), bind2nd(less<int>(), 4));
可能需要對bind2nd做出解釋一下，這一句的意思是對仿函數(shù)less的第二個參數(shù)綁定為40沿侈，整句的意思是：輸出vector a中小于4的元素個數(shù)。
剛剛接觸bind2nd不是很懂什么意思缀拭，這個剛開始我也不太懂，那就分心下源碼：
//第一步：開始找源代碼
template <class __Operation, class _Tp>
binder2nd<__Operation> //返回類型
bind2nd(const __Operation& __op, const _Tp& __x)
{return binder2nd<__Operation>(__op, __x);} //臨時對象binder2nd咙好，倆參數(shù)傳進去，構(gòu)造對象初始值
//第二步勾效，找到binder2nd
template <class __Operation>
class _LIBCPP_TYPE_VIS_ONLY binder2nd
: public unary_function<typename __Operation::first_argument_type,
typename __Operation::result_type>
{
protected:
__Operation op; //定義了操作類型，這里是less<int>
typename __Operation::second_argument_type value; //定義了操作的第二參數(shù)层宫，這里是 4
public:
_LIBCPP_INLINE_VISIBILITY
binder2nd(const __Operation& __x, const typename __Operation::second_argument_type __y)
: op(__x), value(__y) {} //構(gòu)造函數(shù)啊，在這里給上面定義的倆變量賦值
_LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator() //重載了()萌腿，一定是在哪里調(diào)到了
( typename __Operation::first_argument_type& __x) const
{return op(__x, value);} //這里就很明了了，調(diào)用的時候傳入了第一參數(shù)毁菱，我們?nèi)タ纯丛谀恼{(diào)用的。
_LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator()
(const typename __Operation::first_argument_type& __x) const
{return op(__x, value);}
};
//第三步贮庞，找在哪里調(diào)用了__Operation(typename __Operation::first_argument_type& __x)
template <class _InputIterator, class _Predicate>
typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
typename iterator_traits<_InputIterator>::difference_type __r(0);
for (; __first != __last; ++__first)
if (__pred(*__first)) //這一句就是了，仿函數(shù)調(diào)用勘天，我們看到傳入第一參數(shù)。
++__r;
return __r;
}
在STL里面的源碼我都加了注釋脯丝，一步一步找到調(diào)用的地方，簡單來說就是宠进，bind2nd通過binder2nd返回它的臨時對象，這個臨時對象記錄了操作(less<int>())和參數(shù)4材蹬，并重載了()吝镣，看到了沒堤器，這個就是仿函數(shù)了末贾，在count_if源代碼調(diào)用了()，傳入一個參數(shù)拱撵。這就是整個調(diào)用過程。我們這里實際上有兩處是仿函數(shù)拴测，一次是less<int>一次是binder2nd<less<int>>。這里我們并沒有看less的源代碼集索，有興趣可以看看汇跨，雖然很簡單渺鹦。
在C++11中bind2nd這個已經(jīng)被有了更好了用法扰法，那就是bind和lamda表達式毅厚。是因為這個太難理解了嗎浦箱？或許吧。
2酷窥、 accumulate()
累加計算
#include <iostream>
#include <algorithm>
#include <numeric>
#include "Measurement.h"
using namespace std;
struct myClass{
int operator()(int x, int y){
return 2*x+y;
}
} myobj;
int main(int argc, const char * argv[]) {
int init = 0;
int arr[] = {10,20,30};
cout<<accumulate(arr, arr+2, init)<<endl;
cout<<accumulate(arr, arr+3, init, myobj);
return 0;
}
3、 count()
count本身是一個算法蓬推，不是每一種容器都提供count，其中線性容器沒有count算法沸伏，而關(guān)聯(lián)容器由于本身的特性，它是已經(jīng)排好序的紅黑樹毅糟，所以本身提供count接口。
4喇肋、 find()
find需要注意的是一個問題是，在算法里提供了find算法蝶防，它的內(nèi)部實現(xiàn)是全遍歷，時間復(fù)雜度是O(n)间学，那么在所有的線性容器find都可以使用algorithms提供的算法贺喝，不需自己再寫菱鸥，但是set和map等關(guān)聯(lián)容器就不行了躏鱼，由于紅黑樹是一個高度平衡二叉樹，它自己內(nèi)部實現(xiàn)了更加效率的find算法染苛，其時間復(fù)雜度是O(log(n))主到，這也是為什么線性容器沒有find躯概，而關(guān)聯(lián)容器有find的原因登钥。
5娶靡、 sort()
sort方法有個特例，就是list姿锭，list內(nèi)部實現(xiàn)了自己的sort，而其他的容器沒有自己的sort呻此，關(guān)聯(lián)容器本身不需要實現(xiàn)sort，因其本身就是按順序排列的焚鲜，其他的線性容器可以統(tǒng)一使用算法提供的sort，而list由于自身的特殊性糯彬，不需要移動每一個元素，因此自身做了優(yōu)化情连。
仿函數(shù)
仿函數(shù)的已經(jīng)提過很多了览效，STL里面到處都是仿函數(shù)却舀，這也是我們唯一可以修改的地方了吧锤灿，仿函數(shù)寫起來還是比較簡單的，一是小但校，二是比較容易擴容，但是想要和標準庫兼容還是需要繼承通用的父類状囱，負責(zé)是不能和標準庫兼容的。
仿函數(shù)的適配條件：
這個跟函數(shù)適配器是有關(guān)系的袭艺。
適配器
適配器分很多類型：
- 容器適配器
- 函數(shù)適配器
- 迭代器適配器
容器適配器
stack和queue是容器，但是他們在本質(zhì)上是適配器猾编，他們本身并沒有實現(xiàn)什么結(jié)構(gòu)和算法，而是把deque拿過來答倡，接口改造一下，實現(xiàn)了自己需要的功能瘪撇。
函數(shù)適配器
我們前面分析的bind2nd就是一個函數(shù)適配器，我們使用一下C++11提供的bind適配器设江。
bind返回一個函數(shù)對象ret攘轩，調(diào)用ret，相當(dāng)于調(diào)用function
int main(int argc, const char * argv[]) {
using namespace std::placeholders;
//綁定函數(shù)
auto fn_five = bind(my_divide, 10, 2);
cout<<fn_five()<<endl;
auto fn_half = bind(my_divide, _1, 2);
cout<<fn_half(10)<<endl;
auto fn_invert = bind(my_divide, _2, _1);
cout<<fn_invert(2, 10)<<endl;
auto fn_rounding = bind<int>(my_divide, _1, _2);
cout<<fn_rounding(10, 3)<<endl;
//綁定成員函數(shù)和成員變量
myPair ten_two {10,2};
auto bound_memfn = bind(&myPair::multiply, _1);
cout<<bound_memfn(ten_two)<<endl;
auto bound_memdata = bind(&myPair::a, _1);
cout<<bound_memdata(ten_two)<<endl;
//舉例
vector<int> v {1,2,3,4,5,6,7};
auto fn = bind(less<int>(), _1, 5);
cout<<count_if(v.begin(), v.end(), fn);
cout<<count_if(v.begin(), v.end(), not1(bind2nd(less<int>(), 5)));
return 0;
}
迭代器適配器
list<int> foo, bar;
for (int i = 1; i <= 5; i++) {
foo.push_back(i);
bar.push_back(i*10);
}
list<int>::iterator it = foo.begin();
advance(it, 3);
copy(bar.begin(), bar.end(), inserter(foo, it));
for (auto x: foo) {
cout<<x<<' ';
}
輸出結(jié)果：
1 2 3 10 20 30 40 50 4 5
inserter迭代器適配器度帮，在copy的代碼寫的很清楚，但是怎么執(zhí)行插入操作的瞳秽？迭代器適配器重載了=操作符，使得每次賦值的時候都會執(zhí)行插入操作率翅。
ostream_iterator
向控制臺輸出
std::ostream_iterator<int> out_it(std::cout, ",");
copy(foo.begin(), foo.end(), out_it);
