`std :: set`有什么问题？

Question

在另一个主题中,我试图解决这个问题.问题是从a中删除重复的字符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仿函数复制到某个地方,那么它的每个成员也会被复制.我没有看到这里的问题!

Answer 1

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

使用您的第一个仿函数,此声明不成立,因为如果我复制您的仿函数然后调用它,您对其存储集所做的更改不会反映在原始仿函数中,因此副本和原始文件的执行方式会有所不同.类似地,如果您使用第二个仿函数并使其不通过引用存储其集合,则仿函数的两个副本将不会表现相同.

但是,最后版本的仿函数的工作原因是因为该集合是通过引用存储的,这意味着任何数量的tue仿函数副本的行为都相同.

希望这可以帮助!

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

通话"sa"结束后将保留初始信息find_if.同时,该predicate集合为空(其中的插入find_if是本地的).因此,之后的循环将保持第3 a.

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

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).