Klaus Kreft and Angelika Langer
http://www.cuj.com/experts/1810/kreft.htm?topic=experts
在这个专栏中，我们将考察标准运行库中容器set的实现，看看这些实现有多么多样化，以及它们的差异对程序的可移植性造成多大影响。摘要：
l 标准C++运行库中的容器set是用二叉树实现的， 这意味着set中的元素的值决定了它在树中的位置。和所有标准库容器一样，set通过iterator来访问其中的元素。iterator被设计为通过反引用操作来提供对所指元素的读/写访问的。换句话说，我们能通过容器的 iterator来修改其中的元素。
l 对一个set，修改其中的元素会破坏内部的树结构[注1]。因此，set的提供写访问权的iterator（所谓的mutable iterator）被认为是危险的。更有甚者，如果将iterator传给泛型算法，对某些泛型算法（包括remove()泛型算法），它们将悄悄地破坏掉set容器。
l 某些运行库实作试图通过不对set提供mutable的iterator来解决问题。这是安全的，但造成了set在可用性方面的严重限制。基于这个理由，其它的实作决定信赖使用者，而提供mutable的iterator。实际结果是，set及其iterator有可供使用不同实现，因此我们一定要注意可移植性问题。
在这一个专栏中，我们考察set的不同的实现，看看它们引入的缺陷和限制，并探究有什么可移植性问题以及如何解决。
内部的树结构C++标准运行库提供的set容器内部是用二叉树结构组织的，因为标准为所有的泛型算法和容器操作规定了某种复杂度要求。对于set，它要求访问元素必须是对数时间的。为了达到这个要求，set的实现必须基于二叉树结构。( 关于二叉树的细节可以在讨论数据结构和算法的计算机书籍中找到[注2]。)
二叉树的元素在树中的位置是由排序顺序决定的。这在set上表现出来了：它需要一个对元素类型进行操作的比较器。让我们考虑一个例子。假设我们有一个银行帐户类account。它有一个帐户号number和余额balance。在我们的程序中，用一个set容器维护所有的帐户。排序准则是依据帐户号number。set使用less-than作为比较器，并且定义了相应的operator<()版本以用帐户号number比较帐户对象。
class account {
...
size_t _number; // determines ordering
double _balance; // irrelevant for ordering
};
bool operator<(const account& lhs,
const account& rhs)
{ return lhs._number < rhs._number; }
set<account> allAccounts;
set根据这个顺序来决定元素在内部的二叉树中的位置。每当一个元素被加入set，它将被自动地放到正确的位置，以使得元素仍然保持已序状态。当查找一个元素时，相应的搜索算法能根据这个排序高效地遍历树结构。既然set的所有操作都依赖于正确安排的二叉树，很有必要让树在任何时候都要保持完整。
自然地，二叉树被隐藏在set的接口后面，而且只要我们通过它的成员函数来执行修改操作，我们就不会破坏内部的树。然而，标准运行库中还有iterator。
set的Iterator和标准运行库中的所有容器一样，set通过iterator提供对它内部元素的访问。Iterator是类指针对象，可以被反引用（通过反引用操作operater*()）以访问它们所指向的元素。有两种iterator：提供读/写的（称为mutale iterator）和只提供读的（immutable iterator）。在标准运行库中，mutable iterator类型是container::iterator；immutable iterator类型是container::const_iterator。所有的容器类，包括set，必须定义这两个iterator类型。
如果我们有一个set的mutable的iterator并且反引用它，我们将得到对set中元素的写访问权，并能修改其内容。这样的修改可能是极其灾难性的。想一下我们我们正在做的：iterator指向二叉树的一个节点。元素在树中的位置现在是正确的，并反映了它在排序中的位置。当我们以影响排序顺序的方式改变一个元素时（比如，修改比较器所使用的数据成员），那么根据排序，元素应该出现在一个不同的位置上。树必须重新组织以反映新的排序结果。但这不是将要发生的。我们悄悄改变了元素而没有改变它在二叉树中的位置。结果是一个被破坏的树，而对被破坏的树的操作，其行为完全不可预知。
明显，通过set的mutalbe的iterator来修改元素是没有意义的。因此，不成文的规则是：
规定 1：不要以破坏排序的方式修改set中的元素。
这个规则适用于所有通过iterator、[指向容器中元素的]指针和引用所作的所有修改动作。虽然这个规则看起来很有道理，但遵从起来比我们所认为的要难得多。
替换set的元素让我们回顾一下前面的例子以弄清楚遵从这条规则有多容易或多难。我们维护了一个银行帐户的set，是根据帐户号number排序的。一个客户想换到另外一种帐户，并要求用新帐户取代老的。如果我们有一个指向老帐户对象的iterator，我们可以这样实现替换：
set<account> s;
...
set<account>::iterator iter;
...
*iter = *new account; // direct modification of element
这无疑违犯了规则1。虽然新帐户拥有和老帐户相同的数据（比如，name、balance等等），但它很有可能有一个不同的帐户号。用新内容覆盖树中的已存位置也包含了覆盖排序准则[所使用的数据]并破坏了树结构。要替换set中的已存元素，我们应该使用成员函数insert()和erase()而不是通过set的iterator来执行替换。正确的方式是：
set<account> s;
...
set<account>::iterator iter;
...
s.insert(iter, *new account);
s.erase (iter);
insert()成员函数将新元素放在树的正确位置，这样保持了树的完整。它导出了另外一个规则：
规则2: 不要通过set的iterator、[指向元素的]指针或引用来替换元素。改用set的inster()和erase()操作。
set容器和泛型算法这是对规则 1的一个还算明显的违反。但是经常是违反并不怎么明显。下面的程序怎么说？在我们的银行程序中，被取消的帐户并不立即从set中去除，还会存在一段时间，直到垃圾回收器去除它们。废弃的帐户可以通过balance为0而判断出来。它们可以使用remove_if()泛型算法而一次就全部移除。我们所需要的就是一个predicate函数（它判断balance是否为0）：
bool obsolete(const account& acc)
{ return acc.balance() == 0; }
然后使用remove_if()泛型算法，并且很快就完成了：
set<account> s;
...
// remove element if balance is less than 0
s.erase(remove_if(s.begin(),s.end(),obsolete),
s.end(),s.end());
粗看起来很好，但它使得我们破坏了set容器。
名不副实：remove()并不移除[元素]对于本例，为什么违反了规则1，并不是很明显。我们用某中方式影响了排序顺序？从remove_if()泛型算法的描述中，可能得出一个结论：我们从一个已序队列中移除了某些元素，并产生了另外一个已序队列。事实上，标准是这样描述remove_if()泛型算法的：
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first,
ForwardIterator last,
Predicate pred);
要求： 类型T是EqualityComparable。
效果： 去除区间[first, last)内所有满足pred(*i) != false的元素。
返回值： 结果区间的end
附注： 稳定的；没被移除的元素的相对顺序与原始区间相同。
复杂度： 精确的last - first次调用predicate。
那么，为什么这样的移除会破坏树结构？
回答是所有的变动性算法（mutating algorithm）（WQ注，参看《C++标准程序库》中文版P386，此书对此使用modifying algorithm一词，而将mutating algorithm用于变序性算法）都潜在地打破了set容器的树结构。这是因为标准运行库中的泛型算法通过iterator访问容器中的元素，而如果是变动性算法，它们将通过iterator执行修改操作。remove_if()是这样一个变动性算法。
问题是移除性算法（remove algorithm）(这包括remove()、remove_if()及其变种)常被误解。它们的名字是错误的：移除性算法并不移除任何东西。事实上，没有任何一个元素被从序列中移除[注3]。取而代之的，所有有效元素（在我们的例子中是没有废弃的帐户）被拷贝到序列头部，而在尾部留下一堆垃圾。remove_if()泛型算法返回指向尾部垃圾的iterator，我们必须手工调用set的erase()成员函数来移除无效元素。图 1（CUJ上提供的已失效地址http://www.cuj.com/experts/1810/kreft_x.htm?topic=experts#x1）举例说明了remove_if()泛型算法的功能。
在remove_if()泛型算法内部，将有效元素拷贝到序列头部是通过指向序列中的元素的iterator来进行的。这个泛型算法确实做了我们在规则2中指出的问题：它通过反引用一个iterator来将一个元素赋给另外一个元素的。在任何移除性算法的实现中，我们将找到这样一行语句：
* iter1 = *iter2;
在我们的例子中，iter1和iter2是set的iterator。这个赋值打破了排序。
因此，它导了对set的另外一个规则：
规则3: 不要对set使用变动性算法。
在这个地方，“变动性算法”是指通过容器的iterator(或指向元素的指针或引用)来修改元素，而不是使得容器提供的操作（容器的成员函数）的算法。标准运行库中的所有变动性算法（比如copy()、swap()、replace()、remove()、reverse()）都在这个范畴之内。
困境现在应该很清楚了，set的mutable的iterator实际上是一个陷阱，因为它们使得很容易破坏set容器。那么，究竟为什么会有它们呢？如后面将要见到的，容器有mutable的iterator才感觉完美，因为我们不只是查看存储在容器中的元素，有时还想修改这些元素。此外，标准要求所有的容器一定有mutable的和immutable的iterator类型。这是容器的固有概念。扔掉set的mutable的iterator将会挑战泛型这个主意，而这正是设计标准运行库中的容器和泛型算法的中心思想。结果，运行库的实现者陷入了困境，而标准没有说该如何摆脱。
一些运行库的实现者决定信任用户，而对于这些实现(让我们称它们为被放松的实现) ，确保不破坏树结构是我们的职责。然而，这常常比我们想象得困难，如上所示。
其他的实现者打算减少潜在的危险，并决定根本不提供set的mutable的iterator。在那些实现中(让我们称它们为安全实现)，类型set::iterator是set::const_iterator的一个typedef。效果是存储在set中的元素不够通过iterator来修改。这显然比较安全，因为它至少移除了通过iterator破坏树结构的可能性。我们仍然可以通过指向被容纳的元素的指针和引用来破坏set容器，但不提供mutable的iterator肯定是一个进步。然而，这是有代价的；有某些限制。
修改一个元素并不一定影响排序。如果我们只改变了不影响排序的部分，怎么说？这应该是一个无害的修改。悲哀的是，如果set没有mutable的iterator，那么我们就不能通过iterator执行无害的修改，虽然这样做是安全的。
对set中元素的无害修改回顾例子。我们使用了一个帐户的set，并根据帐户号排序的。
class account {
...
size_t _number; // determines ordering
double _balance; // irrelevant for ordering
};
bool operator<(const account&
lhs, const account& rhs)
{ return lhs._number < rhs._number; }
set<account> allAccounts;
在这种情况下，balance和排序无关，修改set中帐户对象的balance数据成员应该是安全的。
set<account>::iterator iter;
...
// direct modification of part of the element
iter->balance = 1000000;
在被放松的set实现中，这能工作；当使用一个安全实现时，编译器将会抱怨一个constness问题。无疑，程序是有意义的，但是它基于set的iterator是mutable的假设的，而这一点实践中未必成立。因此我们遇到了一个问题。问题主要关于可移植性的[注4]。在一个标准运行库的实作中能工作的东西不能在另外一个实作中工作。
我们如何解决这个问题？
暴力方式Constness问题可以通过强制转换而解决，对吧？取代
iter->balance = 1000000;
我们可以
*(const_cast<double*>(&(iter->_balance))) =
1000000;
注意，你不能够对一个对象执行const_cast，只能对指针和引用进行。另外一种可行方式是，我们可以在account类中定义一个const的成员函数以让我们修改balance，但我希望我们能同意强制转换和假const成员函数是糟糕的编程风格，并应该尽可能避免。让我们试着做得更好。
Iterator适配器虽然我们不能够除去const_cast，我们仍然可以试图深入问题的核心并就在它出现的地方解决它。是set的iterator让我们陷入困境的。为什么不定义一个新的iterator类型，它能让我们访问帐户的balance部分，而不暴露帐户号？主意是适配set的iterator，于是适配后的iterator允许无害的修改，但禁止修改和排序相关的部分。
取代通过set的iterator访问元素
set<account>::iterator iter;
...
iter->balance = 1000000;
我们将通过适配后的iterator访问它，可称之为balanceIter：
set<account>::iterator iter;
...
*balanceIter(iter) = 1000000;
实践中，C++程序员很少实现自己的自定义iterator类型，因为他们认为这太复杂了，但它实际上相当容易并且非常有用。下面是一个实现的简要描述：
class balanceIter {
private:
set<account>::iterator _i;
public:
explicit balanceIter(set<account>::iterator i)
:_i(i) {}
balanceIter& operator++() { ++_i; return *this; }
// ... postfix ++, pre- and postfix -- ...
double& operator*() const
{ return *const_cast<double*>(&_i->_balance); }
};
重点是：
l iterator的适配器将原始的iterator(即adaptee)保存为一个数据成员。
l adaptee在构造时被提供；也就是说，构造函数接受原始的iterator作为参数。
l 所有iterator的典型运算必须要被提供，比如operator++，operator--，operator==，等等。他们被实现为委托给adaptee。
l 唯一的有趣的操作是反引用操作。它必须提供对帐户对象的balance部分的写访问权。它的签名和adaptee的反引用操作的签名不同，因为它返回对balance部分的non-const的引用，而不是整个帐户对象的const的引用。
当实现iterator类型时，还有几个细节需要记住，比如提供base()成员函数以能访问adaptee，和提供iterator的嵌套类型(参见Listing 1或[注5]以作为进一步的阅读，或参考你珍藏的介绍标准运行库的书以了解如何实现iterator的适配器。)
评估我们仍然必须在某处使用丑陋的const_cast，但它现在被隐藏在iterator适配器的反引用操作中。不需要修改account类，没有显眼地违背const-correctness规则。我们正确地解决了遇到的问题，而没有在安全性方面造成额外的漏洞。仍然有一个已存的安全性漏洞；我们能够通过适配后的iterator运用泛型算法，但这个问题已经被规则3覆盖了：不要对set使用变动性算法。另外，这个解决方法是可移植的。即使当我们使用set的被放松的实现，iterator适配器也不会造成问题。因为它的所有操作都是内联函数，它不会增加任何开销。
为了避免可移植性问题，这是另外一个建议：
规定 4: 不要通过set的iterator（类型是set<T>::iterator）修改其中的元素。使用iterator适配器来完成不破坏排序的修改。
不破坏排序的修改是被包容的元素中不影响排序的部分上的变化。
总结C++标准没有指明set的iterator（类型是set<T>::iterator）是mutable的还是imutable的。结果，流行的编译器和它们的标准运行库对set的iterator提供了不同的实现。工作于一个实作的程序可能不能在另一个下工作。为了避免可移植性问题，绝不要对set的iterator在mutability/immutability上作任何假设。
我们确定了使用set时的四个有关规则：
l 规定 1：不要以破坏排序的方式修改set中的元素。
l 规定 2: 不要通过set的iterator、[指向元素的]指针或引用来替换元素。改用set的inster()和erase()操作。
l 规定 3: 不要对set使用通过iterator、[指向元素的]指针或引用来修改元素的泛型算法。这包括标准运行库中的所有变动性算法。
l 规定 4: 不要通过set的iterator（类型是set<T>::iterator）修改其中的元素。使用iterator适配器来完成不破坏排序的修改。
规则1到规则3总是成立的，而不依赖于任何标准运行库的特定实现。规则4涉及可移植性问题，它源于实践中set及其iterator类型的不同实现。
Listing 1: The balanceIterator adapterclass balanceIterator
{
public:
typedef set<account>::iterator adapted_type;
typedef adapted_type::iterator_category iterator_category;
typedef adapted_type::value_type value_type;
typedef adapted_type::distance_type difference_type;
typedef double* pointer;
typedef double& reference;
balanceIterator() {}
explicit balanceIterator(adapted_type i) :adaptee(i) {}
template <class Iter>
adapted_type base() const { return adaptee; }
reference operator*() const
{return const_cast<reference>(adaptee->balance()); }
pointer operator->() const { return &(operator*()); }
balanceIterator& operator++()
{ ++adaptee;
return (*this);
}
balanceIterator operator++(int)
{ balanceIterator _Tmp = *this;
++adaptee;
return (_Tmp);
}
balanceIterator& operator--()
{ --adaptee;
return (*this);
}
balanceIterator operator--(int)
{ balanceIterator _Tmp = *this;
--adaptee;
return (_Tmp);
}
private:
adapted_type adaptee;
};
inline bool operator==(const balanceIterator& x,
const balanceIterator& y) {
return x.base() == y.base();
}
inline bool operator!=(const balanceIterator& x,
const balanceIterator& y) {
return x.base() != y.base();
}
附注和引用[1] Herb Sutter. "Standard Library News, Part 2, Sets and Maps," C++ Report (October 1999). This article gives background information on sets and maps; Sutter explains why keys in associative arrays like set must not be modified.
[2] Cormen, Leiserson, and Rivest. Introduction to Algorithms (MIT Press, 1990).
[3] Matt Austern. "Algorithms and Containers," C++ Report (July/August 2000). This article also points out the problem of applying the remove algorithms to associative containers and suggests a solution using container-based generic algorithms and container traits, which are not part of the Standard.
[4] How can one have a portability problem with the Standard library? After all, the purpose of a standard is that it defines a portability platform. True, it's just that in this case we are talking about an open issue in the C++ Standard: the implementation of the set iterators is still an open issue (#103) on the Standards Committee issue list. The problem is identified and a clarification will be added to the Standard.
[5] Klaus Kreft and Angelika Langer. "Iterators in the Standard C++ Library, " C++ Report (November/December 1996). The article is also available at http://www.langer.camelot.de/Articles/IteratorsInStdlib/cppr9612_kreft.html.
本文地址：http://com.8s8s.com/it/it1787.htm