C#與C++相比較之STL篇

雪柳花明 2016-09-22

展開全文

Program into Your Language, Not in It——《代碼大全》,。如何深入一門語言去編程,？我認為有三步：熟悉它,；知道它的局限性；擴展它,。如何熟悉,？不必說，自然是看書看資料,，多用多寫,。如何知曉其局限性？這步我們只能通過對比了,，任何事物都有其自身的局限性,，沒有任何東西是完美的（除了上帝哈 Smile ）,。在這里,，我用C#與C++做對比，嘗試勾勒出C#與C++一些觀念上的不同,。如何擴展,？這點我正在嘗試 Embarrassed smile 。

C++的STL

STL包含六大組件：容器(Containers),、迭代器（Iterators）,、算法（Algorithms）、仿函數(shù)（functors）,、配接器（Adapters）,、配置器（Allocators）。容器通過配置器取得數(shù)據(jù)存儲空間,，算法通過迭代器來存取容器的內(nèi)容,，仿函數(shù)協(xié)助算法完成不同的操作策略，配接器用來修飾或套接仿函數(shù),。這一整套配合,，可以使我們完全掌控數(shù)據(jù)在存儲器上的增刪查改。（在這里我很想畫一張圖出來,，但是我找了很久,，實在找不到好的工具，有沒有哪位同學能分享一些好的畫示意圖之類的工具呢,？）

容器

STL中,，最常用的容器要算vector、list,、map,、set這四種了。C#中,，對應的容器分別是:List,、LinkedList,、Dictionary、HashSet,。單看容器,，其實它只是抽象出了一些邏輯結(jié)構(gòu)，根據(jù)不同的邏輯需要,，在存儲器上反應出不同的物理存儲結(jié)構(gòu),。這點C++和C#的抽象沒有什么不同，當然,，其實現(xiàn)上,，很不相同。這點通過代碼的書寫,，就可以略窺一斑,。

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++并沒有內(nèi)置的foreach語句（貌似新的標準中有？）,，所以它通過迭代器來幫助它來完成迭代,。而C#就非常方便了，在語法級別完成了這個功能,。從寫法上我們可以看到,，c++的迭代器看上去是一個指針，是一個可以做自增操作的指針,。c#迭代出的每個item則是當前存放的數(shù)據(jù),。

迭代器

STL中的迭代器有五種：輸入迭代器（Input Iterator）、輸出迭代器（Output Iterator）,、前向迭代器（Forward Iterator）,、雙向迭代器（Bidirectional Iterator）、隨機存取迭代器（Random Access Iterator）,。C#中,，沒有相對應的迭代器概念。畢竟迭代器就是一個智能指針,，而C#卻不支持指針（unsafe另算哈）,。

輸入迭代器，只能一次一個向前讀取元素,，并且只能讀取該元素一次,。如果我們復制一份輸入迭代器，副本輸入迭代器和原來的輸入迭代器分別向前讀取一個元素,，那么他們可能會遍歷到不同的值,。以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;
    }
}

輸出迭代器,，與輸入迭代器相反,，它的作用是將元素值一個個寫入，所以只能作為左值,。以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é)合,，但是卻沒能用有輸入、輸入迭代器的全部功能,，真心覺得這個迭代器很尷尬,。前向迭代器提取值的時候，要確保它是有效的迭代器（比如到了序列尾端）,，而輸出迭代器卻不用（輸出迭代器不提供比較操作,，無需檢查是否達到尾端）。我沒見過比較有代表性的前向迭代器,，所以給不出代碼示例（囧…）,。

雙向迭代器,，在前向迭代器的基礎(chǔ)上增加了回頭遍歷的能力,。寫法上來說，就是提供了自減操作,。最合適的列子非鏈表的迭代器莫屬了,。如下：

#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 << " ";
    }
}

隨機迭代器，在雙向迭代器的基礎(chǔ)上增加了隨機存取能力,。寫法上來說,，就是提供了加減法操作，還提供了大小比較操作(除了這個迭代器,，其他都沒有大小比較,，所以一般判斷迭代器是否結(jié)尾，是用 == 或者 != 來判斷),。最合適的列子就是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;

至此，我們對C++迭代器有些基本的了解了?，F(xiàn)在讓我們探索一下這背后到底是怎么實現(xiàn)的,。我們知道C++的STL是依靠模板(Template)來實現(xiàn)的，用C#的詞來描述就是泛型(Generic),。一個迭代器,，其實是一個類型，一個遵循了一系列潛規(guī)則的類型,。按照被潛的程度,，分成兩種：自娛自樂,，狼狽為奸。如果只是想自娛自樂的話,，那么很簡單,，只要像下面這樣既可：

#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;
};

//每個元素
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;
    }
}

上述代碼中，我們完全依賴自己的雙手,，通過重載*,、->、 ++,、==,、!=等操作符，實現(xiàn)了自己的行為上類似迭代器的迭代器,。但是我們僅能自娛自樂而已,，不能融入STL的大家庭。我們無法復用STL原有的輪子,，也無法將我們的輪子完美的放進STL（只需重載一下全局的!=操作符,，可以使用STL的find）。我們?yōu)榱藢崿F(xiàn)這個迭代器,，將容器的元素類型（ListItem）暴露了,，而且還暴露了ListItem的內(nèi)部實現(xiàn)細節(jié)（重載++操作符，用到了ptr->next()）,明顯不科學??！所以一般迭代器都是相應的容器的設(shè)計者實現(xiàn)的，內(nèi)嵌在容器中,。

