Что не так с `std :: set`?

Question

В другая тема Я пытался решить эту проблему.Проблема заключалась в удалении повторяющихся символов из std::string.

std::string s= "saaangeetha";

Поскольку порядок не был важен, поэтому я сначала отсортировал s, а затем использовал std::unique и, наконец, изменил его размер, чтобы получить желаемый результат :

aeghnst

Это правильно!

---

Теперь я хочу сделать то же самое, но в то же время я хочу, чтобы порядок символов не изменился.Значит, я хочу этот вывод:

sangeth

Итак, я написал 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 ;
}

, который дает этот вывод:

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 гибкость для копирования функторов и передачи их по своему усмотрению.

С вашим первым функтором это утверждение не выполняется, потому что если я скопирую ваш функтор, а затем вызову его, внесенные вами измененияего сохраненный набор не отражается в оригинальном функторе, поэтому копия и оригинал будут работать по-разному.Точно так же, если вы возьмете второй функтор и не сохраните его набор по ссылке, две копии функтора не будут вести себя одинаково.

Причина, по которой ваша окончательная версия функтора работает, заключается в том, чтотот факт, что набор хранится по ссылке, означает, что любое количество копий фьюнктора будет вести себя идентично друг другу.

Надеюсь, это поможет!

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

Редактировать: я не думаю, что это влияет на это поведение, ноЯ также исправил небольшую ошибку в вашем функторе (оператор () должен принимать параметр типа T, а не char).

Answer 4

Полагаю, проблема может заключаться в том, что функтор is_repeated скопирован где-то внутри реализации std::remove_if.В этом случае используется конструктор копирования по умолчанию, а это, в свою очередь, вызывает std::set конструктор копирования.В итоге вы получите два is_repeated функтора, возможно, используемых независимо.Однако, поскольку наборы в обоих из них являются различными объектами, они не видят взаимных изменений.Если вы превратите поле is_repeated::unique в ссылку, то скопированный функтор все еще будет использовать исходный набор, который вам нужен в этом случае.

Answer 5

Классы функторов должны быть чистыми функциями и не иметь собственного состояния. См. Пункт 39 в книге Скотта Мейера Effective STL для хорошего объяснения этого. Но суть в том, что ваш класс функторов может быть скопирован 1 или более раз внутри алгоритма.

Answer 6

В зависимости от реализации 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;
}

Answer 7

Другие ответы верны, поскольку проблема заключается в том, что используемый вами функтор не является копируемым безопасным. В частности, STL, который поставляется с gcc (4.2), реализует 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] означает, что первый найденный элемент добавляется к копии функтора, и это означает, что первый «а» будет потерян в забвении. Функтор также копируется в [2], и это было бы хорошо, если бы не было, потому что оригинал для этой копии - пустой функтор.