7.5　集合

集合（set）容器仅接受每个元素的一个副本。它也对元素排序。（进行排序并不是set的概念定义所固有的，但是STL set用一棵平衡树数据结构来存储其元素以提供快速的查找，因此在遍历set的时候就产生了排序的结果。）在本章的前两个例子中用到了set。

考虑为一本书创建索引的问题。有人可能喜欢从书中的所有单词开始创建，但是每个单词只需要一个实例，并且希望它们排过序。对于这个问题，容器set是理想的选择，它可以毫不费力地解决这个问题。然而，还存在标点符号和非字母字符的问题，它们必须被去掉以便产生正确的单词。该问题的一个解决方案就是用标准C库函数isalpha（）和isspace（）提取只需要的字符。可以用空白字符来替换所有不需要的字符，这样就可以很容易地从读入的每一行中提取出合法的单词：

调用transform（），以空白字符替换每个要被忽略掉的字符。容器set不但忽略重复的单词，而且根据函数对象less＜string＞（set容器默认的第2个模板参数）比较它保存的那些单词，该函数依次使用string：operator＜（）进行比较操作，因此这些单词按字母顺序出现。

仅仅为了得到一个经过排序的序列，就没有必要使用set。可以在不同的STL容器上使用函数sort（）（与STL众多的其他函数）来达到这个目的。然而，在这里或许set将会更快地完成该操作。当只想做查找操作时，使用set将会特别便利，因为其find（）成员函数有对数级的复杂性，因此它比通用的find（）算法要快得多。如前所述，通用的find（）算法需要遍历全部范围直到找到要搜寻的元素（这将导致最坏情况下算法复杂性为N，平均复杂性为N/2）。然而，如果有一个已经排过序的序列容器，在查找元素时使用equal_range（），就可以得到对数级的算法复杂性。

下面这个程序显示了如何使用迭代器istreambuf_iterator来构建单词表，迭代器将字符从一个地方（输入流）移到另一个地方（一个string对象），该操作依赖标准C库函数isalpha（）的返回值是否为真：

这个例子是由Nathan Myers提议的，他发明了istreambuf_iterator及其家族成员。这个迭代器从一个流中逐字符地提取信息。虽然istreambuf_iterator的模板参数可能暗示读者提取例如以int型数据而非char型数据，但事实却不是这样。该参数必须是某些字符类型—常规的char类型或宽字符类型。

文件打开以后，称为p的istreambuf_iterator被附到该istream上，这样就可以从中提取字符了。名为wordlist的set＜string＞将保存作为结果的单词。

采用while循环从输入流中读取单词直到发现输入流结束。这是用istreambuf_iterator的默认构造函数进行检测的，它产生超越末尾的迭代器对象end。因此，如果要进行测试以确信不在该流的末尾，只需用p！=end。

在这里使用的第2个迭代器类型是在前面已经看到的insert_iterator。利用它将对象插入一个容器。在这里，“容器”是一个称为word的string，它对于insert_iterator的目的来说，其行为像一个容器。对于insert_iterator的构造函数，则需要该容器和一个指明应在何处开始插入这些字符的迭代器。也可以使用一个back_insert_iterator，它需要容器拥有一个push_back（）（string产生）。

while循环在做好各种准备后，就开始查找第1个字母字符，对start进行增1操作直到那个字符被找到。然后将查找到的字符从一个迭代器指向的位置复制到另一个迭代器指向的位置，当发现一个非字母字符时停止复制。假定其不为空，则每一个word都被添加到wordlist中去。

可完全重用的标识符识别器

单词表例子使用不同的方法从流中提取标识符，但它们都不特别灵活。因为STL容器和算法都是围绕着迭代器来展开的，所以最灵活的解决方法是它自己使用迭代器。可以把TokenIterator想象成一个迭代器，该迭代器封装其任何能够产生字符的其他迭代器。因为它确实是一个输入迭代器类型（最原始的迭代器类型），可以向任何STL算法提供输入。不仅其本身就是一个很有用的工具，下列的TokenIterator也是如何设计用户自己的迭代器的很好的例子。^[1]

