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

Ответ 1

В GCC (libstdС++), 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 являются локальными). Поэтому цикл после этого будет удерживать третий a.

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

Ответ 2

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

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

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

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

Ответ 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).

Ответ 4

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

Ответ 5

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

Ответ 6

Другие ответы верны, поскольку проблема заключается в том, что используемый вами функтор не является безопасным для копирования. В частности, STL, который поставляется с gcc (4.2), реализует std::remove_if как комбинацию std::find_if, чтобы найти первый элемент для удаления, за которым следует a 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], и это было бы хорошо, если бы не потому, что оригинал для этой копии был пустым функтором.

Ответ 7

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