Comment fonctionne un vecteur comme clé en interne en C ++?

14

Ce SO répond que la carte STL avec un vecteur pour la clé, le vecteur peut être utilisé comme clé. Donc, lorsque nous utilisons un vecteur comme clé. Comment cela fonctionne-t-il réellement puisque la clé doit être unique, donc lorsque nous insérons un autre vecteur avec les mêmes éléments, la mapvérification du doublon élément par élément ou le nom du vecteur spécifiera-t-il quelque chose? Comme le nom du tableau représente l'adresse de base. Ainsi, un tableau peut être utilisé comme clé puisque l'adresse de base peut être utilisée comme clé dans ce cas, mais quelle est la clé dans le cas d'un vecteur. Comment ça marche en interne.

Parce que lorsque j'imprime le nom du vecteur, j'obtiens une erreur

vector<int> v;
cout<<v; //error
c++ arrays dictionary vector stl Pulkit Bhatnagar
la source
Que voulez-vous dire par imprimer le nom du vecteur?
Bart
has operators == and <comment cela aide-t-il? ma question était de vérifier les éléments en double cartographieront comparer l'élément clé vecteur par élément
Pulkit Bhatnagar
3
@PulkitBhatnagar Mais ... Personne ne vous forcera jamais à utiliser std::vectorcomme clé pour std::map. Vous payez pour ce que vous utilisez . Cela peut être fait, et il existe peut-être des cas d'utilisation pour cela, mais vous pouvez certainement changer la structure de données de votre choix. Les conteneurs STL sont conçus pour être polyvalents et utilisables au maximum de la manière dont les utilisateurs pourraient vouloir les utiliser.
Yksisarvinen
1
@PulkitBhatnagar Voir, par exemple, pourquoi std :: map est-il implémenté comme un arbre rouge-noir? .
Daniel Langr
1
@PulkitBhatnagar Magasins directement. std::mapcopiera la clé et la valeur en elle-même. std::unordered_mappeut stocker le hachage de la clé.
Yksisarvinen

Réponses:

9

Il existe un opérateur surchargé <pour le modèle de classe std :: vector.

template <class T, 
class Allocator>
bool operator< (const vector<T, Allocator>& x, const vector<T, Allocator>& y);

qui est basé sur l'algorithme standard std::lexicographical_compare.

Voici un programme démonstratif.

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v1 = { 1, 2 };
    std::vector<int> v2 = { 1, 2, 3 };
    std::vector<int> v3 = { 2 };

    std::cout << std::boolalpha << ( v1 < v2 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v1 ), std::end( v1 ),
                                               std::begin( v2 ), std::end( v2 ) )
             << '\n';                                              

    std::cout << std::boolalpha << ( v1 < v3 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v1 ), std::end( v1 ),
                                               std::begin( v3 ), std::end( v3 ) )
             << '\n';                                              

    std::cout << std::boolalpha << ( v2 < v3 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v2 ), std::end( v2 ),
                                               std::begin( v3 ), std::end( v3 ) )
             << '\n';                                              

    return 0;
}

Sa sortie est

true
true
true
true
true
true

Ainsi, la classe peut être utilisée comme clé dans la carte.

Par défaut, la carte du modèle de classe utilise l'objet fonction std :: less qui à son tour utilise l'opérateur <

template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair<const Key, T>>>
class map 
{
    //...
};

Cependant, il n'y a pas d'opérateur surchargé << pour le modèle de classe std :: vector.

Vlad de Moscou
la source
5
Je vois vos réponses récemment dans presque toutes les questions C ++ sur SO, je ne sais pas si dans toute ma vie je serai jamais capable de réaliser ce que vous avez mais je ferai de mon mieux. Merci pour la réponse
Pulkit Bhatnagar
8

Le nom d'un objet et le contenu de cet objet sont toujours des choses sans rapport.

operator ==for std::vectorcomparera d'abord la longueur des vecteurs, puis chacun de ses éléments en utilisant operator ==également.

operator <compare les éléments du vecteur lexicographiquement, c'est-à-dire qu'il renvoie x[i] < y[i]le premier élément non égal dans les vecteurs xet y.

Ce sont les exigences std::mapa pour un type utilisé comme Key. Puisqu'il std::vectorsatisfait les deux, il peut être utilisé par as Key. Notez que le type géré par vector doit également avoir ces opérateurs surchargés pour que cela fonctionne (car il std::vectordépend de ces opérateurs pour implémenter ses propres opérateurs).

Yksisarvinen
la source