C#与C++相比较之STL篇

引言

Program into Your Language, Not in It——《代码大全》。如何深入一门语言去编程?我认为有三步:熟悉它;知道它的局限性;扩展它。如何熟悉?不必说,自然是看书看资料,多用多写。如何知晓其局限性?这步我们只能通过对比了,任何事物都有其自身的局限性,没有任何东西是完美的(除了上帝哈C#与C++相比较之STL篇)。在这里,我用C#与C++做对比,尝试勾勒出C#与C++一些观念上的不同。如何扩展?这点我正在尝试C#与C++相比较之STL篇

C++的STL

STL包含六大组件:容器(Containers)、迭代器(Iterators)、算法(Algorithms)、仿函数(functors)、配接器(Adapters)、配置器(Allocators)。容器通过配置器取得数据存储空间,算法通过迭代器来存取容器的内容,仿函数协助算法完成不同的操作策略,配接器用来修饰或套接仿函数。这一整套配合,可以使我们完全掌控数据在存储器上的增删查改。(在这里我很想画一张图出来,但是我找了很久,实在找不到好的工具,有没有哪位同学能分享一些好的画示意图之类的工具呢?)

容器

STL中,最常用的容器要算vector、list、map、set这四种了。C#中,对应的容器分别是:List、LinkedList、Dictionary、HashSet。单看容器,其实它只是抽象出了一些逻辑结构,根据不同的逻辑需要,在存储器上反应出不同的物理存储结构。这点C++和C#的抽象没有什么不同,当然,其实现上,很不相同。这点通过代码的书写,就可以略窥一斑。

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++并没有内置的foreach语句(貌似新的标准中有?),所以它通过迭代器来帮助它来完成迭代。而C#就非常方便了,在语法级别完成了这个功能。从写法上我们可以看到,c++的迭代器看上去是一个指针,是一个可以做自增操作的指针。c#迭代出的每个item则是当前存放的数据。

迭代器

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结束输入,或者按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;
}
}

前向迭代器,是输入、输入迭代器的结合,但是却没能用有输入、输入迭代器的全部功能,真心觉得这个迭代器很尴尬。前向迭代器提取值的时候,要确保它是有效的迭代器(比如到了序列尾端),而输出迭代器却不用(输出迭代器不提供比较操作,无需检查是否达到尾端)。我没见过比较有代表性的前向迭代器,所以给不出代码示例(囧…)。

双向迭代器,在前向迭代器的基础上增加了回头遍历的能力。写法上来说,就是提供了自减操作。最合适的列子非链表的迭代器莫属了。如下:

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

随机迭代器,在双向迭代器的基础上增加了随机存取能力。写法上来说,就是提供了加减法操作,还提供了大小比较操作(除了这个迭代器,其他都没有大小比较,所以一般判断迭代器是否结尾,是用 == 或者 != 来判断)。最合适的列子就是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++迭代器有些基本的了解了。现在让我们探索一下这背后到底是怎么实现的。我们知道C++的STL是依靠模板(Template)来实现的,用C#的词来描述就是泛型(Generic)。一个迭代器,其实是一个类型,一个遵循了一系列潜规则的类型。按照被潜的程度,分成两种:自娱自乐,狼狈为奸。如果只是想自娱自乐的话,那么很简单,只要像下面这样既可:

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

上述代码中,我们完全依赖自己的双手,通过重载*、->、 ++、==、!=等操作符,实现了自己的行为上类似迭代器的迭代器。但是我们仅能自娱自乐而已,不能融入STL的大家庭。我们无法复用STL原有的*,也无法将我们的*完美的放进STL(只需重载一下全局的!=操作符,可以使用STL的find)。我们为了实现这个迭代器,将容器的元素类型(ListItem)暴露了,而且还暴露了ListItem的内部实现细节(重载++操作符,用到了ptr->next()),明显不科学啊!所以一般迭代器都是相应的容器的设计者实现的,内嵌在容器中。

如果想让我们的迭代器能融入到STL中,那么,我们就必须为我们的迭代器实现五个“接口”,一个表示迭代器的类型iterator_category,一个表示值类型value_type,一个表示两个迭代器之间的距离类型difference_type,一个表示迭代器的指针pointer,一个表示迭代器的解引用reference。这五个“接口”,就是STL关于迭代器的潜规则。比如一个定义良好的iterator_category可以帮助我们的迭代器在使用distance(),advance()之类的函数时,有更高的效率。为了帮助我们定义自己的迭代器,STL有一个结构,只要我们继承即可,在VS中输入iterator然后转到定义,即可看到下图:

C#与C++相比较之STL篇

 

