Avant de commencer avec le problème, je veux faire une note. Je sais que cela a été publié et j'ai déjà lu des articles qui contiennent presque le même problème que le mien. Je m'en excuse, mais je n'ai pas compris exactement quoi faire.

Alors ... j'ai cette structure

struct Url
{
    string host;
    string path;
    string content;
    bool visited;
};

Dans ma fonction main(), je crée un vector<Url>. Jusqu'à présent, j'ai rempli le vector avec les informations dont j'ai besoin.

Les autres questions que j'ai lues ici disent que je dois d'abord sort le vector<Url> pour supprimer les doublons. La seule chose que je veux faire maintenant est de supprimer les Url s avec une valeur égale Url.path du vecteur.

J'apprécierai toute aide à ce sujet. Merci d'avance!

-2
Georgi Georgiev 31 déc. 2015 à 13:34

2 réponses

Meilleure réponse

Nous avons d'abord besoin d'une fonction pour comparer les URL.

bool compare_url (const Url& u, const Url& v) {
    return !(u.path.compare(v.path));
}

Désormais, pour supprimer les doublons de vector, nous pouvons utiliser les fonctions de la bibliothèque de modèles algorithm: sort et unique. Passez le pointeur de fonction à notre fonction de comparaison compare_url en tant que paramètre à sort. Dans le vecteur trié résultant, nous pouvons utiliser unique pour "supprimer" les doublons consécutifs. Remarque unique ne supprime pas vraiment les éléments en double (et donc la taille du vecteur reste la même), la suppression se fait plutôt en remplaçant les éléments en double par l'élément suivant qui n'est pas un doublon, et en signalant la nouvelle taille du portée raccourcie en renvoyant un itérateur à l'élément qui doit être considéré comme son nouvel élément past-the-end [Référence]. Par conséquent, nous appelons vector::erase pour supprimer les doublons.

void remove_dup_vectors (vector <Url>& vu) {
    sort(vu.begin(), vu.end(), &compare_url);
    vector<Url>::iterator newEnd = unique(vu.begin(),vu.end(), &compare_url);
    vu.erase(newEnd, vu.end());
}

La complexité de cette fonction est O (n lg n) (sort) + O (n) (unique).

Une deuxième solution, plus rapide, consiste à utiliser le conteneur unordered_set qui stocke des objets uniques. Les opérations courantes d'insertion, de recherche et de suppression ont une complexité en temps constant dans le cas moyen. C'est parce que chaque clé est hachée. Notez également que les éléments ne sont pas triés contrairement à set.

Semblable au cas précédent, une fonction de comparaison est à définir, mais ici l'opération est equal to puisque chaque clé est hachée.

bool operator==(const Url& A, const Url& B) {
    return A.path == B.path;
}

En outre, une fonction de hachage doit être définie. Les fonctions de hachage pour les opérations courantes sont déjà définies dans l'en-tête functional. Nous utilisons cela ici.

namespace std
{
    template<> struct hash<Url> {
        size_t operator()(const Url &u) const{
            return hash<string>()(u.path);
        }
    };
}

Avec ces derniers en place, une variable unordered_set<Url> us; peut être définie et utilisée, avec la garantie de l'absence de doublons et d'un accès plus rapide.

-1
Erobrere 1 janv. 2016 à 19:49

Je suppose que vous voulez savoir comment trier votre structure. Vous pouvez donner un opérateur inférieur à ou un foncteur qui peut ordonner les URL. Un exemple de l'opérateur serait:

bool operator<(const Url &l, consr Url &r){
   return tie(l.path, l.host, l.content. l.visited)<tie(r.path, r.host, r.content, r.visited);
}

Vous pouvez ensuite trier le vecteur en appelant std::sort.

Référence:

  1. Moins que comparabale

  2. cravate

0
bashrc 31 déc. 2015 à 10:41