What is wrong with `std::set`?

Question

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

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 

That is correct!

---

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 

So I wrote this:

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

Which gives this output:

saangeth 

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

Output:

sangeth 

Problem gone!

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.

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

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!

Answer 1

Functors are supposed to be designed in a way where a copy of a functor is identical to the original functor. That is, if you make a copy of one functor and then perform a sequence of operations, the result should be the same no matter which functor you use, or even if you interleave the two functors. This gives the STL implementation the flexibility to copy functors and pass them around as it sees fit.

With your first functor, this claim does not hold because if I copy your functor and then call it, the changes you make to its stored set do not reflect in the original functor, so the copy and the original will perform differently. Similarly, if you take your second functor and make it not store its set by reference, the two copies of the functor will not behave identically.

The reason that your final version of the functor works, though, is because the fact that the set is stored by reference means that any number of copies of tue functor will behave identically to one another.

Hope this helps!