Очистка дубликатов объектов в векторе производит бесконечный цикл

Question

У меня есть вектор с именем:

vector<MiniPair> miniPairVector;

Объект MiniPair имеет 2 свойства, 1 - целое число docNumber, другое - строка word

Я пытаюсь удалить дубликаты в этом векторе, что означает, что если docNumber и слово существуют в другом объекте внутри вектора, удалите дубликаты

Это то, что я пробовал, но он производит бесконечный цикл:

for (int i = 0; i < miniPairVector.size(); i++) {

    for (int k = i + 1; k < miniPairVector.size(); k++) {

        if (miniPairVector[i].getDocNumber() == miniPairVector[k].getDocNumber() && miniPairVector[i].getWord() == miniPairVector[k].getWord()) {
            cout << "i am erasing" << endl;
            miniPairVector.erase(miniPairVector.begin() + k);

        }

    }

}

это класс мини-пары:

#pragma once
// classes example
#ifndef MINIPAIR_H
#define MINIPAIR_H
#include <iostream>
using namespace std;

class MiniPair {
    friend bool operator<(MiniPair const &a, MiniPair const &b) {

        return a.docNumber < b.docNumber || a.docNumber == b.docNumber && a.word < b.word;
    }
    friend bool operator==(MiniPair const &a, MiniPair const &b) {

        return a.docNumber == b.docNumber && a.word == b.word;
    }
private:
    string word;
    int docNumber;

public:
    MiniPair();
    MiniPair(string word, int docNumber);
    string getWord();
    int getDocNumber();

};
#endif

Answer 1

C ++ 98 решение:

#include <algorithm>
#include <string>
#include <vector>

struct MiniPair {
    int docNumber;
    std::string word;
    friend bool operator<(MiniPair const &a, MiniPair const &b) {
        return a.docNumber < b.docNumber || a.docNumber == b.docNumber && a.word < b.word;
    }
    friend bool operator==(MiniPair const &a, MiniPair const &b) {
        return a.docNumber == b.docNumber && a.word == b.word;
    }
};

int main() {
    std::vector<MiniPair> miniPairVector;
    // fill miniPairVector with data
    std::sort(miniPairVector.begin(), miniPairVector.end());
    miniPairVector.erase(std::unique(miniPairVector.begin(), miniPairVector.end()), miniPairVector.end());
}

Answer 2

Я предполагаю, что вы делаете это для класса.

Во-первых, хотя это может не относиться к задаче, которую вы сейчас решаете написать из-за ограничений, наложенных классом, это плохой способ реализовать это. При правильной реализации количество сравнений будет примерно равно miniPairVector.size() * miniPairVector.size(). Это много сравнений и гораздо больше, чем нужно на самом деле.

Если бы я пытался сделать это в неигровой (или не присваиваемой) программе, я бы использовал раздел <algorithm> стандартной библиотеки. Я бы использовал ::std::sort, а затем ::std::unique.

Вот как бы я это сделал, используя эти два:

#include <algorithm>

void remove_dupes(::std::vector<MiniPair> &minipair_vec)
{
    ::std::sort(minipair_vec.begin(), minipair_vec.end(),
                [](MiniPair const &a, MiniPair const &b) -> bool {
                    return (a.getDocNumber() < b.getDocNumber())
                           || ((a.getDocNumber() == b.getDocNumber())
                               && (a.getWord() < b.getWord())));
               }); // End lambda and sort.
     auto newend = ::std::unique(minipair_vec.begin(), minipair_vec.end(),
                                [](MiniPair const &a, MiniPair const &b) -> bool {
                                   return a.getDocNumber() == b.getDocNumber()
                                          && a.getWord() == b.getWord();
                                }); // End lambda and unique.
     minipair_vec.resize(newend - minipair_vec.begin());
}

Я проверил его, поэтому он должен работать нормально.

Общий урок состоит в том, что, если вы обнаружите, что зацикливаетесь, задайте следующие вопросы:

• Индексирую ли я в линейную структуру данных? Если да, то почему я использую индексы вместо итераторов?
• Есть ли алгоритм, который уже делает то, что мне нужно, или пара алгоритмов может быть легко составлена, чтобы делать то, что мне нужно?

Код, который я представил, должен быть запущен за время, пропорциональное minipair_vec.size() * ::std::log2(minipair_vec.size()). Код, который вы написали, будет выполняться за время, пропорциональное minipair_vec.size() * minipair_vec.size() (как только вы его запустите), что намного больше для большого списка.