Nos mapas STL, é melhor usar map :: insert do que []?

201

Há um tempo, tive uma discussão com um colega sobre como inserir valores nos mapas STL . Eu preferi map[key] = value; porque parece natural e é claro de ler, enquanto ele preferia map.insert(std::make_pair(key, value))

Eu apenas perguntei a ele e nenhum de nós pode se lembrar do motivo pelo qual o insert é melhor, mas tenho certeza de que não era apenas uma preferência de estilo, mas havia um motivo técnico, como eficiência. A referência da SGI STL diz simplesmente "Estritamente falando, essa função de membro é desnecessária: existe apenas por conveniência".

Alguém pode me dizer esse motivo, ou estou apenas sonhando que existe um?

danio
fonte
2
Obrigado por todas as ótimas respostas - elas foram realmente úteis. Esta é uma ótima demonstração do estouro de pilha no seu melhor. Fiquei impressionado com a resposta correta: netjeff é mais explícito sobre os diferentes comportamentos, Greg Rogers mencionou problemas de desempenho. Gostaria de poder assinalar os dois.
Danio
6
Na verdade, com C ++ 11, provavelmente você está melhor fora de usar mapa :: emplace que evita a dupla construção
einpoklum
@einpoklum: Na verdade, Scott Meyers sugere o contrário em sua palestra "A busca em evolução por C ++ eficaz".
21415 Thomas Eding
3
@einpoklum: Esse é o caso quando se instala na memória recém-construída. Porém, devido a alguns requisitos de padrões para o mapa, há razões técnicas pelas quais o local pode ser mais lento que o interior. A palestra está disponível gratuitamente no youtube, como o link youtube.com/watch?v=smqT9Io_bKo @ ~ 38-40 minutos. Para uma ligação SO, aqui está stackoverflow.com/questions/26446352/...
Thomas Eding
1
Na verdade, eu argumentaria com parte do que Meyers apresentou, mas isso está além do escopo deste tópico de comentários e, de qualquer forma, acho que tenho que retratar meu comentário anterior.
einpoklum

Respostas:

240

Quando você escreve

map[key] = value;

não há como saber se você substituiu o valuefor keyou se criou um novo keycom value.

map::insert() criará apenas:

using std::cout; using std::endl;
typedef std::map<int, std::string> MyMap;
MyMap map;
// ...
std::pair<MyMap::iterator, bool> res = map.insert(MyMap::value_type(key,value));
if ( ! res.second ) {
    cout << "key " <<  key << " already exists "
         << " with value " << (res.first)->second << endl;
} else {
    cout << "created key " << key << " with value " << value << endl;
}

Para a maioria dos meus aplicativos, geralmente não me importo se estou criando ou substituindo, então uso o mais fácil de ler map[key] = value.

netjeff
fonte
16
Deve-se notar que map :: insert nunca substitui valores. E, no caso geral, eu diria que é melhor usar, em (res.first)->secondvez de valuetambém no segundo caso.
dalle
1
Atualizei para ficar mais claro que map :: insert nunca substitui. Deixei o arquivo elseporque acho que o uso valueé mais claro do que o iterador. Somente se o tipo de valor tivesse um copiador incomum ou op == seria diferente, e esse tipo causaria outros problemas ao usar contêineres STL como map.
NetJack
1
map.insert(std::make_pair(key,value))deveria ser map.insert(MyMap::value_type(key,value)). O tipo retornado de make_pairnão coincide com o tipo de tomadas por inserte a solução atual exige uma conversão
David Rodríguez - dribeas
1
existe uma maneira de saber se você inseriu ou acabou de atribuir operator[], basta comparar o tamanho antes e depois. Imho poder chamar map::operator[]apenas tipos construtivos padrão é muito mais importante.
Idclev 463035818
@ DavidRodríguez-dribeas: Boa sugestão, atualizei o código na minha resposta.
Netjef 13/06/19
53

Os dois têm semântica diferente quando se trata da chave já existente no mapa. Portanto, eles não são diretamente comparáveis.

