2017-10-10 4 views

Répondre

0

Ils sont fondamentalement différents. Bien que vous puissiez faire les deux g2[0] et g1[0], le comportement est très différent. Supposons qu'il n'y ait rien à l'index 0, alors std::map construira par défaut un nouveau type_valeur, dans ce cas un vecteur, et renverra une référence, tandis que std::vector aura un comportement indéfini, mais généralement segmentera ou renverra des ordures.

Ils sont également complètement différents en termes de disposition de la mémoire. Alors que std::map est soutenu par un arbre rouge-noir, std::vector est contigu en mémoire. Ainsi, l'insertion dans la carte entraînera toujours une allocation dynamique quelque part en mémoire, alors que le vecteur serait redimensionné au cas où sa capacité actuelle serait dépassée. Notez cependant qu'un vecteur de vecteurs n'est pas contigu en mémoire. Le premier vecteur, qui est lui-même contigu en mémoire est composée de vecteurs qui ressemblent à peu près comme ceci en termes de données:

struct vector 
{ 
    T* data; 
    size_t capacity; 
    size_t size; 
}; 

Si chacun des vecteurs possède son allocation dynamique de mémoire à data. L'avantage de la carte est qu'elle n'a pas besoin d'être densément peuplée, c'est-à-dire que vous pouvez avoir quelque chose à l'index 0 et 12902 sans tous les éléments intermédiaires, et elle est triée. Si vous n'avez pas besoin de la propriété triée et que vous pouvez utiliser C++ 11, considérez std::unordered_map. Le vecteur est toujours densément peuplé, c'est-à-dire à la taille 10000, les éléments 0 à 9999 existent.

+0

Notez que RB-tree n'est pas spécifié par la norme. Cela dépend de la mise en œuvre, même si c'est le cas la plupart du temps. – Caduchon

+0

true, mais connaissez-vous une implémentation qui n'utilise pas d'arborescence rb? IIRC la norme exige typiquement seulement certains temps d'exécution asymptotiques pour certaines opérations, mais dans la pratique la stratégie d'allocation de mémoire a un impact beaucoup plus grand que la différence d'exécution asymptotique dans la plupart des cas. – midor

+0

Non, mais il y a tellement de compilateurs étranges, je ne serais pas surpris si certains d'entre eux implémentent d'autres algorithmes (comme Casio ou Texas Instrument, utilisant déjà des octets de 16 bits, par exemple). – Caduchon

1

La similitude est la façon dont vous accédez aux données, il peut être la même syntaxe:

std::cout << g1[3][2] << std::endl; 
std::cout << g2[3][2] << std::endl; 

La principale différence est la suivante: la carte de vecteur ne doit pas contenir tous les indices. Ensuite, vous pouvez avoir, à titre d'exemple, seuls 3 vecteurs dans votre carte accessible avec les touches de 17 ', « 1234 » et 13579:

g2[17].resize(10); 
g2[1234].resize(5); 
g2[13579].resize(100); 

Si vous voulez la même syntaxe avec un vecteur de vecteurs, vous devez avoir au moins 13579 vecteurs (y compris 13576 vecteur vide) dans votre vecteur principal. Mais cela va utiliser beaucoup d'espace inutilisé dans la mémoire.

De plus, dans votre carte, vous pouvez également accéder à vos vecteurs avec des clés négatifs (ce qui est impossible dans le vecteur de vecteurs):

g2[-10].resize(10); 

Après cette différence évidemment élevé, le stockage des données est différent . Le vecteur alloue la mémoire contiguë, tandis que la carte est stockée en tant qu'arbre. La complexité de l'accès dans le vecteur est O(1), tandis que O(log(n)) dans la carte. Je vous invite à apprendre quelques tutoriels sur les conteneurs en C++ pour comprendre toutes les différences et la façon habituelle de les utiliser.

0

Avec l'exemple, vous pouvez comprendre la différence. Disons que le vector<int> stocke les ID uniques des personnes, et map stocke le code PIN respectif comme clé.

map< int , vector<int> > listOfPeopleAtRespectivePinCode; 
vector< vector<int> > bunchOfGroupsOfPeople; 

De toute évidence, map sont capables d'associer clé et la valeur (ici une liste de valeurs), tandis que vector peut stocker efficacement un tas de données.