Удалить повторяющиеся записи в векторе C++

Просто хочу удалить дубликаты. Пул - это vector<pair<string, int>>, но я, кажется, каким-то образом пропустил некоторые элементы в начале вектора. Кто-нибудь может проверить логику удаления? Спасибо :)

Pool Master::eliminateDuplicates(Pool generation)
{
    for(int i = 0; i < generation.size(); i++)
    {
        string current = generation.at(i).first;

        for(int j = i; j < generation.size(); j++)
        {
            if(j == i)
            {
                continue;
            }
            else
            {
                string temp = generation.at(j).first;
                if(current.compare(temp) == 0)
                {
                    Pool::iterator iter = generation.begin() + j;
                    generation.erase(iter);
                }
            }
        }
    }

    return generation;
}

c++ vector erase duplicate-removal
person Jarrod Cabalzar    schedule 10.05.2013    source источник
comment
Вы не возражаете, если это будет отсортировано?   -  person chris    schedule 10.05.2013
comment
Более простой (и, вероятно, более быстрый способ, чем способ O(n^2), который используется в настоящее время) сделать это — добавить все элементы в std::set, а затем обратно в std::vector.   -  person Yuushi    schedule 10.05.2013
comment
Кроме того, я полагаю, вы имеете в виду, что Pool является vector<pair<string, int>>?   -  person Yuushi    schedule 10.05.2013
comment
Я думал, что наборы будут работать только на основе целочисленного типа данных? Я сравниваю дубликаты строк. РЕДАКТИРОВАТЬ да, извините опечатка;)   -  person Jarrod Cabalzar    schedule 10.05.2013
comment
Это утверждение if(j == i){continue;} необходимо? Вы можете просто начать цикл с i+1.   -  person Quazi Marufur Rahman    schedule 10.05.2013
comment
@QuaziMarufurRahman Может привести к ошибке сегментации, если я был последним элементом.   -  person Jarrod Cabalzar    schedule 10.05.2013
comment
std::set работает либо на основе operator<, либо вы можете дать ему функцию сравнения, которую он может использовать. Это был бы довольно бесполезный набор, если бы он работал только с целыми числами!   -  person Yuushi    schedule 10.05.2013
comment
В любом случае вам не нужно использовать set. Вы можете отсортировать свой вектор и использовать std::unque. Это будет O(Nlog(N))   -  person juanchopanza    schedule 10.05.2013

Ответы (2)


arrow_upward
4
arrow_downward

Это очень распространенная проблема.

Потому что после того, как вы удалите элемент, указанная позиция j, пропустит один элемент из-за j++ в цикле for. самое простое решение проблемы на основе вашего кода — добавить j-- после generate.erase(iter):

  generation.erase(iter);
  j--;
person Gisway    schedule 10.05.2013
comment
Я потратил на это час, лол - person sdev; 20.07.2021

arrow_upward
20
arrow_downward

Если вы не возражаете против сортировки вектора, вы можете использовать std::unique. Это будет O(Nlog(N))

#include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); 
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    for (const auto& i : v)
      std::cout << i << " ";
    std::cout << "\n";
}
person juanchopanza    schedule 10.05.2013
comment
+1 Кто-то должен написать запись в вики / FAQ для всех случаев использования векторов хлеба с маслом. - person TemplateRex; 10.05.2013
comment
@rhalbersma, SO должен вести список наиболее часто задаваемых вопросов по популярным темам, например, 10 лучших вопросов по C++ или что-то в этом роде. Это было бы удобно. :D - person Jarrod Cabalzar; 10.05.2013
comment
Интересно, почему во всех ответах об использовании std::unique никто не упоминает, что unique не учитывает последний элемент. - person tomi.lee.jones; 21.12.2013
comment
@tomi.lee.jones Я не совсем понимаю, что вы имеете в виду. Поведение std::unique кажется мне вполне интуитивным. - person juanchopanza; 21.12.2013
comment
@juan из документации удаляет все последовательные повторяющиеся элементы из диапазона [first, last), поэтому (1,2,3,1) будет (1,2,3,1). Как это интуитивно? Я знаю, почему диапазон открывается справа и почему так и должно быть, но если вы не уверены, что в последней позиции нет двойника, то уникальность кажется бесполезной. - person tomi.lee.jones; 21.12.2013
comment
@tomi.lee.jones Поскольку все стандартные алгоритмы библиотеки работают с открытыми диапазонами, и обычно мы передаем начало, конец, который таким образом открыт. - person juanchopanza; 21.12.2013
comment
Если собираетесь сортировать, то почему бы и нет std::sort? - person ; 18.05.2014