C++ STL安全变体解决方案研究：迭代器适配器和安全容器的运行时测量

理论计算机科学电子笔记264（5）（2011）71-83www.elsevier.com/locate/entcs测量C++标准模板库安全变体NorbertPataki1Zala'nSzugyi2GermanD'evai3埃奥特维奥斯·洛兰德大学编程语言与语言学系匈牙利布达佩斯摘要C++标准模板库是一个广泛使用的基于泛型编程范式的库。 使用这个库并不能保证程序没有错误。 此外，许多新的错误 这可能是由于泛型编程范式的不准确使用，如解引用无效的迭代器或误解了类似删除的算法。大多数STL算法都有先决条件，这些先决条件既不在编译时也不在运行时检查。违反这一先决条件将导致不正当行为。在本文中，我们提出了这些问题的一个子集的解决方案。我们描述的技术帮助程序员以一种更安全的方式在排序区间上使用泛型算法。 我们提出了一种新的迭代器适配器类型和标签，以及跟踪迭代器有效性的安全容器。我们测量运行时开销这些扩展。保留字：C++ STL，迭代器适配器，容器1介绍C++标准模板库（STL）是采用泛型编程方法开发的.通过这种方式，容器被定义为类模板，许多算法可以实现为函数模板。此外，算法以独立于容器的方式实现，因此可以将它们用于不同的容器[21]。C++ STL被广泛使用，因为它是一个非常方便的标准C++库，其中包含有用的容器（如列表，向量，地图等），很多 算法（如排序、查找、计数等）以及其他实用程序。STL被设计为可扩展的。我们可以添加可以与现有算法一起工作的新容器。另一方面，我们可以用一个可以与现有容器一起工作的新算法来扩展算法1电子邮件：patakino@elte.hu2电子邮件地址：lupin@ludens.elte.hu3电子邮件：deva@elte.hu1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.06.00572N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）迭代器弥合了容器和算法之间的差距[5]。用这种方法解决了表达式问题[24]。STL还包括适配器类型，用于转换库的标准元素以实现不同的功能[1]。然而，C++ STL的使用并不意味着无bug或无错误的代码[9]。因此，库的不正确应用可能会引入新类型的问题[20]。其中一个问题是，错误诊断通常是复杂的，并且很难找出程序错误的原因[25，26]。在比较函子中违反严格弱序的要求也意味着奇怪的bug [11]。这会导致运行时容器不一致。一种不同的坚持是，如果我们有一个迭代器对象指向容器中的一个元素，但该元素被擦除或者容器另一个常见的错误是根据删除算法。这些算法是独立于容器的，因此它们不知道如何从容器中擦除元素，只是将它们放在容器的末尾，我们需要调用一个特定的擦除成员函数来物理地删除元素例如，remove算法实际上不能从容器中删除任何元素[15]。大多数属性都是在编译时检查的。例如，如果对标准列表容器使用排序算法，则代码无法编译，因为列表其他属性在运行时检查。例如，标准的vector容器运行一个at方法，该方法测试索引是否有效，否则会引发异常[17]。不幸的是，仍然有大量的一些属性既不在编译时也不在运行时进行测试。遵守这些属性是程序员的责任。让我们考虑以下代码片段：std：：vectorint> v; int x;//... std：：vectorint>：：iterator i=std：：lower_bound（v.begin（），v.end（），x）;下界的目的是在有序范围内找到一个元素。是二进制搜索的一个版本，因此它具有对数复杂度。我们假设我们可以在对数时间内找到一个向量中的元素，因为向量的排序。然而，如果向量不是有序的，它会导致未定义的结果[18]。这些算法的实现不测试范围是否被适当地排序。许多STL算法期望有序范围：相等范围，二分查找，集差等。此外，以下算法通常用于有序范围，尽管它们不需要它们：唯一和唯一副本。此外，集装箱的分类是不够的。我们必须确保同一个排序函数对象用于排序和搜索。下面的代码片段也会导致不确定的行为：N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）73std：：vectorint> v; int x;//...std：：sort（v.begin（），v.end（））; std：：vector int>：：iteratori=std：：lower_bound（v.begin（），v.end（），x，std：：greater int>（））;其他典型的STL相关错误与迭代器失效有关。当正在使用迭代器处理的容器具有它的形状在这个过程中发生了变化，例如，任何导致向量重新分配（增加capacity（）的结果）的事情当一个人使用一个无效的迭代器也会导致一个unfined结果[10]。让我们考虑以下代码：std：：vector int> v;//...std：：vector int>：：iteratori= v.begin（）;//我想...//vector的容量已更改. std：：<bool is_sorted（Iteratorfirst， Iteratorlast，Comp c）{for（Citi=first; i！= last-1;++i） if（！c（*i，*（i+1）return false;return true;}模板类Container，class Compare = std：：less typeObject Container：：value_type> > class range_check_const_iterator：public Container：：const_iterator{Container：：const_iterator CIt;void check（CItfirst， CItlast， Comparec）{如果（！is_sorted（first，last，c））throw not_sorted（）;}公共场所：range_check_const_iterator（CIt curr，CItfirst， CIt last）：Container：：const_iterator（curr）{check（first，last）;}};这是一个适配器类型，它将原始的const迭代器类型转换为范围检查迭代器类型。它的构造函数检查排序，如果失败则抛出异常。以这种方式使用迭代器增强了STL的功能，因为现在可以以更安全的方式应用算法。3便利设施可以很容易地使用前面的迭代器适配器让我们考虑以下代码：std：：vectorint> v; int x;//... std：：vectorint>：：iterator i=N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）75std：：move_arrow（76N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）range_check_const_iterator std：：vector int> >（v.begin（），v.begin（），v.end（）），range_check_const_iterator std：：vector int> >（v.end（），v.end（），v.end（）），x）;下界的第一个参数检查区间算法的第二个参数检查一个空的间隔，因为我们不想在同一个间隔内执行两次排序检查 下限在范围v.begin（），v.end（）中搜索值x。由于范围检查，这个调用需要线性时间而不是原始的对数时间。由于这种解决方案使得算法的单个调用非常困难，我们提供了能够创建安全迭代器的函数模板代码如下：template classContainer>range_check_const_iterator Container>iterator_check_begin（const容器c）{return range_check_const_iterator Container>（c.begin（），c.begin（），return（）;}template classContainer>range_check_const_iterator Container>iterator_nocheck_begin（const容器c）{return range_check_const_iterator Container>（c.begin（），c.begin（），c. start（）;}类似的函数模板对于结束迭代器和任意函数都物体也是。这些技术在STL中非常典型：标准行为和任意行为的不同函数模板。开发函数模板进行参数推导在STL中非常常见。然而，在这种情况下有一个问题：当我们有一个迭代器作为下界的参数时，我们不能使用这些模板函数。在STL中，算法可以在迭代器标签上重载，例如距离和前进可以利用不同的迭代器，它在随机访问迭代器中以常数时间运行，但当参数是双向迭代器时，它需要线性时间。首先，我们引入一个新的迭代器标签，来处理上述技术并保存基本迭代器的类别：struct checked_iterator_tag {};N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）77模板类Container，class Compare = std：：less typeObject Container：：value_type> > class range_check_const_iterator：public Container：：const_iterator{公共场所：iterator_category checked_iterator_tag;typedef typerstd：：iterator_traits<容器：：const_iterator>：：iterator_categorybase_category;//我想...};第二，我们尝试将下界应用到新的迭代器类别中。STL参考文献（例如[2]）描述了下界的复杂性取决于参数迭代器因此，在迭代器标记上，下界是重载的。因此，我们可以通过以下方式为checkediterator标签创建下限：模板类Iterator，class T，classComp> Iteratorlower_bound（Iteratorfirst， Iteratorlast，constT a，Compc，checked_iterator_tag）{如果（！is_sorted（first，last，c））thrownot_sorted（）;其他return lower_bound（first，last，a，c，Iterator：：base_category（）;}安全迭代器的构造函数不再检查排序，因为重载算法能够检查它并调用原始算法。其他一些函数模板应该根据STL实现（如距离和前进）以类似的方式重载到这个类别。4克服无效迭代器在本节中，我们将介绍一种技术，可以用来避免无效迭代器使用的未定义行为。该技术适用于所有标准和非标准容器。不同的容器以不同的方式使迭代器无效，然而，这种技术也可以转换为列表，双端队列或其他第三方定义的容器。在更复杂的解决方案中，失效行为应该被参数化。我们提出的技术作为STL的矢量模板的扩展在我们的实现中，向量对象保持跟踪它们的迭代器，迭代器有一个成员来描述迭代器是否有效。当向量重新分配时，78N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）向它的迭代器发送一个消息，告诉它们它们变得无效。如果通过无效的迭代器访问元素，则会引发异常让我们考虑以下代码片段：template class T，class Alloc =std：：alloc， booldebug=false> class vector{T*p;int caps，s; std：：listiterator*> iterators;公共场所：结构迭代器：std：：iterator std：：random_access_iterator_tag，T>{私人：bool isvalid;T*curr;公共场所：iterator（T* c）：curr（c），isvalid（true）{}T运算符 *（）{如果（！return *curr;if（i）return*curr;其他throw_iterator（）;}iterator operator++（）{++curr;return *this;}Iterator operator++（int）{iterator tmp（*this）;++curr;return curr;}N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）79//我想...};私人：void realloc（）{return 2;T*t= newT[cap]; std：：copy（p，p+s，t）;delete [] p;p =t;}void invalid（）{for（type = std：：list iterator*>：：iteratorit=iterators.begin（）;it！= return（）;++it）{（*it）->isvalid= false;}}public：vector（）：cap（1），s（0）{int [int n];}vector（）{delete [] p;}void push_back（constT a）{if（s cap）p[s++]=a;其他{return（）;return（a）;}80N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）}iterator begin（）{iterator i（p）;iterators.push_back（i）; returni;}iterator end（）{iterator i（p+s）;iterators.push_back（i）; returni;}//我想...};当然，测试可以依赖于预处理器宏或其他东西传统的基于STL的代码可以很容易地转换为使用这个矢量容器，并进行额外的检查。只需要向vector类型传递一个额外的参数。然而，在未测试和测试的向量容器之间没有简单的赋值和复制，但是可以添加一个特殊的模板复制构造函数和赋值运算符。当然，我们可以为安全和不安全版本创建专门化。这使我们的实现更快，但现在我们只是证明我们的概念。类似地，我们可以创建一个能够追踪向量在这种情况下，当迭代器指向被擦除的元素时，会引发异常。如果失效包括结束迭代器，也应该考虑。如果结束迭代器被解引用，也会导致运行时问题。它可以以正交的方式处理。如果我们想使所有指向被擦除元素的迭代器无效，我们应该按照以下方式编写erasetemplate class T，class Alloc= std：：alloc，booldebug = false>class vector{//像前面的代码一样...公共场所：void erase（i）{if（debug&&！i.无效）N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）81throw_iterator（）;std：：copy（i.curr+1，p+s，i.curr）;for（type = std：：list iterator*>：：iteratorit=iterators.begin（）;it！= return（）;++it）{if（it->curr==i.curr）int-> valid= false;}}};5测量开销在本节中，我们将评估第4节中介绍的向量实现的运行时开销。我们设计了一些变体来管理包含的迭代器。也可以提到一些处理包含迭代器的方向如何处理它们是一个有趣的问题。在vector：：iterator的析构函数中，我们可以执行代码来管理它们。因此，迭代器对象应该持有一个指针，该指针指向调用begin（）或end（）方法的向量对象这个方法可以被扩展为传递一个指向this的指针，迭代器第一个变体是最简单的一个，没有对包含迭代器做任何事情，所有构造的迭代器都可以在列表中找到。这种方法的缺点是包含的迭代器的数量增加，并且在重新分配时执行了太多不必要的无效操作。这个变量可以在前面的部分中看到。该版本在表格上标记为第一变体。另一种方法是在迭代器被析构时维护列表。在vector：：iterator的析构函数中很容易从列表中删除迭代器。这种方法的优点是在列表中只能找到现有的迭代器。这在比较中用第二个变量标记。我们开发了一些通用的迭代器密集型代码来衡量我们实现的开销。这些代码包含比通常应用程序更多的迭代器因此，我们的实现的效率是更好的在普通的使用。我们用我们的两个变体和SGI STL实现测量了代码的运行时间。我们总是将我们的解决方案的速度因此，std：：vector的运行时间是100%。在我们的第一个测试用例中，我们创建了很多具有很少元素的向量，并执行了STL的排序82N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）STD：：vector百分百第一种变体百分之一百一十四第二种变体 百分之二百九十九第二个测试用例创建了大量具有中等数量元素的向量，并执行了不同的迭代器操作（如解引用，递增，递减等）。STD：：vector百分百第一种变体百分之七十二第二种变体百分之八十四在第三个测试用例中，我们创建了一个巨大的向量，并执行了与前一个测试用例相同STD：：vector百分百第一种变体百分之六百零八第二种变体 726%在最后一个测试用例中，我们逐步增加向量的大小，以查看重新分配如何影响性能，并在此向量上应用STL的累积STD：：vector百分百第一种变体百分之一百零N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）83六第二种变体 百分之一百一十在那些迭代器操作占主导地位的应用程序中，我们的解决方案要慢六到七倍（参见。第三个测试用例）。然而，在向量的一般用法中，向量操作的数量与迭代器操作的数量相平衡，我们的解决方案只是比STL的实现稍微慢一点在第二个测试用例中，我们的实现稍微快一点，大概我们的重新分配策略更适合这个测试。也可以看出，第一个变体在所有测试用例中具有更好的效率，以这种方式维护包含的迭代器是不值得的。6结论和今后的工作在本文中，我们提出了C++ STL的一些扩展。这些扩展可以用来避免一些运行时问题，包括无效的迭代器和违反的前提条件。在最初的实现中，这些问题导致了不确定性-84N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）但我们可以处理例外情况。我们利用了许多基于STL的技术，使我们的解决方案更舒适。我们提出了实际的扩展，反向兼容工程与原始代码。此外，我们还测量了我们实现的效率。在本文中，我们没有处理多线程程序，所以我们没有分析我们在多线程环境中的实现。我们将考虑，检查和准备线程程序的实现[3]。在将来，我们考虑如何将无效作为一个特征传递。如果可以参数化失效策略并将其传递给容器，这将非常有用。包含迭代器的维护也可以更复杂，它也应该是一个特质。根据类型系统可以提到另一个方向。 支持C++类型系统的检查以缓存结果并避免不必要的运行时检查将是优雅的。引用[1] Alexandrescu，A.：“Modern C++ Design” Addison-Wesley[2] Austern，M. H.：“Generic Programming and the STL: Using and Extending the C++ Standard TemplateLibrary,” Addison-Wesley[3] Austern ， M.H 、 托 尔 河 一 、 Stepanov ， A. 答 ： Range partition adaptors ： a mechanism forparallelizing STL，in ACM SIGAPP Applied Computing Review 19964（1），pp.五比六[4] 鲍斯角，Becker，T.：STL的自定义迭代器，在C++模板编程的第一次研讨会上。[5] Becker，T.：STL泛型编程：编写自己的迭代器，C/C++用户杂志200119（8），pp. 51比57[6] Bic z'o，M.， P'oczaK.，去你的，我， P或kol'ab，Z.： ANew ConceptofE++ Specific Environment中的E++ R e g ression Test Gene ration，Acta Cybernetica 2008 18（3），pp. 408-501[7] 恰 尔 内 茨 基 ·K. Eisenecker ， U. W. ： “Generative Programming: Methods, Tools and Applications,”Addison-Wesley[8] Das D Vagli， M.， Wong ，M.， Cambly， C.： 加速 C++应用 程序 中的STL集/映射 使用 ，LNCS5119（2008），pp。314-321[9] 来吧，G.， Pataki，N.：C++标准模板库的已验证用法。第10届编程语言和软件工具研 讨 会 （SPLST）2007年，第 10 页。360-371[10] 来吧，G.， Pataki，N.： Atoolforformal specifyingtheC++Standa rdTemplateLibrary，InAnnalesUniversitatisScie ntiarumBuda pestinensisdeRolandoEüotv�os Nominations，SectioComputatorica31，pp. 147比166[11] Gregor，D.， Jüarvi，J.，Siek，J.，Stroustrup，B.， DosReis，G.，Lumsdaine，A.： Conc epts：linguisticsupportfor generic programming in C++ ， in Proc. of the 21st annual ACM SIGPLANconference on Object- Oriented Programming systems ， languages ， and applications （ OOPSLA2006），pp. 291-310.[12] Gregor ， D. ， Schupp ， S. ： Stllint ： lifting static checking from languages to libraries ， Software -Practice Experience，200636（3），pp.225-254[13] Jüarvi，J.，Gregor，D.，Willc ock，J.，Lumsdaine，A.，Siek，J.： 泛型编程中的一个特例：C++中约束泛型的挑战，2006年ACM SIGPLAN编程语言设计和实现会议（PLDI 2006），第10页。272-282.[14] Matsuda，M.，Sato，M.，Ishikawa，Y.：使用C++ STL适配器的并行数组类实现，在面向对象并行环境中的科学计算，LNCS1343，pp。113- 120N. Pataki et al. /Electronic Notes in Theoretical Computer Science 264（5）（2011）85[15] Meyers，S.：“有效的STL - 50种改进标准模板库使用的具体方法”，Addison-Wesley（2001）。[16] Musser， D. R.， Stepanov ， A. 答 ： Generic Programming ， in Proc. of the International SymposiumISSAC13-25[17] P ataki，N.， Por kol'ab，Z.，Istenes ，Z.：C++标准模板库的 语 法 正 确 性 检 验 . 电子计算机和信息学，ECI 2006，pp。186-191。[18] Pataki，N.， Szugyi，Z.， 你好，G.：C ++标准模板库在一个更安全的方式，在程序. WGT 2010（WGT2010），pp. 46比55[19] Pirkelbauer，P.，Parent，S.，马库斯，M.，Stroustrup，B.：C++标准模板库，在Proc.在2008年ACM应用计算研讨会上，171比177[20] P or kol'ab，Z.， 如果你 愿 意 ， Pataki，N.： 在C++标准模板库中，在Proc. 第11届面向对象软件工程定量方法ECOOP研讨会QAOOSE研讨会，ECOOP 2007，柏林，pp.2比6[21] Stroustrup，B.：“The C++ Programming Language”,[22] Szugyi，Z.， 如果你 愿 意 ， Por kol'ab，Z. 本文介绍了C++概念映射的模型化。 关于生成式编程的 研 讨会（WGT 2008），pp。33比43[23] Szugyi，Z.， Sin kovics，A'.， Pataki，N.， P或kola′b，Z.：C++MetastringLibraryand itsAppli cations，InProc. of Generative and Transformational Techniques in Software Engineering 2009，LNCS 6491，pp.467-486.[24] Torgersen，M.：The Expression Problem Revisited-123-143[25] Zolman，L.：一个STL消息解密器为Visual C++，在C/C++用户杂志，2001年19（7），页。24-30.[26] 我是佐利俄米岛， P或kol'ab，Z.： Toowa rdsaGene ralTemplateInt ros peslib rary，inPr oc. 第三次国际会议（GPCE 2004），LNCS 3286，pp. 266-282。