TokenIterator类具有双重灵活性。首先，可以选择产生char输入的迭代器类型。其次，TokenIterator不是仅说明什么字符表示分界符，而是使用一个函数对象判定函数，其operator（）接受一个char型参数并决定它是否将计入标识符。虽然这两个例子在这里给出了什么字符属于标识符的静态概念，但是用户可以很容易地设计自己的函数对象，以便在读入字符的时候改变其状态，创建一个更复杂的解析器。

和TokenIterator模板一起，下列的头文件还包含了两个基本判定函数，Isalpha和Delimiters：

TokenIterator类派生自std：iterator模板。它可能表现出某些来自std：iterator的功能，但它是纯粹对迭代器进行标记的一种方式，用来告诉使用它的容器可以做些什么。在这里，可以看到作为iterator_category模板参数的input_iterator_tag—这告诉那些询问者，TokenIterator只有一个输入迭代器的能力，不能与那些需要更复杂的迭代器的算法一起使用。除了进行标记以外，std：iterator不能做超出提供几个有用的类型定义的任何事情。用户必须自行实现所有其他的功能。

起初读者可能会认为TokenIterator类有点奇怪，因为其第1个构造函数需要“开始”和“终止”两个迭代器作为参数，和它们在一起的还有一个判定函数。记住，这是一个“封装器”迭代器，在输入结束时它没有办法如何告知何时其输入处于末尾，所以在第1个构造函数中这个“终止”迭代器是必需的。第2个（默认）构造函数存在的理由是，STL算法（以及所有用户自己编写的算法）需要一个TokenIterator标记作为超越末尾的值。因为判断一个TokenIterator是否已经到达其输入的末尾的所有信息都已经由第1个构造函数收集，这第2个构造函数创建TokenIterator对象，在算法中它只作为占位符使用。

行为的核心发生在运算符operator++中。它使用string：resize（）擦除当前word的值，然后使用find_if（）寻找第1个满足判定函数的字符（如此来发现一个新的标识符的起始位置）。结果迭代器被分配给first，因此将first向前移动至标识符的起始位置。然后，一旦判定函数被满足而又没有到达输入的末尾，输入字符就被复制到word中。最后，TokenIterator对象返回，并且必须被解析以便访问新的标识符。

这里的前缀增1要求有一个CaptureState类型的对象在增1前持有值，因此它是可以返回的。产生的实际值是一个直接的operator*操作。为输出迭代器定义的其余的函数仅仅是operator==和operator！=，用以指明TokenIterator是否已经到达了其输入的末尾。读者可以看到operator==的参数被忽略—它仅仅关心是否已经到达其内部的last迭代器。注意，operator！=是通过operator==定义的。

一个好的TokenIterator测试包括许多不同来源的输入字符，包括一个streambuf_iterator、一个char*和一个deque＜char＞：iterator。最后，最初的单词表的问题解决如下：

在使用istreambuf_iterator时，创建一个附属于istream的对象，并与默认构造函数一起作为超越末尾标记。这两者用于创建将产生标识符的TokenIterator；而默认构造函数创建一个伪TokenIterator超越末尾的标记。（这仅仅是个占位符并且被忽略。）TokenIterator产生那些要被插入string容器的string—在这里，除了最后一个以外，在所有的情况下都使用vector＜string＞。（也可以将所有的结果连接成一个string。）除此之外，TokenIterator就像任何其他输入迭代器一样工作。

在定义一个双向（并且因此也成为一个随机访问）迭代器时，可以使用std：reverse_iterator适配器“免费地”得到反向迭代器。如果已经为一个具有双向能力的容器定义了一个迭代器的话，可以从如下在容器类里的前向遍历迭代器那里得到一个反向迭代器：

std：reverse iterator适配器可以做所有这些工作。比如，如果使用运算符*来解析反向迭代器，它自动地对它持有的前向迭代器的一个临时拷贝减1，以便返回正确的元素，因为反向迭代器在逻辑上指向它们引用的元素的下一个位置。

[1]这是Nathan Myers讲授的另一个例子。