21

在另一个主题中，我试图解决这个问题。问题是从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仿函数被复制到某个地方，那么它的每个成员也会被复制。我看不到这里的问题！

4

7 回答 7

17

仿函数的设计方式应该是仿函数的副本与原始仿函数相同。也就是说，如果您复制一个函子，然后执行一系列操作，则无论您使用哪个函子，或者即使您交错两个函子，结果都应该是相同的。这使 STL 实现可以灵活地复制仿函数并在它认为合适的时候传递它们。

对于您的第一个函子，此声明不成立，因为如果我复制您的函子然后调用它，您对其存储集所做的更改不会反映在原始函子中，因此副本和原始函子的执行方式将不同。同样，如果您使用第二个仿函数并使其不通过引用存储其集合，则仿函数的两个副本的行为将不同。

但是，您的函子的最终版本起作用的原因是，集合是通过引用存储的这一事实意味着任何数量的 tue 函子副本的行为将彼此相同。

希望这可以帮助！

于 2011-03-22T20:53:52.320 回答
15

在 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
//  ^

首字母"sa"将在find_if通话后保留。同时，predicate的集合是空的（其中的插入find_if是本地的）。因此之后的循环将保持 3rd a。

   sa | angeth
// ^^   ^^^^^^
// ||   kept by the loop in remove_if
// ||
// kept by find_if
于 2011-03-22T21:07:41.817 回答
5

不是一个真正的答案，但作为另一个值得考虑的有趣花絮，这确实有效，即使它使用了原始仿函数：

#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）。

于 2011-03-22T21:07:24.343 回答
4

我想问题可能在于is_repeated仿函数被复制到std::remove_if. 如果是这种情况，则使用默认的复制构造函数，然后 this 调用std::set复制构造函数。您最终会得到两个is_repeated可能独立使用的仿函数。然而，由于它们中的集合是不同的对象，它们看不到相互的变化。如果您将该字段is_repeated::unique转换为引用，则复制的仿函数仍然使用原始集合，这就是您在这种情况下想要的。

于 2011-03-22T20:51:05.393 回答
2

Functor 类应该是纯函数并且没有自己的状态。请参阅 Scott Meyer 的Effective STL book 中的第 39 项，以获得对此的良好解释。但它的要点是，您的仿函数类可能会在算法中被复制 1 次或多次。

于 2011-03-22T21:21:40.363 回答
1

其他答案是正确的，因为问题是您使用的仿函数不是可复制安全的。特别是，gcc (4.2) 附带的 STL 实现std::remove_if了一个组合std::find_if来定位要删除的第一个元素，然后是 astd::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] 中，如果不是因为该副本的原件是一个空仿函数，那就没问题了。

于 2011-03-22T21:38:22.940 回答
1

根据执行情况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;
}
于 2011-03-22T23:51:30.153 回答