Mas a versão do operador [] requer a construção padrão do valor e a atribuição, portanto, se isso for mais caro, copie a construção, então será mais caro. Às vezes, a construção padrão não faz sentido e, portanto, seria impossível usar a versão do operador [].

Greg Rogers
fonte
1
O make_pair pode exigir um construtor de cópias - isso seria pior que o padrão. +1 de qualquer maneira.
1
O principal é, como você disse, que eles têm semânticas diferentes. Portanto, nenhum é melhor que o outro, basta usar o que faz o que você precisa.
jalf
Por que o construtor de cópias seria pior que o construtor padrão seguido pela atribuição? Se for, a pessoa que escreveu a classe perdeu alguma coisa, porque qualquer operador = faz, deveria ter feito o mesmo no construtor de cópias.
21608 Steve Jessop
1
Às vezes, a construção padrão é tão cara quanto a própria atribuição. Naturalmente, a atribuição e a construção de cópias serão equivalentes.
Greg Rogers
@Arkadiy Em uma construção otimizada, o compilador geralmente remove muitas chamadas desnecessárias de construtores de cópias.
antred 17/07/2015
35

Outra coisa a se notar std::map:

myMap[nonExistingKey];criará uma nova entrada no mapa, digitada para nonExistingKeyinicializada com um valor padrão.

Isso me assustou muito na primeira vez que o vi (enquanto batia minha cabeça contra um inseto legado). Não teria esperado isso. Para mim, isso parece uma operação get, e eu não esperava o "efeito colateral". Prefere map.find()ao sair do seu mapa.

Hawkeye Parker
fonte
3
Essa é uma visão decente, embora os mapas de hash sejam bastante universais para esse formato. Pode ser um desses "esquisitices que ninguém pensa que é estranho" apenas por causa de quão disseminado eles usam as mesmas convenções
Stephen J
19

Se o desempenho do construtor padrão não for um problema, por favor, pelo amor de Deus, vá com a versão mais legível.

:)

Torlack
fonte
5
Segundo! Tenho que marcar isso. Muitas pessoas trocam obtusidade por acelerações de nanossegundos. Tende piedade de nós, pobres almas que devem manter tais atrocidades!
28468 Mr.Ree
6
Como Greg Rogers escreveu: "Os dois têm semânticas diferentes quando se trata da chave já existente no mapa. Portanto, elas não são diretamente comparáveis".
Dalle
Esta é uma pergunta e resposta antigas. Mas "versão mais legível" é uma razão estúpida. Porque o que é mais legível depende da pessoa.
precisa
14

insert é melhor do ponto de exceção de segurança.

A expressão map[key] = valueé na verdade duas operações:

  1. map[key] - criando um elemento do mapa com valor padrão.
  2. = value - copiando o valor para esse elemento.

Uma exceção pode acontecer na segunda etapa. Como resultado, a operação será realizada apenas parcialmente (um novo elemento foi adicionado ao mapa, mas esse elemento não foi inicializado com value). A situação em que uma operação não está concluída, mas o estado do sistema é modificado, é chamada de operação com "efeito colateral".

