`std :: set`有什么问题？ [英] What is wrong with `std::set`?

问题描述

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

In the other topic I was trying to solve this problem. The problem was to remove duplicate characters from a std::string.

std::string s= "saaangeetha";

因为顺序不重要，所以我排序 s 首先，然后使用 std :: unique ，最后调整大小以获得所需的结果：

Since the order was not important, so I sorted s first, and then used std::unique and finally resized it to get the desired result:

aeghnst

这是正确的！

现在我想做同样的事情，但同时我想要的字符顺序完好无损。方法，我想要这个输出：

Now I want to do the same, but at the same time I want the order of characters intact. Means, I want this output:

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

c> a 被重复，虽然其他重复也没有了。代码有什么问题？

That is, a is repeated, though other repetitions gone. What is wrong with the code?

无论如何我更改我的代码有点： （见注释）

Anyway I change my code a bit: (see the comment)

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

问题所在！

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

So what is wrong with the first solution?

此外，如果我不使成员变量 引用类型，然后问题不能解决。

Also, if I don't make the member variable unique reference type, then the problem doesn't go.

std :: set 或 is_repeated 函子有什么问题？

What is wrong with std::set or is_repeated functor? Where exactly is the problem?

我还注意到如果 is_repeated 函子被复制到某处，它的每个成员也被复制。我在这里看不到问题！

I also note that if the is_repeated functor is copied somewhere, then every member of it is also copied. I don't see the problem here!

推荐答案

在GCC（libstdc ++）中， remove_if

In GCC (libstdc++), remove_if is implemented essentially as

    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;
           }
         }
      }
    }

您的谓词被传递<-em> by-value 到 find_if ，所以结构体以及集合被修改在 find_if 不会传播回调用者。

Note that your predicate is passed by-value to find_if, so the struct, and therefore the set, modified inside find_if will not be propagated back to caller.

由于第一个副本出现在：

Since the first duplicate appears at:

  saaangeetha
//  ^

code> find_if 调用后将保留code>sa。同时，谓词的集合为空（ find_if 中的插入是局部的）。因此，循环之后将保持第三个 a 。

The initial "sa" will be kept after the find_if call. Meanwhile, the predicate's set is empty (the insertions within find_if are local). Therefore the loop afterwards will keep the 3rd a.

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

这篇关于`std :: set`有什么问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！