|
Program into Your Language, Not in It——《代碼大全》。如何深入一門(mén)語(yǔ)言去編程？我認(rèn)為有三步：熟悉它；知道它的局限性；擴(kuò)展它。如何熟悉？不必說(shuō)，自然是看書(shū)看資料，多用多寫(xiě)。如何知曉其局限性？這步我們只能通過(guò)對(duì)比了，任何事物都有其自身的局限性，沒(méi)有任何東西是完美的（除了上帝哈 ）。在這里，我用C#與C++做對(duì)比，嘗試勾勒出C#與C++一些觀念上的不同。如何擴(kuò)展？這點(diǎn)我正在嘗試 。 C++的STLSTL包含六大組件：容器(Containers)、迭代器（Iterators）、算法（Algorithms）、仿函數(shù)（functors）、配接器（Adapters）、配置器（Allocators）。容器通過(guò)配置器取得數(shù)據(jù)存儲(chǔ)空間，算法通過(guò)迭代器來(lái)存取容器的內(nèi)容，仿函數(shù)協(xié)助算法完成不同的操作策略，配接器用來(lái)修飾或套接仿函數(shù)。這一整套配合，可以使我們完全掌控?cái)?shù)據(jù)在存儲(chǔ)器上的增刪查改。（在這里我很想畫(huà)一張圖出來(lái)，但是我找了很久，實(shí)在找不到好的工具，有沒(méi)有哪位同學(xué)能分享一些好的畫(huà)示意圖之類的工具呢？） 容器STL中，最常用的容器要算vector、list、map、set這四種了。C#中，對(duì)應(yīng)的容器分別是:List、LinkedList、Dictionary、HashSet。單看容器，其實(shí)它只是抽象出了一些邏輯結(jié)構(gòu)，根據(jù)不同的邏輯需要，在存儲(chǔ)器上反應(yīng)出不同的物理存儲(chǔ)結(jié)構(gòu)。這點(diǎn)C++和C#的抽象沒(méi)有什么不同，當(dāng)然，其實(shí)現(xiàn)上，很不相同。這點(diǎn)通過(guò)代碼的書(shū)寫(xiě)，就可以略窺一斑。 C++代碼如下： #include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec;
list<int> lst;
map<int,int> mp;
set<int> st;
for (int i = 0; i < 10; ++i)
{
vec.push_back(i);
lst.push_back(i);
mp.insert(make_pair(i, i));
st.insert(i);
}
cout << "vector: " << endl;
vector<int>::const_iterator iterVec(vec.begin());
while (iterVec != vec.end())
{
cout << *iterVec << endl;
++iterVec;
}
cout << "\nlist: " << endl;
list<int>::const_iterator iterLst(lst.begin());
while (iterLst != lst.end())
{
cout << *iterLst << endl;
++iterLst;
}
cout << "\nmap: " << endl;
map<int, int>::const_iterator iterMap(mp.begin());
while (iterMap != mp.end())
{
cout << "Key = " << iterMap->first
<< "Value = " << iterMap->second
<< endl;
++iterMap;
}
cout << "\nset: " << endl;
set<int>::const_iterator iterSet(st.begin());
while (iterSet != st.end())
{
cout << *iterSet << endl;
++iterSet;
}
} C#代碼如下： using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Net.Sockets;
using System.Net;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
List<String> list = new List<String>();
LinkedList<String> linkedList = new LinkedList<String>();
Dictionary<Int32, String> dic = new Dictionary<Int32, String>();
HashSet<String> set = new HashSet<String>();
for (int i = 0; i < 10; ++i )
{
list.Add(i.ToString());
linkedList.AddLast(i.ToString());
dic.Add(i, i.ToString());
set.Add(i.ToString());
}
Console.WriteLine("List: ");
foreach (var item in list)
{
Console.WriteLine(item);
}
Console.WriteLine("\nLinkedList: ");
foreach (var item in linkedList)
{
Console.WriteLine(item);
}
Console.WriteLine("\nDictionary: ");
foreach (var item in dic)
{
Console.WriteLine("Key = {0}, Value = {1}", item.Key, item.Value);
}
Console.WriteLine("\nHashSet: ");
foreach (var item in set)
{
Console.WriteLine(item);
}
}
}
}
C++并沒(méi)有內(nèi)置的foreach語(yǔ)句（貌似新的標(biāo)準(zhǔn)中有？），所以它通過(guò)迭代器來(lái)幫助它來(lái)完成迭代。而C#就非常方便了，在語(yǔ)法級(jí)別完成了這個(gè)功能。從寫(xiě)法上我們可以看到，c++的迭代器看上去是一個(gè)指針，是一個(gè)可以做自增操作的指針。c#迭代出的每個(gè)item則是當(dāng)前存放的數(shù)據(jù)。 迭代器STL中的迭代器有五種：輸入迭代器（Input Iterator）、輸出迭代器（Output Iterator）、前向迭代器（Forward Iterator）、雙向迭代器（Bidirectional Iterator）、隨機(jī)存取迭代器（Random Access Iterator）。C#中，沒(méi)有相對(duì)應(yīng)的迭代器概念。畢竟迭代器就是一個(gè)智能指針，而C#卻不支持指針（unsafe另算哈）。 輸入迭代器，只能一次一個(gè)向前讀取元素，并且只能讀取該元素一次。如果我們復(fù)制一份輸入迭代器，副本輸入迭代器和原來(lái)的輸入迭代器分別向前讀取一個(gè)元素，那么他們可能會(huì)遍歷到不同的值。以istream_iterator為列，代碼如下： #include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
int main()
{
//按Ctrl+Z結(jié)束輸入，或者按Ctrl+C取消輸入
istream_iterator<string> iterBegin(cin);
istream_iterator<string> iterEnd;
while (iterBegin != iterEnd)
{
cout << *iterBegin << endl;
++iterBegin;
}
} 輸出迭代器，與輸入迭代器相反，它的作用是將元素值一個(gè)個(gè)寫(xiě)入，所以只能作為左值。以ostream_iterator為列，代碼如下： #include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
int main()
{
ostream_iterator<int> iter(cout, "\n");
vector<int> vec ;
for (int i = 0; i < 10; ++i)
{
*iter = i;
}
} 前向迭代器，是輸入、輸入迭代器的結(jié)合，但是卻沒(méi)能用有輸入、輸入迭代器的全部功能，真心覺(jué)得這個(gè)迭代器很尷尬。前向迭代器提取值的時(shí)候，要確保它是有效的迭代器（比如到了序列尾端），而輸出迭代器卻不用（輸出迭代器不提供比較操作，無(wú)需檢查是否達(dá)到尾端）。我沒(méi)見(jiàn)過(guò)比較有代表性的前向迭代器，所以給不出代碼示例（囧…）。 雙向迭代器，在前向迭代器的基礎(chǔ)上增加了回頭遍歷的能力。寫(xiě)法上來(lái)說(shuō)，就是提供了自減操作。最合適的列子非鏈表的迭代器莫屬了。如下： #include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
int main()
{
list<int> lst;
for (int i = 0; i < 10; ++i)
{
lst.push_back(i);
}
list<int>::const_iterator iter(lst.begin());
while (iter != lst.end())
{
cout << *iter << " ";
++iter;
}
cout << endl;
while (iter != lst.begin())
{
--iter;
cout << *iter << " ";
}
} 隨機(jī)迭代器，在雙向迭代器的基礎(chǔ)上增加了隨機(jī)存取能力。寫(xiě)法上來(lái)說(shuō)，就是提供了加減法操作，還提供了大小比較操作(除了這個(gè)迭代器，其他都沒(méi)有大小比較，所以一般判斷迭代器是否結(jié)尾，是用 == 或者 != 來(lái)判斷)。最合適的列子就是vector的迭代器了。如下： vector<int> vec;
for (int i = 0; i < 10; ++i)
{
vec.push_back(i);
}
vector<int>::const_iterator iter(vec.begin());
cout << *(iter + 4) << endl; 至此，我們對(duì)C++迭代器有些基本的了解了?，F(xiàn)在讓我們探索一下這背后到底是怎么實(shí)現(xiàn)的。我們知道C++的STL是依靠模板(Template)來(lái)實(shí)現(xiàn)的，用C#的詞來(lái)描述就是泛型(Generic)。一個(gè)迭代器，其實(shí)是一個(gè)類型，一個(gè)遵循了一系列潛規(guī)則的類型。按照被潛的程度，分成兩種：自?shī)首詷?lè)，狼狽為奸。如果只是想自?shī)首詷?lè)的話，那么很簡(jiǎn)單，只要像下面這樣既可： #include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
template<typename Item>
struct ListIter;
template<typename T>
struct ListItem;
//作為存放元素的容器
template <typename T>
struct ListContainer
{
ListContainer() : _front(nullptr)
, _end(nullptr)
, _size(0)
{
}
void insert_front(T value)
{
ListItem<T>* newItem = new ListItem<T>(value, _front);
if (_front == nullptr)
{
_end = newItem;
}
_front = newItem;
}
void insert_end(T value)
{
ListItem<T>* newItem = new ListItem<T>(value, nullptr);
if (_end == nullptr)
{
_front = newItem;
_end = newItem;
}
else
{
_end->setNext(newItem);
_end = newItem;
}
}
void display(std::ostream &os = std::cout) const
{
ListItem<T>* tmp = _front;
while (tmp != nullptr)
{
os << tmp->value() << " ";
tmp = tmp->next();
}
os << std::endl;
}
ListItem<T>* front() const
{
return _front;
}
private:
ListItem<T>* _end;
ListItem<T>* _front;
long _size;
};
//每個(gè)元素
template<typename T>
struct ListItem
{
ListItem(T val, ListItem<T>* next) : _value(val)
, _next(next)
{
}
T value() const
{
return _value;
}
ListItem* next() const
{
return _next;
}
void setNext(ListItem<T>* next)
{
_next = next;
}
private:
T _value;
ListItem<T>* _next;
};
//迭代器
template<typename Item>
struct ListIter
{
Item* ptr;
ListIter(Item* p = 0) : ptr(p)
{}
Item& operator*() const { return *ptr; }
Item* operator->() const { return ptr; }
ListIter& operator++()
{
ptr = ptr->next();
return *this;
}
ListIter operator++(int)
{
ListIter tmp =*this;
++(*this);
return tmp;
}
bool operator==(const ListIter& i) const
{
return ptr == i.ptr;
}
bool operator!=(const ListIter& i) const
{
return ptr != i.ptr;
}
};
int main()
{
ListContainer<int> myList;
for (int i = 0; i < 10; ++i)
{
myList.insert_front(i);
myList.insert_end(i + 10);
}
myList.display();
ListIter<ListItem<int> > begin(myList.front());
ListIter<ListItem<int> > end;
while (begin != end)
{
cout << begin->value() << endl;
++begin;
}
} 上述代碼中，我們完全依賴自己的雙手，通過(guò)重載*、->、 ++、==、!=等操作符，實(shí)現(xiàn)了自己的行為上類似迭代器的迭代器。但是我們僅能自?shī)首詷?lè)而已，不能融入STL的大家庭。我們無(wú)法復(fù)用STL原有的輪子，也無(wú)法將我們的輪子完美的放進(jìn)STL（只需重載一下全局的!=操作符，可以使用STL的find）。我們?yōu)榱藢?shí)現(xiàn)這個(gè)迭代器，將容器的元素類型（ListItem）暴露了，而且還暴露了ListItem的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)（重載++操作符，用到了ptr->next()）,明顯不科學(xué)??！所以一般迭代器都是相應(yīng)的容器的設(shè)計(jì)者實(shí)現(xiàn)的，內(nèi)嵌在容器中。 如果想讓我們的迭代器能融入到STL中，那么，我們就必須為我們的迭代器實(shí)現(xiàn)五個(gè)“接口”,一個(gè)表示迭代器的類型iterator_category，一個(gè)表示值類型value_type，一個(gè)表示兩個(gè)迭代器之間的距離類型difference_type，一個(gè)表示迭代器的指針pointer，一個(gè)表示迭代器的解引用reference。這五個(gè)“接口”,就是STL關(guān)于迭代器的潛規(guī)則。比如一個(gè)定義良好的iterator_category可以幫助我們的迭代器在使用distance(),advance()之類的函數(shù)時(shí)，有更高的效率。為了幫助我們定義自己的迭代器，STL有一個(gè)結(jié)構(gòu)，只要我們繼承即可，在VS中輸入iterator然后轉(zhuǎn)到定義，即可看到下圖： 
下面讓我們來(lái)定義一個(gè)可以與STL“狼狽為奸”的迭代器。 #include <iostream>
#include <vector>
using namespace std;
template <typename T, typename container = ostream>
struct Our_OutputIterator : public iterator<output_iterator_tag,
T,
ptrdiff_t,
T*,
T&>
{
Our_OutputIterator(container& os) : _os(&os)
{
}
Our_OutputIterator<T, container>& operator*()
{
return *this;
}
Our_OutputIterator<T, container>& operator=(const T& _Val)
{
*_os << _Val << " " ;
return *this;
}
Our_OutputIterator<T, container>& operator++()
{
return *this;
}
Our_OutputIterator<T, container>& operator++(int)
{
return *this;
}
container* _os;
};
int main()
{
Our_OutputIterator<int> os(cout);
vector<int> vec;
for (int i = 0; i < 10; ++i)
{
vec.push_back(i);
vec.push_back(i + 100);
}
copy(vec.begin(), vec.end(), os);
} 看起來(lái)好像沒(méi)什么區(qū)別？其實(shí)這里面的區(qū)別大了。 STL迭代器的潛規(guī)則讓我們先從C#的接口談起，相信大家對(duì)接口這個(gè)概念都不陌生。能被foreach遍歷的類型，必須繼承了IEnumerable這個(gè)接口。能夠做比較運(yùn)算的類型，必須繼承了IComparable接口。接口，是個(gè)非常強(qiáng)的概念。它與類的虛函數(shù)相比，最大的不同就是：繼承該接口后，必須要實(shí)現(xiàn)接口中的方法，而虛函數(shù)則不必。有了這層語(yǔ)法上的限制，那么我們?cè)贑#中定義我們的泛型方法時(shí)，就可以強(qiáng)制一些規(guī)定，便于我們操作傳進(jìn)來(lái)的泛型實(shí)參。比如我們要定義一個(gè)排序算法。既然是排序，首先就要求元素能夠被比較，如果不能比較，那就只能呵呵了…下面貼代碼。 public void FunnyQuickSort<T>(IList<T> list, Int32 right, Int32 left) where T : IComparable<T>
{
Int32 start = right, end = left;
if (start >= end)
{
return;
}
T @base = list[start];
while (start != end)
{
while (start < end && list[end].CompareTo(@base) >= 0)
{
end--;
}
list[start] = list[end];
while (start < end && list[start].CompareTo(@base) <= 0)
{
start++;
}
list[end] = list[start];
}
list[start] = @base;
FunnyQuickSort(list, right, start - 1);
FunnyQuickSort(list, start + 1, left);
} 通過(guò)用where這個(gè)方法，規(guī)定元素T的類型必須是可比較的，來(lái)限制用戶程序員傳入的類型。使用接口約束，不緊能方便我們?cè)诜椒ㄖ凶龌谝欢ㄏ拗频倪壿嫴僮?，還能在需要的時(shí)候確定方法的返回類型以及一些類型的限定信息?？赡芎竺孢@兩個(gè)優(yōu)點(diǎn)在C#中還不怎么明顯，如果見(jiàn)識(shí)到STL為了這么簡(jiǎn)單的操作饒了多么大的彎，我們就能深刻體會(huì)到這種好處了。假設(shè)我們有這么個(gè)需求：需要返回一個(gè)兩個(gè)迭代器（迭代器一個(gè)在前一個(gè)在后，能形成半開(kāi)區(qū)間）間元素中的最大值。大家會(huì)怎么寫(xiě)這個(gè)方法？用C#,方法大概是這樣： 我們可以返回一個(gè)T或者IComparable<T>。這是由于傳進(jìn)來(lái)的值的類型已經(jīng)確定了是T。這是與C++最大的不同。在C++中，如果為通用的STL迭代器寫(xiě)一個(gè)算法，大概如下: 
這時(shí)候，我們應(yīng)該返回什么類型？我們甚至不知道這個(gè)迭代器指向的是什么類型！我們知道指向的值可以用*begin來(lái)表示，但是我們要怎么讓編譯器知道？這里可沒(méi)有C#的委托限制，無(wú)法用委托來(lái)確定類型。大家想到怎么確定迭代器指向的類型了嗎？沒(méi)錯(cuò)，是利用函數(shù)模板的參數(shù)推到機(jī)制。我們要在里面再嵌入一層函數(shù)，即可得到迭代器指向的元素的類型。最后看起來(lái)代碼像這樣： 
現(xiàn)在還剩一個(gè)問(wèn)題了，最上層的Max應(yīng)該返回什么類型？有兩個(gè)方法可以確定：我們?cè)贋镸ax加一個(gè)泛型參數(shù)指明返回類型；再在模板中加一個(gè)插件。前一種很簡(jiǎn)單，不過(guò)不是很優(yōu)雅，略過(guò)不談。如何在模板中加插件？還記得我們前面所說(shuō)的潛規(guī)則么？我們定義了五個(gè)“接口”，其中有一個(gè)是表示值類型的value_type。答案就在這！我們通過(guò)一個(gè)第三方的提取工具：iterator_traits，來(lái)獲得返回的值類型。代碼如下： 
將迭代器的類型傳入iterator_traits中，提取出定義該迭代器的時(shí)候定義的元素類型。這下所有的問(wèn)題都解決了。是不是很優(yōu)雅？當(dāng)然，不要跟C#比。下面我們測(cè)試一下我們的代碼： #include <iostream>
#include <vector>
using namespace std;
template<typename inputIter>
typename iterator_traits<inputIter>::value_type Max(inputIter begin, inputIter end)
{
typedef typename iterator_traits<inputIter>::value_type type;
type val = *begin;
while (begin != end)
{
if (*begin > val)
{
val = *begin;
}
++begin;
}
return val;
}
int main()
{
vector<int> vec;
for (int i = 0; i < 10; ++i)
{
vec.push_back(i);
}
vec.push_back(100);
vec.push_back(1);
cout << Max(vec.begin(), vec.end()) << endl;
} 我們看到，由于C++少了接口這個(gè)語(yǔ)法級(jí)的概念，實(shí)現(xiàn)一個(gè)這么簡(jiǎn)單的方法，都要繞這么大一個(gè)彎！而且在調(diào)試代碼的時(shí)候，模板出錯(cuò)的報(bào)錯(cuò)提示，是出了名的多！一個(gè)小問(wèn)題可以引起大段的錯(cuò)誤提示。其實(shí)上面的代碼很容易出錯(cuò)，如果迭代器指向的類型無(wú)法做邏輯比較怎么辦？比如將一個(gè)map的迭代器傳進(jìn)來(lái)，大家可以試一試！而C#從語(yǔ)法層面上將這些弊端都規(guī)避掉了。如果不符合接口限制，將會(huì)有優(yōu)雅的提示信息。返回類型可以直接返回接口類型。我真心感覺(jué)吊炸天！如果不與C++比較，我是無(wú)法知道C#為我做了這么多工作！想到STL是上世紀(jì)的杰作，我很佩服當(dāng)時(shí)為了解決這些問(wèn)題而探索出的traits方法。而C#作為后來(lái)者，明顯吸收了很多C++的精華。 通過(guò)容器和迭代器這兩個(gè)組件，我們可以看到STL的構(gòu)思之巧妙，通過(guò)一系列的潛規(guī)則，來(lái)實(shí)現(xiàn)了通用的目的。我們也看到了C#的方便之處。到目前的比較為止，C#的表現(xiàn)非常不錯(cuò)。但是，C#會(huì)一直這么拽嗎？有句話說(shuō)的好:“你不拽我們還可以做朋友…”。以我現(xiàn)在還和C#是朋友的現(xiàn)狀來(lái)看…… 我本來(lái)想以一篇來(lái)概括STL的，寫(xiě)了快10小時(shí)，發(fā)現(xiàn)還僅是寫(xiě)到第二個(gè)組件！現(xiàn)在只剩下一句話：欲知后事如何，請(qǐng)聽(tīng)下回分解！ 總結(jié)C#作為后來(lái)者，在語(yǔ)法層面上規(guī)避了很多STL遇到的問(wèn)題。而STL的構(gòu)思之妙，略窺一二。 參考資料- 侯捷.STL源碼剖析.武漢：華中科技大學(xué)出版社，2013
- Nicolai M. Josuttis.C++標(biāo)準(zhǔn)庫(kù).侯捷譯.武漢：華中科技大學(xué)出版社，2011
- Jeffrey Richter. CLR via C#.周靖譯.北京：清華大學(xué)出
|