insertA operação oferece uma garantia forte, significa que não possui efeitos colaterais ( https://en.wikipedia.org/wiki/Exception_safety ). inserté completamente feito ou deixa o mapa em estado não modificado.

http://www.cplusplus.com/reference/map/map/insert/ :

Se um único elemento for inserido, não haverá alterações no contêiner em caso de exceção (garantia forte).

anton_rh
fonte
1
mais importante, a inserção não exige que o valor seja construtível por padrão.
UmNyobe
13

Se o seu aplicativo for crítico quanto à velocidade, aconselho o uso do operador [], pois ele cria um total de 3 cópias do objeto original, das quais 2 são objetos temporários e, mais cedo ou mais tarde, serão destruídos como.

Mas no insert (), 4 cópias do objeto original são criadas, das quais 3 são objetos temporários (não necessariamente "temporários") e são destruídas.

O que significa tempo extra para: 1. Uma alocação de memória de objetos 2. Uma chamada de construtor extra 3. Uma chamada de destruidor extra 4. Uma desalocação de memória de objetos

Se seus objetos são grandes, os construtores são típicos, os destruidores liberam muitos recursos, os pontos acima contam ainda mais. Quanto à legibilidade, acho que ambas são justas o suficiente.

A mesma pergunta veio à minha mente, mas não sobre legibilidade, mas velocidade. Aqui está um exemplo de código através do qual eu vim a conhecer o ponto que mencionei.

class Sample
{
    static int _noOfObjects;

    int _objectNo;
public:
    Sample() :
        _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside default constructor of object "<<_objectNo<<std::endl;
    }

    Sample( const Sample& sample) :
    _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside copy constructor of object "<<_objectNo<<std::endl;
    }

    ~Sample()
    {
        std::cout<<"Destroying object "<<_objectNo<<std::endl;
    }
};
int Sample::_noOfObjects = 0;


int main(int argc, char* argv[])
{
    Sample sample;
    std::map<int,Sample> map;

    map.insert( std::make_pair<int,Sample>( 1, sample) );
    //map[1] = sample;
    return 0;
}

Saída quando insert () é usado Saída quando o operador [] é usado

Rampal Chaudhary
fonte
4
Agora execute esse teste novamente com as otimizações completas ativadas.
antred 17/07/2015
2
Além disso, considere o que o operador [] realmente faz. Ele primeiro pesquisa no mapa uma entrada que corresponda à chave especificada. Se encontrar um, substituirá o valor dessa entrada pelo especificado. Caso contrário, ele insere uma nova entrada com a chave e o valor especificados. Quanto maior o seu mapa, mais tempo será necessário para que o operador [] pesquise no mapa. Em algum momento, isso mais do que compensará uma chamada extra de cópia ou cópia (se isso ainda permanecer no programa final após o compilador ter feito sua mágica de otimização).
antred 17/07/2015
1
@ antred, inserttem que fazer a mesma pesquisa, então não há diferença disso [](porque as chaves do mapa são únicas).
Sz.
Boa ilustração do que está acontecendo com as impressões - mas o que esses dois bits de código estão realmente fazendo? Por que são necessárias 3 cópias do objeto original?
precisa saber é o seguinte
1. deve implementar o operador de atribuição, ou você obterá números errados no destruidor 2. use std :: move ao construir par para evitar excesso de construção de cópia "map.insert (std :: make_pair <int, Sample> (1, std: : mover (amostra))); "
Fl0 07/12/16
10

Agora, em c ++ 11, acho que a melhor maneira de inserir um par em um mapa STL é:

typedef std::map<int, std::string> MyMap;
MyMap map;

auto& result = map.emplace(3,"Hello");

O resultado será um par com:

  • Primeiro elemento (result.first), aponta para o par inserido ou aponta para o par com essa chave, se a chave já existir.

  • Segundo elemento (result.second), true se a inserção estava correta ou falsa, algo deu errado.

PS: Se você não se interessa pelo pedido, pode usar std :: unordered_map;)

Obrigado!

GutiMac
fonte
9

Uma dica com map :: insert () é que ele não substituirá um valor se a chave já existir no mapa. Eu vi o código C ++ escrito por programadores Java, onde eles esperavam que insert () se comportasse da mesma maneira que Map.put () em Java, onde os valores são substituídos.

Anthony Cramp
fonte
2

Uma observação é que você também pode usar o Boost.Assign :

using namespace std;
using namespace boost::assign; // bring 'map_list_of()' into scope

void something()
{
    map<int,int> my_map = map_list_of(1,2)(2,3)(3,4)(4,5)(5,6);
}
rlbond
fonte
1

Aqui está outro exemplo, mostrando que operator[] substitui o valor da chave, se ela existir, mas .insert não substitui o valor, se ela existir.

