Что не так с `std::set`?
В другой теме я пытался решить эту проблему. Проблема заключалась в удалении повторяющихся символов из 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 Функтор куда-то копируется, затем копируется каждый его член. Я не вижу здесь проблемы!
7 ответов
В 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
Предполагается, что функторы должны быть сконструированы таким образом, чтобы копия функтора была идентична оригинальному функтору. То есть, если вы делаете копию одного функтора и затем выполняете последовательность операций, результат должен быть одинаковым независимо от того, какой функтор вы используете, или даже если вы чередуете два функтора. Это дает реализации STL гибкость для копирования функторов и их передачи по своему усмотрению.
С вашим первым функтором это утверждение не выполняется, потому что, если я скопирую ваш функтор, а затем вызову его, изменения, внесенные в его сохраненный набор, не будут отражены в исходном функторе, поэтому копия и оригинал будут работать по-разному. Аналогичным образом, если вы возьмете второй функтор и не сохраните его набор по ссылке, две копии функтора не будут вести себя одинаково.
Причина того, что ваша окончательная версия функтора работает, заключается в том, что тот факт, что набор хранится по ссылке, означает, что любое количество копий тью функтора будет вести себя идентично друг другу.
Надеюсь это поможет!
На самом деле это не ответ, а еще один интересный момент, который работает, хотя он и использует оригинальный функтор:
#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).
Я полагаю, что проблема может заключаться в том, что is_repeated Функтор копируется где-то внутри реализации std::remove_if, Если это так, то используется конструктор копирования по умолчанию, а это, в свою очередь, вызывает std::set Копировать конструктор. Вы в конечном итоге с двумя is_repeated Функторы, возможно, используются независимо. Однако поскольку наборы в обоих из них являются отдельными объектами, они не видят взаимных изменений. Если вы включите поле is_repeated::unique к ссылке, тогда скопированный функтор все еще использует исходный набор, который вам нужен в этом случае.
Классы функторов должны быть чистыми функциями и не иметь собственного состояния. См. Пункт 39 в книге Скотта Мейера " Эффективный STL" для хорошего объяснения этого. Но суть в том, что ваш класс функторов может быть скопирован 1 или более раз внутри алгоритма.
В зависимости от реализации 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;
}
Другие ответы верны, потому что проблема в том, что используемый вами функтор не является безопасным для копирования. В частности, 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], и это было бы хорошо, если бы не было, потому что оригинал для этой копии - пустой функтор.