“std::set”有什么问题？

Question

在另一个主题中，我尝试解决这个问题。问题是从std::string中去除重复字符。

std::string s= "saaangeetha";

由于顺序不重要，所以我先对s进行排序，然后使用std::unique，最后调整大小以获得所需的结果：

aeghnst

没错！

---

现在我想要做同样的事情，但同时我希望字符的顺序保持不变。也就是说，我想要这个输出：

sangeth

所以我写了这个：

template<typename T>
struct is_repeated
{
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    s.erase(std::remove_if(s.begin(), s.end(), is_repeated<char>()), s.end()); 
    std::cout << s ;
}

这将产生以下输出：

saangeth

也就是说，虽然有其他的重复，但a被重复了。这段代码有什么问题吗？

无论如何我稍微改动了一下我的代码：（见注释）

template<typename T>
struct is_repeated
{
    std::set<T> & unique;  //made reference!
    is_repeated(std::set<T> &s) : unique(s) {} //added line!
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    std::set<char> set; //added line!
    s.erase(std::remove_if(s.begin(),s.end(),is_repeated<char>(set)),s.end()); 
    std::cout << s ;
}

输出：

sangeth

问题解决了！

那么第一种解决方案有什么问题呢？

此外，如果我不将成员变量unique设置为引用类型，则问题就无法解决。

std::set 或 is_repeated 函数对象有什么问题？问题出在哪里？

我也注意到，如果把is_repeated函数对象复制到其他地方，那么它的每个成员也会被复制。我看不出这有什么问题！

- Nawaz

---

顺便提一下，对数据进行排序的时间复杂度为O(N log N)。但是有一种更高效的算法可以实现。首先线性遍历字符串，计算每个字符的出现次数。然后再遍历一次字符串，只输出出现次数为1的字符。这种方法的时间复杂度为O(N)。 - Jeff Foster

不需要使用两个循环，只需创建一个布尔数组，检查 bFound[c] 是否等于 true。如果为 false，则将其附加到结果字符串并将 bFound[c] 设置为 true。这样就可以建立过滤器并在一次遍历中使用它。 - Alois Kraus

@Jeff：或者使用unordered_set而不是set。 - kennytm

@Kenny：很遗憾，这个方法不起作用。它仍然会重新排序 :-s - Nawaz

Answer 1

Functors被设计成复制一个functor与原始functor相同。也就是说，如果您复制一个functor并执行一系列操作，则无论您使用哪个functor，甚至如果您交叉使用两个functors，结果都应该相同。这使得STL实现可以灵活地复制functors并将它们传递。

然而，对于您的第一个functor，这种说法并不成立，因为如果我复制您的functor并调用它，您对其存储的set所做的更改不会反映在原始functor中，因此副本和原始functor将表现不同。同样，如果您将第二个functor设置为不通过引用存储其set，则两个functor的副本将无法完全相同。

然而，您最终版本的functor之所以有效，是因为set是通过引用存储的，这意味着任意数量的functor副本将彼此完全相同。

希望这有所帮助！

- templatetypedef

---

你的意思是 std::remove_if 会复制函数对象吗？你能给我看一下代码吗？这个 std::remove_if 的实现并不会复制：http://www.cplusplus.com/reference/algorithm/remove_if/ - Nawaz

这实际上取决于你对STL的实现方式；我认为标准并没有明确说明它是否应该或必须复制。然而，我相当肯定标准规定它可以复制，根据输出结果看起来它确实在这么做。 - templatetypedef

答案是正确的。通常情况下，你的函数对象不应该有状态，因为它们可以被复制。 - Brian Neal

@Nawaz，你提到的那个实现至少会复制一次；谓词“pred”是按值传递的。然而，根据你的结果，我怀疑你正在使用VS2010或相关版本；remove_if的这种实现首先调用find_if，然后调用内部的remove_if实现。这样就会多复制两个“pred”，这可以解释你的结果。 - MSN

Answer 2

在GCC（libstdc++）中，remove_if的实现基本上是这样的:

    template<typename It, typename Pred>
    It remove_if(It first, It last, Pred predicate) {
      first = std::find_if(first, last, predicate);
    //                                  ^^^^^^^^^
      if (first == last)
         return first;
      else {
         It result = first;
         ++ result;
         for (; first != last; ++ first) {
           if (!predicate(*first)) {
    //          ^^^^^^^^^
              *result = std::move(*first);
              ++ result;
           }
         }
      }
    }

请确认以下翻译是否符合要求：