void mapTest()
{
  map<int,float> m;


  for( int i = 0 ; i  <=  2 ; i++ )
  {
    pair<map<int,float>::iterator,bool> result = m.insert( make_pair( 5, (float)i ) ) ;

    if( result.second )
      printf( "%d=>value %f successfully inserted as brand new value\n", result.first->first, result.first->second ) ;
    else
      printf( "! The map already contained %d=>value %f, nothing changed\n", result.first->first, result.first->second ) ;
  }

  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

  /// now watch this.. 
  m[5]=900.f ; //using operator[] OVERWRITES map values
  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

}
bobobobo
fonte
1

Este é um caso bastante restrito, mas, a julgar pelos comentários que recebi, acho que vale a pena notar.

Eu já vi pessoas no passado usarem mapas na forma de

map< const key, const val> Map;

para evitar casos de substituição acidental de valores, mas continue escrevendo outros bits de código:

const_cast< T >Map[]=val;

A razão de fazer isso, pelo que me lembro, era porque eles tinham certeza de que nesses certos bits de código não estavam substituindo os valores do mapa; portanto, seguindo em frente com o método mais 'legível' [].

Na verdade, nunca tive nenhum problema direto com o código que foi escrito por essas pessoas, mas sinto até hoje que riscos - ainda que pequenos - não devem ser tomados quando podem ser facilmente evitados.

Nos casos em que você estiver lidando com valores de mapa que absolutamente não devem ser substituídos, use insert. Não faça exceções apenas para facilitar a leitura.

dk123
fonte
Várias pessoas diferentes escreveram isso? Certamente use insert(não input), pois isso const_castfará com que qualquer valor anterior seja substituído, o que é muito não-constante. Ou não marque o tipo de valor como const. (Esse tipo de coisa é geralmente o resultado final const_cast, por isso é quase sempre uma bandeira vermelha indicando um erro em outro lugar.)
Potatoswatter
@Potatoswatter Você está certo. Só estou vendo que const_cast [] é usado com valores de mapa const por algumas pessoas quando elas têm certeza de que não estarão substituindo um valor antigo em certos bits de código; já que [] em si é mais legível. Como mencionei na parte final da minha resposta, recomendo usar insertnos casos em que você deseja impedir que valores sejam substituídos. (Apenas mudou o inputque insert- graças)
dk123
@Potatoswatter Se bem me lembro, as principais razões pelas quais as pessoas parecem estar usando const_cast<T>(map[key])eram 1. [] é mais legível, 2. estão confiantes em certos bits de código que não estarão substituindo valores e 3. não quer outros bits de código desconhecido que sobrescrevem seus valores - daí o const value.
dk123
2
Eu nunca ouvi falar disso; onde você viu isso? Escrever const_castparece mais do que negar a "legibilidade" extra de [], e esse tipo de confiança é quase suficiente para disparar um desenvolvedor. Condições de tempo de execução complicadas são resolvidas por projetos à prova de balas, não por sentimentos.
Potatoswatter
@Potatoswatter Lembro que foi durante um dos meus trabalhos anteriores no desenvolvimento de jogos educativos. Eu nunca consegui que as pessoas que escreviam o código mudassem seus hábitos. Você está absolutamente certo e eu concordo plenamente com você. De seus comentários, decidi que isso provavelmente vale mais a pena notar do que a minha resposta original e, portanto, atualizei-a para refletir isso. Obrigado!
dk123
1

O fato de a insert()função std :: map não sobrescrever o valor associado à chave nos permite escrever o código de enumeração de objetos assim:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    dict.insert(make_pair(word, dict.size()));
}

É um problema bastante comum quando precisamos mapear diferentes objetos não exclusivos para alguns IDs no intervalo 0..N. Esses IDs podem ser usados ​​posteriormente, por exemplo, em algoritmos de gráficos. Alternativa com operator[]pareceria menos legível na minha opinião:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    size_t sz = dict.size();
    if (!dict.count(word))
        dict[word] = sz; 
} 
mecatrônico
fonte