如果想讓我們的迭代器能融入到STL中,，那么，我們就必須為我們的迭代器實現(xiàn)五個“接口”,一個表示迭代器的類型iterator_category,，一個表示值類型value_type,，一個表示兩個迭代器之間的距離類型difference_type，一個表示迭代器的指針pointer,，一個表示迭代器的解引用reference,。這五個“接口”,就是STL關(guān)于迭代器的潛規(guī)則。比如一個定義良好的iterator_category可以幫助我們的迭代器在使用distance(),advance()之類的函數(shù)時,，有更高的效率,。為了幫助我們定義自己的迭代器，STL有一個結(jié)構(gòu),，只要我們繼承即可,，在VS中輸入iterator然后轉(zhuǎn)到定義，即可看到下圖：

下面讓我們來定義一個可以與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);
}

看起來好像沒什么區(qū)別,？其實這里面的區(qū)別大了,。

STL迭代器的潛規(guī)則

讓我們先從C#的接口談起，相信大家對接口這個概念都不陌生,。能被foreach遍歷的類型,，必須繼承了IEnumerable這個接口。能夠做比較運算的類型,，必須繼承了IComparable接口,。接口，是個非常強的概念,。它與類的虛函數(shù)相比,，最大的不同就是：繼承該接口后，必須要實現(xiàn)接口中的方法,，而虛函數(shù)則不必,。有了這層語法上的限制，那么我們在C#中定義我們的泛型方法時,，就可以強制一些規(guī)定,，便于我們操作傳進來的泛型實參。比如我們要定義一個排序算法,。既然是排序,，首先就要求元素能夠被比較，如果不能比較,，那就只能呵呵了…下面貼代碼,。

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);
       }

通過用where這個方法，規(guī)定元素T的類型必須是可比較的,，來限制用戶程序員傳入的類型。使用接口約束,，不緊能方便我們在方法中做基于一定限制的邏輯操作,，還能在需要的時候確定方法的返回類型以及一些類型的限定信息?？赡芎竺孢@兩個優(yōu)點在C#中還不怎么明顯,，如果見識到STL為了這么簡單的操作饒了多么大的彎，我們就能深刻體會到這種好處了,。假設(shè)我們有這么個需求：需要返回一個兩個迭代器（迭代器一個在前一個在后,，能形成半開區(qū)間）間元素中的最大值。大家會怎么寫這個方法,？用C#,方法大概是這樣：

我們可以返回一個T或者IComparable<T>,。這是由于傳進來的值的類型已經(jīng)確定了是T。這是與C++最大的不同。在C++中,，如果為通用的STL迭代器寫一個算法,，大概如下:

這時候，我們應該返回什么類型,？我們甚至不知道這個迭代器指向的是什么類型,！我們知道指向的值可以用*begin來表示，但是我們要怎么讓編譯器知道,？這里可沒有C#的委托限制,，無法用委托來確定類型。大家想到怎么確定迭代器指向的類型了嗎,？沒錯,，是利用函數(shù)模板的參數(shù)推到機制。我們要在里面再嵌入一層函數(shù),，即可得到迭代器指向的元素的類型,。最后看起來代碼像這樣：

現(xiàn)在還剩一個問題了，最上層的Max應該返回什么類型,？有兩個方法可以確定：我們再為Max加一個泛型參數(shù)指明返回類型,；再在模板中加一個插件。前一種很簡單,，不過不是很優(yōu)雅,，略過不談。如何在模板中加插件,？還記得我們前面所說的潛規(guī)則么,？我們定義了五個“接口”，其中有一個是表示值類型的value_type,。答案就在這,！我們通過一個第三方的提取工具：iterator_traits，來獲得返回的值類型,。代碼如下：

將迭代器的類型傳入iterator_traits中,，提取出定義該迭代器的時候定義的元素類型。這下所有的問題都解決了,。是不是很優(yōu)雅,？當然，不要跟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++少了接口這個語法級的概念，實現(xiàn)一個這么簡單的方法,，都要繞這么大一個彎,！而且在調(diào)試代碼的時候，模板出錯的報錯提示，是出了名的多,！一個小問題可以引起大段的錯誤提示,。其實上面的代碼很容易出錯，如果迭代器指向的類型無法做邏輯比較怎么辦,？比如將一個map的迭代器傳進來,，大家可以試一試！而C#從語法層面上將這些弊端都規(guī)避掉了,。如果不符合接口限制,，將會有優(yōu)雅的提示信息。返回類型可以直接返回接口類型,。我真心感覺吊炸天,！如果不與C++比較，我是無法知道C#為我做了這么多工作,！想到STL是上世紀的杰作,，我很佩服當時為了解決這些問題而探索出的traits方法。而C#作為后來者,，明顯吸收了很多C++的精華,。

通過容器和迭代器這兩個組件，我們可以看到STL的構(gòu)思之巧妙,，通過一系列的潛規(guī)則,，來實現(xiàn)了通用的目的。我們也看到了C#的方便之處,。到目前的比較為止,，C#的表現(xiàn)非常不錯。但是,，C#會一直這么拽嗎,？有句話說的好:“你不拽我們還可以做朋友…”。以我現(xiàn)在還和C#是朋友的現(xiàn)狀來看……

我本來想以一篇來概括STL的,，寫了快10小時,，發(fā)現(xiàn)還僅是寫到第二個組件！現(xiàn)在只剩下一句話：欲知后事如何,，請聽下回分解！