Como um vetor como chave funciona internamente em C ++?

14

Este SO responde que o Mapa STL com um Vetor para a Chave pode ser usado como chave. Então, quando usamos um vetor como chave. Como isso realmente funciona, uma vez que a chave precisa ser única e, quando inserirmos outro vetor com os mesmos elementos, a mapverificação de elemento duplicado por elemento ou o nome do vetor especificarão alguma coisa? Como o nome da matriz, representa o endereço base. Portanto, uma matriz pode ser usada como uma chave, pois o endereço base pode ser usado como uma chave nesse caso, mas qual é a chave no caso de um vetor. Como isso funciona internamente?

Porque quando imprimo o nome do vetor, recebo um erro

vector<int> v;
cout<<v; //error
c++ arrays dictionary vector stl Pulkit Bhatnagar
fonte
O que você quer dizer com imprimir o nome do vetor?
Bart
has operators == and <como isso ajuda? minha pergunta era para verificar elementos duplicados irá mapear comparar o elemento chave do vetor por elemento
Pulkit Bhatnagar
3
@PulkitBhatnagar Mas ... Ninguém nunca irá forçá-lo a usar std::vectorcomo chave para std::map. Você paga pelo que usa . Isso pode ser feito e talvez haja alguns casos de uso para isso, mas certamente você pode alterar sua estrutura de dados de escolha. Os contêineres da STL foram projetados para serem maximamente versáteis e utilizáveis ​​da maneira que o usuário desejar.
Yksisarvinen
11
@PulkitBhatnagar Veja, por exemplo, por que o std :: map é implementado como uma árvore vermelho-preta? .
Daniel Langr 17/02
11
@PulkitBhatnagar Stores diretamente. std::mapcopiará a chave e o valor em si. std::unordered_mappode armazenar o hash da chave.
Yksisarvinen

Respostas:

9

Há um operador sobrecarregado <para o modelo de classe std :: vector.

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

isso é baseado no algoritmo padrão std::lexicographical_compare.

Aqui está um programa demonstrativo.

#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;
}

Sua saída é

true
true
true
true
true
true

Portanto, a classe pode ser usada como uma chave no mapa.

Por padrão, o mapa do modelo de classe usa o objeto de função std :: less que, por sua vez, usa o operador <

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

No entanto, não há operador sobrecarregado << para o modelo de classe std :: vector.

Vlad de Moscou
fonte
5
Vejo suas respostas recentemente em quase todas as perguntas de C ++ sobre SO, não sei se em toda a minha vida vou conseguir o que você tem, mas tentarei o meu melhor. Obrigado pela resposta
Pulkit Bhatnagar
8

O nome de um objeto e o conteúdo desse objeto são sempre coisas não relacionadas.

operator ==pois std::vectorprimeiro comparará o comprimento dos vetores e, em seguida, cada um de seus elementos também será usado operator ==.

operator <compara elementos no vetor lexicograficamente, ou seja, ele retorna x[i] < y[i]para o primeiro elemento não igual em vetores xe y.

Estes são os requisitos std::mappara um tipo usado como Key. Como std::vectorsatisfaz ambos, pode ser usado como Key. Observe que o tipo gerenciado por vetor também deve ter esses operadores sobrecarregados para que isso funcione (porque std::vectorconta com esses operadores para implementar seus próprios operadores).

Yksisarvinen
fonte