std :: unique с предикатом, сравнивающим std :: string без удаления дубликата
Если я что-то упускаю или неправильно понимаю механизм (очень вероятно) Разве не должно существовать дубликат «1» в этом векторе?
chunks.erase( std::unique ( chunks.begin(), chunks.end(),
[]( std::string &s1, std::string &s2 ){
return ( s1.compare(s2) == 0 ? true : false );}),
chunks.end() );
Перед выполнением вышеуказанного:
1 l:1
1+ l:2
1+1 l:3
1+1= l:4
+ l:1
+1 l:2
+1= l:3
1 l:1
1= l:2
= l:1
После выполнения вышеуказанного кода:
1 l:1
1+ l:2
1+1 l:3
1+1= l:4
+ l:1
+1 l:2
+1= l:3
1 l:1
1= l:2
= l:1
Я пытался без предиката (при условии, что идентичные строки std :: strings будут удалены). По какой-то причине «те» идентифицированы как идентичные? Я посмотрел на их длину (предполагая, что пробел застрял как префикс или постфикс), но они имеют одинаковую длину.
Я что-то пропустил ?
Решение
Вы (вероятно) что-то неправильно понимаете.
std::unique удаляет только смежные дубликаты, поэтому, если вы хотите удалить все дубликаты, необходимо выполнить предварительное условие std::unique сортировать ваш диапазон, используя тот же предикат.
Другие решения
std::unique Предполагается, что неуникальные элементы являются смежными, как если бы (для одного примера) chunks были отсортированы. Это позволяет std::unique иметь O (n) сложность.
Если вы хотите поддерживать определенный порядок в вашем vector и удалите дубликаты, это проблема с O (N2) сложность. Вы можете использовать логику, представленную здесь, чтобы сделать это.
// Create a new vector without the duplicates
std::vector<string> unique_chunks;
for (std::vector<string>::iterator x = chunks.begin(); x != chunks.end();) {
if ( unique_chunks.find(*x) != unique_chunks.end() ) {
unique_chunks.push_back( *x );
}
}
// Make chunks hold this new vector (allowing the old vector to be destroyed)
std::swap( chunks, unique_chunks );
И нет, вам не нужен этот предикат.
Как уже упоминалось в другом ответе, unique удаляет смежные блоки дубликатов, если вам нужно удалить дубликаты и сохранить порядок остальных элементов (порядок первого появления здесь) в O(N log N) время вы можете сделать следующее:
template<typename T>
bool bySecond(const pair<T, int>& a, const pair<T, int>& b) {
return a.second < b.second;
}
template<typename T>
bool firstEqual(const pair<T, int>& a, const pair<T, int>& b) {
return a.first == b.first;
}
template<typename it>
it yourUnique(it begin, it end){
typedef typename std::iterator_traits<it>::value_type value_t;
vector<pair<value_t, int>> v;
for(it c = begin; c != end; ++c){
v.push_back(make_pair(*c, v.size())); // second is start index;
}
sort(v.begin(), v.end()); // sort by value then by index
v.erase(unique(v.begin(), v.end(), firstEqual<value_t>), v.end());
sort(v.begin(), v.end(), bySecond<value_t>); // restore order.
it c = begin;
for(const auto& x: v){
*(c++) = x.first;
}
return it;
}
Возможность иметь собственный предикат не реализована. Это возможно, но одним недостатком является то, что вам придется предоставить less-than функция, а не equality Во-первых, это может быть невозможно в некоторых случаях.
std::unique Алгоритм предполагает, что входной диапазон находится в порядке, и удаляет дубликаты, сравнивая два последовательных значения. Чтобы использовать алгоритм, вам нужно сначала отсортировать входные данные.
detector