下面让我们来定义一个可以与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);
}

看起来好像没什么区别?其实这里面的区别大了。

STL迭代器的潜规则

让我们先从C#的接口谈起,相信大家对接口这个概念都不陌生。能被foreach遍历的类型,必须继承了IEnumerable这个接口。能够做比较运算的类型,必须继承了IComparable接口。接口,是个非常强的概念。它与类的虚函数相比,最大的不同就是:继承该接口后,必须要实现接口中的方法,而虚函数则不必。有了这层语法上的限制,那么我们在C#中定义我们的泛型方法时,就可以强制一些规定,便于我们操作传进来的泛型实参。比如我们要定义一个排序算法。既然是排序,首先就要求元素能够被比较,如果不能比较,那就只能呵呵了…下面贴代码。

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这个方法,规定元素T的类型必须是可比较的,来限制用户程序员传入的类型。使用接口约束,不紧能方便我们在方法中做基于一定限制的逻辑操作,还能在需要的时候确定方法的返回类型以及一些类型的限定信息。可能后面这两个优点在C#中还不怎么明显,如果见识到STL为了这么简单的操作饶了多么大的弯,我们就能深刻体会到这种好处了。假设我们有这么个需求:需要返回一个两个迭代器(迭代器一个在前一个在后,能形成半开区间)间元素中的最大值。大家会怎么写这个方法?用C#,方法大概是这样:C#与C++相比较之STL篇

我们可以返回一个T或者IComparable<T>。这是由于传进来的值的类型已经确定了是T。这是与C++最大的不同。在C++中,如果为通用的STL迭代器写一个算法,大概如下:

C#与C++相比较之STL篇

这时候,我们应该返回什么类型?我们甚至不知道这个迭代器指向的是什么类型!我们知道指向的值可以用*begin来表示,但是我们要怎么让编译器知道?这里可没有C#的委托限制,无法用委托来确定类型。大家想到怎么确定迭代器指向的类型了吗?没错,是利用函数模板的参数推到机制。我们要在里面再嵌入一层函数,即可得到迭代器指向的元素的类型。最后看起来代码像这样:

C#与C++相比较之STL篇

现在还剩一个问题了,最上层的Max应该返回什么类型?有两个方法可以确定:我们再为Max加一个泛型参数指明返回类型;再在模板中加一个插件。前一种很简单,不过不是很优雅,略过不谈。如何在模板中加插件?还记得我们前面所说的潜规则么?我们定义了五个“接口”,其中有一个是表示值类型的value_type。答案就在这!我们通过一个第三方的提取工具:iterator_traits,来获得返回的值类型。代码如下:

C#与C++相比较之STL篇

将迭代器的类型传入iterator_traits中,提取出定义该迭代器的时候定义的元素类型。这下所有的问题都解决了。是不是很优雅?当然,不要跟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++少了接口这个语法级的概念,实现一个这么简单的方法,都要绕这么大一个弯!而且在调试代码的时候,模板出错的报错提示,是出了名的多!一个小问题可以引起大段的错误提示。其实上面的代码很容易出错,如果迭代器指向的类型无法做逻辑比较怎么办?比如将一个map的迭代器传进来,大家可以试一试!而C#从语法层面上将这些弊端都规避掉了。如果不符合接口限制,将会有优雅的提示信息。返回类型可以直接返回接口类型。我真心感觉吊炸天!如果不与C++比较,我是无法知道C#为我做了这么多工作!想到STL是上世纪的杰作,我很佩服当时为了解决这些问题而探索出的traits方法。而C#作为后来者,明显吸收了很多C++的精华。

通过容器和迭代器这两个组件,我们可以看到STL的构思之巧妙,通过一系列的潜规则,来实现了通用的目的。我们也看到了C#的方便之处。到目前的比较为止,C#的表现非常不错。但是,C#会一直这么拽吗?有句话说的好:“你不拽我们还可以做朋友…”。以我现在还和C#是朋友的现状来看……

我本来想以一篇来概括STL的,写了快10小时,发现还仅是写到第二个组件!现在只剩下一句话:欲知后事如何,请听下回分解!

总结

C#作为后来者,在语法层面上规避了很多STL遇到的问题。而STL的构思之妙,略窥一二。

参考资料

  1. 侯捷.STL源码剖析.武汉:华中科技大学出版社,2013
  2. Nicolai M. Josuttis.C++标准库.侯捷译.武汉:华中科技大学出版社,2011
  3. Jeffrey Richter. CLR via C#.周靖译.北京:清华大学出版社,2011
上一篇:PHP之readdir()函数


下一篇:CentOS下samba配置心得(smb和nmb都要启动)