注意，你的谓词作为值传递给find_if，因此在find_if内部修改的结构体和集合将不会传播回调用者。

由于第一个重复项出现在：

  saaangeetha
//  ^

在find_if调用后，初始的"sa"将被保留。与此同时，predicate的集合为空（find_if中的插入是局部的）。因此，之后循环将保留第三个a。

   sa | angeth
// ^^   ^^^^^^
// ||   kept by the loop in remove_if
// ||
// kept by find_if

- kennytm

---

+1. 这解释了这种行为。这完全取决于std::remove_if的实现。 - Nawaz

好的。所有这些分析和学习的底线是：函数对象不能有状态。对吧？ - Nawaz

并非一定如此。例如，for_each算法接受一个函数对象，然后在应用到每个元素后将其返回，并理解它确实会被修改。但是，谓词和比较函数对象不应该具有状态，因为它们应该代表数学上的比较，在时间上不应该发生变化。 - templatetypedef

Answer 3

并不是一个真正的答案，但作为另一个有趣的细节需要考虑的是，尽管它使用了原始函数对象，但它确实有效：

#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

template<typename T>
struct is_repeated {
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    std::remove_copy_if(s.begin(), s.end(), 
                        std::ostream_iterator<char>(std::cout), 
                        is_repeated<char>());
    return 0;
}

编辑：我认为这不影响此行为，但我也纠正了您的函数对象中的一个小问题（operator() 显然应该使用类型为 T 而不是 char 的参数）。

- Jerry Coffin

Answer 4

我认为这个问题可能在于 is_repeated 函数副本在 std::remove_if 的实现中被复制了。如果是这样，将使用默认的复制构造函数，这将调用 std::set 的复制构造函数。你最终可能会得到两个独立使用的 is_repeated 函数。然而，由于它们所包含的 set 是不同的对象，它们无法看到相互之间的更改。如果将字段 is_repeated::unique 更改为引用，则复制的函数仍将使用原始的 set，这正是在此情况下所需的。

- julx

---

我编辑了我的问题。请阅读我最后一行的内容，其中我说：如果is_repeated函数复制到其他地方，则它的每个成员也会被复制。我不明白问题在哪里！ - Nawaz

正如我所写，如果成员被复制，你会得到两个“unique”集合。它们的初始状态都可以是空的。接下来这两个集合可能被用于检查字符a是否存在。 - julx

@KennyTM：但是复制并不会引起问题。我的意思是，当函数被复制时，它的每个成员都会被复制，对吧？ - Nawaz

a) 实例1被复制到实例2中。 b) 实例1正在测试"a"并将其添加到其“unique”集合中。 c) 实例2做相同的事情。由于它使用了另一个集合，因此仍然不包含任何"a"字符，并返回导致问题的结果。 - julx

@Nawaz：不是这样的，因为复制是在空集上完成的。请看我的回答。 - kennytm

Answer 5

函数对象类应该是纯函数，不应该有自己的状态。在Scott Meyer的Effective STL一书中，第39项对此进行了很好的解释。但其要点是，您的函数对象类可能会在算法内部被复制1次或多次。

- Brian Neal

Answer 6

其他答案是正确的，问题在于您使用的函数对象不是可复制安全的。特别地，gcc（4.2）附带的STL将std::remove_if实现为std::find_if与std::remove_copy_if的组合，以定位要删除的第一个元素，然后完成操作。

template <typename ForwardIterator, typename Predicate>
std::remove_if( ForwardIterator first, ForwardIterator end, Predicate pred ) {
   first = std::find_if( first, end, pred ); // [1]
   ForwardIterator i = it;
   return first == last? first 
          : std::remove_copy_if( ++i, end, fist, pred ); // [2]
}

[1]中的复制意味着将找到的第一个元素添加到函数对象的副本中，这意味着第一个'a'将会被遗忘。[2]中的函数对象也被复制了，如果原始函数对象不为空，那么这样做就没问题。

- David Rodríguez - dribeas

Answer 7

根据remove_if的实现方式，可能会复制您的谓词。要么重构您的函数对象并使其无状态，要么使用Boost.Ref来“传递对通常会复制其参数的函数模板（算法）的引用”，例如：

#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

#include <boost/ref.hpp>
#include <boost/bind.hpp>

template<typename T>
struct is_repeated {
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 

int main() {
    std::string s= "saaangeetha";
    s.erase(std::remove_if(s.begin(), s.end(), boost::bind<bool>(boost::ref(is_repeated<char>()),_1)), s.end());
    std::cout << s;

    return 0;
}

- Eugen Constantin Dinca