[dotNET]曾毅翻译的《体验STL.NET》

happmaoo

浏览: 4325531 次
性别:
来自: 杭州

最近访客更多访客>>

flyjava

icesort

adamkisy

wangyy

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2013-06 ( 10)
2012-01 ( 29)
2011-12 ( 23)
更多存档...

.net 算法 C++C#C

体验STL.NET

[翻译] zengyi820 2004-10-07

为了更好的使STL适合.NET开发，Visual C++产品组,在2005版的Visual C++中重新设计了STL，并命名为STL.NET，从Beta1版本的产品中开始提供。

在STL.NET的设计中，STL的实现使用了CLI泛型和C++模版机制。2005版本的C++将加入C++/CLI动态编程的支持，应当会成为最能够满足程序员设计的语言。

给予程序员丰富的选择

总共有三个容器库可供程序员用于操作CLI类型，这三个容器库建于三种类型参数化模型之上。

原先元素类型存储的Systems::Collection 库是基于CLI类型中的对象基类来实现的。如下的 ArrayList实现了IList接口。它代表类型对象的数组，在本例中用于控制String类型的元素。（这里采用版本2的语法来实现）

void objectCollection()

{

using namespace System::Collections;

ArrayList ^as = gcnew ArrayList;

as->Add( "Pooh" );as->Add( "Piglet" );

as->Add( "Eeyore" );as->Add( "Rabbit" );

as->Sort();

Console::WriteLine( "ArrayList holds {0} elements: ",

as->Count );

for ( int i = 0; i Count; i++ )

Console::WriteLine( as[ i ] );

int index = as->IndexOf( "Pooh" );

if ( index != -1 )

{

//需要一个清晰地downcast

String^ item = safe_cast<string>( as[ index ]); as->RemoveAt( index ); } as->Remove( "Rabbit" ); Console::WriteLine( "\nArrayList holds {0} elements: ", as->Count ); IEnumerator^ is = as->GetEnumerator(); while ( is->MoveNext() ) Console::WriteLine( is->Current ); } 现在我们引入了一个基于CLI泛型机制的新的容器库。可以在System::Collections::Generic 命名空间中找到。这是在Visual Studio 2005 Beta1中的实现，在最终的发布版当中可能会有所改变。Collection<t> 是一个具体的泛型基类，用户们可以从其中派生自己特化的容器类。下面的样例与上面的例子作用相同，只是使用了新的容器库， void genericCollection() { using namespace System::Collections::Generic; Collection<string> ^cols = gcnew Collection<string>; cols->Add( "Pooh" ); cols->Add( "Piglet" ); cols->Add( "Eeyore" ); cols->Add( "Rabbit" ); //没有与Collection关联的Sort方法 Console::WriteLine( "Collection holds {0} elements: ", cols->Count ); for ( int i = 0; i Count; i++ ) Console::WriteLine( cols[ i ] ); int index = cols->IndexOf( "Pooh" ); if ( index != -1 ) { //不需要downcast…… String ^item = cols[ index ]; cols->RemoveAt( index ); } cols->Remove( "Rabbit" ); Console::WriteLine( "\nCollection holds {0} elements:", cols->Count ); IEnumerator<string> ^is = cols->GetEnumerator(); while ( is->MoveNext() ) Console::WriteLine( is->Current ); } STL.NET提供了一个与以往设计风格迥异的类型参数化模型，我们将在下个话题中谈到。下面是String容器的实现。 #include <cli vector> #include <algorithm> void stlCollection() { vector<string> ^svec = gcnew vector<string>; svec->push_back("Pooh"); svec->push_back("Piglet"); svec->push_back("Eeyore"); svec->push_back("Rabbit"); //泛型算法：sort sort( svec->begin(), svec->end() ); Console::WriteLine( "Collection holds {0} elements: ", svec->size() ); for ( int i = 0; i size(); i++ ) Console::WriteLine( svec[ i ] ); //泛型算法：find vector<string>::iterator iter = find( svec->begin(), svec->end(), "Pooh" ); if ( iter != svec->end() ) { //不需要downcast…… String ^item = *iter; svec->erase( iter ); } //泛型算法： remove…… remove( svec->begin(), svec->end(), "Rabbit" ); Console::WriteLine( "\nCollection holds {0} elements:", svec->size() ); IEnumerator<string> ^is = svec->GetEnumerator(); while ( is->MoveNext() ) Console::WriteLine( is->Current ); } 为什么要选用STL.NET？ 在我们深入STL.NET之前，让我们首先来简要地回答一个不可避免的问题：Visual C++程序员为什么要选用STL.NET容器类而不是语言中立的系统：Collections或者System::Collections::Generic 库? 立即放弃System::Collections库和Visual Studio 2005决定提供泛型裤的原因是一样的：由于类型信息的丢失，经常会造成参数化对象模型非常的复杂并且不安全。在简单的使用中，例如在容器中装有16个或者更少的元素，进行冒泡排序的时候还可以使用。但当你的应用程序涉及到真实世界的问题的时候，你就必须要提供一个更为完善的解决方案了。 所以，STL.NET和System::Collections::Generic库便成为如Visual C++这样的系统级程序设计语言的备选方案。为什么Visual C++程序员应当偏爱于STL.NET呢？这不就使我们的程序与其他的.NET语言隔离开了么？这是一个很现实的问题，并且也值得作出一个答复。 回复之一是“可扩展性（extensibility）”。最初STL的设计模式是由Alex Stepanov发明的, 他将算法和容器存放在了不同的域空间中。这样用户就可以将所有容器都适用的算法添加到算法集当中去，或者将每个算法都可以应用的容器添加到容器集当中去。泛型库是一个更为传统的模型。这就引出了我们第二个回复。 第二个回复是“统一性（unification）”。现在正在使用C++的程序员使用这个库和现有的代码的水平已经达到了专家水准。我们不仅仅希望能够提供一个对现有代码迁移的途径，同时也希望使程序员们积累下来的专家经验仍然适用。如果在你原来进行C++编程的时候依赖于STL，并且很难想象一个C++程序员不依赖于STL，那么它在.NET中的消失会使你感到是一个很大的失误—至少这是我曾经的体会。与我曾经交流过的很多C++专家都曾经提到过这个问题，并且因此表示对迁移到.NET持保留态度。 第三个回复是“性能”。但是C++程序员对于讨论性能这个话题早已显得不愿意再提这些陈词滥调，我这里只是一笔带过—在后续的文章中将深入讨论。 最后问题是。这些做的都非常棒并且非常好Stan, 但是这不是将C++程序员和C++/CLI程序与.NET社群的其它部分隔阂开了么？对于这个问题的回答，我认为是一个非常简单的“不”。STL.NET的体系架构师，包括Anson Tsao, Martyn Lovell, 和P.J. Plauger, 已经非常慎重地考虑了这个问题，通过对IEnumerator, IList, 和ICollection的支持，我们对于STL.NET能够和其它.NET 语言共同操作的能力非常有信心。我们将在后续的系列文章中深入的讨论。 定义一个公共基础 深入了解并使用STL.NET的方法有两种：一种途径是可以通过了解STL和STL.NET的区别来掌握。另外一种途径是通过了解他们有哪些共性。虽然那些有STL丰富使用经验的人来说似乎需要一张“区别清单”，然而这并不能使你从那些不熟悉的库的乌烟瘴气中逃离出来，所以说，当我们放慢脚步，深入这些或那些容器以及他们是如何与系统集合库（System collection libraries）互操作等这样的深奥角落的时候—虽然这些都是非常整洁优雅的，但我们直接的去了解这些新的内容不是更好么？至少在下面的简短介绍部分我希望大家是这样做的。通过这种方法，对于那些新手来说就可以对STL和STL.NET提供的参数化集合的扩展模型有一个了解。 那么STL和STL.NET都有哪些共性呢？这两者都包括两个主要的组件：顺序式（Sequential）和关联式（associative）容器类型，以及一个泛型算法集。(是的，如果你是一个经验丰富的STL开发者，你就应当知道我下面要讨论什么。同样，两者具有同样的术语和背景，所以你得耐心点。) 泛型算法不直接操作容器类型。取而代之的是，我们使用了一个迭代器来成对的标识用于操作的元素范围。元素范围符号（正式的术语为左包含区间）如下所示： // 读作：包含first直至但是不包括last [ first, last ) 这表明了范围是从first开始以last结束但是不包含last。当first等于last的时候这个范围就是空了。 顺序式容器中存储了单独类型元素的序列集。vector和list类型是两个主要的顺序式容器。(第三个顺序式容器是deque—发音deck—提供了vector同样的功能，但是用于对高效插入和删除第一个元素这种特殊情况。一般我们首选deque而不是vector，例如一个队列的实现。) 我们在访问一个连续容器类型之前，我们必须包含进合适的头文件，如下所示： #include <cli vector> #include <cli list> #include <cli deque> 这些头文件同时也包含了共享基类接口的声明，例如interface_vector，以及泛型在容器中的应用，例如generic_vector。 STL.NET的容器是引用类型的；容器的声明中会有一个追踪句柄—它会自动的初始化为nullptr。我们通过gcnew操作符分配一个实际的容器。我们在前面的小节中曾经简单地提到过，现在我来详细地解释一下： void f() { //分配一个空向量（vector）…… vector<string>^ svec = gcnew vector<string>; //分配一个含有10个元素的表（list） //每一个值默认都被设为nullptr list^ olist = gcnew list( 10 ); //追踪句柄值自动地设为nullptr deque<int>^ ideck; //做一些有趣的事情…… }; 我们将在这个系列文章的后续文章中讨论有关顺序式容器的声明和使用的话题。 关联式容器（associative container）支持对现有元素的显示和检索的高效查询。关联式容器类型中最主要的两个就是map和set。Map是一个key（键）/value（值）对：key用于查询，value用于存储和检索数据。举个例子来说，电话号码簿可以用map简单地表示出来：key是每一个人的名字，value是相关联的电话号码。 map使用带下划线的树抽象来按照值升序排列条目。hash_map容器能够进行更为高效的检索排序。尽管如此，hash_map迭代也是某种程度上随机地访问元素。如果检索是map中的主要活动，就应首选hash_map容器。 set包含一个单键值（key value）并且支持元素是否存在的高效查询。例如，文本查询系统在建立文本词库的时候可能需要建立一个常用词语集并将之排除在文本外，例如the, and, but, 等等。程序将轮流的读取文本中的每一个词，检查它是否是拒绝接纳词汇集中的词汇，根据查询的结果，或者是忽略这个词，或者是将之存入数据库。除了set以外，还有hash_set 容器，它与map和hash_map有相同的特性。 map和set只能包含一个键（key）。multimap和multiset 支持出现多个同样的键。还以我们的电话号码簿为例，我们可能需要将一个人列在多张表中。在这种情况下，我们就要使用multimap。同样也存在hash_multimap和hash_multiset。 与这些容器类型相关联的头文件如下所示： //用于map和multimap #include <cli map> //用于set和multiset #include <cli set> //用于hash_map和hash_multimap #include <cli hash_map> //用于hash_set和hash_multiset #include <cli hash_set> 一个简单的演示 让我们通过一个实例来具体地讨论一下。下面的例子实现了文本词汇统计。它展示了map, hash_set, 和vector的使用。函数声明如下： map<string>^ build_word_count( vector<array>^>^ words, array<string> ^common_words ) 模板语法让人看起来非常地复杂。让我们看看能够做哪些有益的改进。build_word_count() 的返回类型是map，键(key)是字符串—文本中每一个不同于其他词的单词—值(value)是用于统计相关联词出现次数的整数。函数的第一个参数是CLI数组向量(vector),它将文件中的词汇保存为字符串元素。第2个参数中保存着我们要排除在外的字符集。 由于很多“帽子”和右中括号间隔出现，这看起来相当的复杂。我们可以使用typedef从文字上化简一下： typedef array<string>^ words; typedef vector<words>^ text; 使用typedef重定义的函数如下所示： map<string>^ build_word_count( text theText, words common ) 我们也可以除去显式的map声明，但是出于读者练习的考虑我仍然保留了声明。下一个工作是实现。我们可以将之分为两部分：(1) map和hash_set的初始化，如下所示，(2)实际的文本处理程序。 // 第1项：初始化容器 // 分配一个空map……我们并不清楚它的大小…… map<string> ^wordOccur = gcnew map<string>; //用数组中的元素填充hash_set hash_set<string> ^comWords = gcnew hash_set<string>( &common[0], &common[common->Length]); 如果你不熟悉STL, hash_set 的初始化可能会使你感到陌生。但是除了语法之外，它的声明是非常直接和有力的。 我们要做的是使用数组中的元素来初始化hash_set。我们显然可以做到，当然要用一个for each语句进行迭代实现。例如， //简化hash_set声明 //第1部分:分配一个空的hash_set hash_set<string> ^comWords = gcnew hash_set<string>; //第2部分: 用数组中的元素填充hash_set for each ( String^ wd in common ) comWords->insert( wd ); 数组元素中的第一个直至有效的最后一个元素的地址装入hash_set的构造函数为元素装入hash_set提供了同等的机会。这两个地址为hash_set 构造函数的迭代提供了一个元素范围，轮流的将它们插入容器中。这就是我在这部分开始提到的迭代器的范围。 实现的第2部分便是文本处理。因为我们还没有看到官方正式发布的迭代器，我们现在仍然使用for循环来遍历vector。我们将使用for each语句来遍历vector的每一个数组元素。这就是如上所述的代码： //循环的访问每一个数组 for ( int ix = 0; ix size(); ++ix ) { for each ( String^ wd in theText[ ix ] ) if ( common->find( wd ) == common->end() ) word_map[ wd ]++; } // 不要忘记返回结果…… return word_map; find() 是hash_set的成员函数，它用于确定词汇项是否已经存在于set当中—所有的关联式容器都支持find()成员函数。(是的，顺序式容器，以及内置数组，和所有你可能将集成到STL/STL.NET模型中的集合，都使find()泛型算法。算法和容器的隔离理论上比实际上要为严重。我们将特别地讨论一下列表顺序式容器(list sequential container) 。)他返回的是我还没有讨论过的—容器中的迭代器。此时，我们将迭代器假想为指针类型。如果在容器中词汇项已经存在了，那么find()将返回给它一个迭代器；否则，将返回最后一个词汇项的迭代器。这与end()返回的迭代器值是相同的。我们判断STL下的元素搜索是否成功的方法就是比较用搜索方法返回的迭代器值与end()方法返回的迭代器值是否相同。如果两者相同，那么元素便不在容器中。 每一个容器都提供begin()和end()成员函数。begin()返回给容器中first元素一个迭代器。正如我前面说到的，end()返回给容器中last元素一个迭代器。举例如下，下面的程序中展示了我们如何声明两个迭代器并且用这两个成员函数初始化它们， vector<words>::iterator first = theText->begin(); vector<words>::iterator last = theText->end(); 容器的遍历一般使first在一个for循环或者是while循环中递增，当first等于last的时候终止循环。例如, for ( ; first != last; ++first ) 对迭代器对的要求是他们必须能够通过增量运算符的重复应用以first开头并能够达到last。尽管如此，编译器自身不能做到；如果不能够达到这个要求则会产生未定义的运行时行为（undefined run-time behavior）。 我们通过反引用(*)操作符访问迭代器涉及到的元素。例如，为了重新获得我们的向量(vector)的每一个CLI数组元素，我们在上述的for循环体中写入下面的代码， array<string> ^as = *first; 我们将在这一系列文章的后续文章中介绍关联式容器的声明和用法。 算法的选择 泛型算法为这些容器类型和两个内置数组类型的元素提供了操作。这些操作包括Search (find, count), Sort (merge, partition, permutate, reverse, rotate, shuffle, sort), Deletion/Subtitution (remove, replace, swap, unique), Copy, Relational (equal, min, max, includes), Generate (fill, for-each, generate, transform), Set (union, intersection, difference), Heap (make, sort, pop, push), 以及很多深奥的数字操作，例如积分，部分求和，内积（inner product）,和临差(adjacent difference)。 在我们使用泛型算法前，当然，我们必须包含进相应的头文件。除了数字算法之外的其它所有算法，我们都这样写： #include <algorithm> 四个数字算法，积分，部分求和，内积,和临差被分出一个单独的头文件。在使用这些算法的时候我们这样写头文件： #include <numeric> (我一直在寻求为什么这四个操作的头文件被单独的提出来的原因—这显然将算法的使用的讨论复杂化—但是无论是在文档中还是经过深入的研究，我仍然找不到答案。在原先Stepanov的实现中，这四个操作与其它的算法使用的是同一个头文件。在标准化过程中， numeric头文件被引入了并且在数字库标准选举部分确实做了一个讨论。) 你可能会想，天哪，Stan,这些不应当写作<cli algorithm>吗？毕竟，这是容器头文件的验证方法。如果那样写的话不是有点弄巧成拙么？令人吃惊的是，答案是“不”。我说令人吃惊的是因为STL和STL.NET中采用了相同的实现方法。天哪，我们讨论到了代码重用去了！ 好的。让我们看看如何使用这些算法。举例来说，让我们在将字符串元素数组插入map之前对它们进行排序。我们将使用sort()泛型算法来实现它。对于所有的泛型算法，参数几乎都是迭代器对构成的范围： sort( &as[0], &as[ as->Length ] ); 在开始的代码中还要使用到另外两个泛型算法—find()和remove()： //泛型算法：find vector<string>::iterator iter = find( svec->begin(), svec->end(), "Pooh" ); if ( iter != svec->end() ){ ... } //泛型算法：remove…… remove( svec->begin(), svec->end(), "Rabbit" ); 到现在为止我们应当对这里的用法模式非常敏感了：由迭代器对划分出的范围与容器的算法密不可分。搜索算法返回一个迭代器，或者用于发现容器中的项，抑或是找不到，迭代器用于标识范围内的最后一个项。 我们将用泛型算法做一些有趣的事情—但这必须在后续的文章中完成。我希望这些内容给我们了一个我们将要讨论什么的不错的概览，并且为我们能够作为一个学习小组向前走提供了一个公共的词汇表和背景知识。下次再会。 感谢 即使是最简单的文章问世，也有很多双台后的手提供帮助。我要郑重地感谢Scott Currie在最终文档上给予我的深刻的评论，其中有些内容我已经认为没有什么可以改动的余地了！Anson Tsao在STL.NET方面给予了我很多指导，我为此表示衷心的感谢。Martyn Lovell掌控着STL.NET的进度部署，感谢他允许我一路跟踪STL.NET的开发。最后感谢Brian Johnson 和Ronald Laeremans使我坚定信心开始撰写这一系列文章。</string></cli></numeric></algorithm></string></words></words></string></string></string></string></string></string></string></words></string></string></array></string></cli></cli></cli></cli></int></string></string></cli></cli></cli></string></string></string></string></algorithm></cli></string></string></string></t></string>

分享到：