English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Map é um contêiner associativo da STL, que oferece capacidade de processamento de dados um para um (o primeiro pode ser chamado de chave, cada chave pode aparecer apenas uma vez no map, o segundo pode ser chamado o valor da chave), devido a essa característica, ele pode fornecer um caminho rápido na programação quando lidamos com dados um para um. Aqui vamos falar sobre a organização dos dados internos do map, o map interna constrói uma árvore rubro-negra (um tipo de árvore binária de busca balanceada não estritamente), essa árvore tem a função de ordenar automaticamente os dados, então todos os dados internos do map estão ordenados, vamos ver os benefícios do ordenamento mais tarde.
Aqui está um exemplo de que é um mapeamento de dados um para um. Por exemplo, em uma classe, cada número de matrícula de um aluno e seu nome existem em um mapeamento um para um, esse modelo pode ser descrito facilmente com map, obviamente, o número de matrícula é descrito por int, o nome é descrito por uma string (neste artigo, não usamos char *para descrever strings, em vez de usar STL::string para descrever), aqui está o código de descrição do map:
Map<int, string> mapStudent;
1. Construtores do map
O map oferece6os construtores, que envolvem alocação de memória, vamos passar, abaixo vamos conhecê-los alguns métodos de construção do map, aqui o que vamos dizer é que, geralmente usamos o seguinte método para construir um map:
Map<int, string> mapStudent;
2Inserção de dados
Após a construção do contêiner map, podemos inserir dados nele. Aqui vamos discutir três métodos de inserção de dados:
Primeiro:Aqui está um exemplo de como inserir dados do tipo pair usando a função insert (os seguintes códigos foram escritos à mão e devem compilar corretamente em VC e GCC, você pode executá-los para ver o efeito, em VC, por favor, adicione esta sentença para bloquear4786Aviso: #pragma warning (disable:4786) )
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
iterator map<int, string>::iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first << " " << iter->second << end;
}
}
Segundo:Aqui está um exemplo de como inserir dados do tipo value_type usando a função insert.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(map<int, string>::value_type (1, “student_one”));
mapStudent.insert(map<int, string>::value_type (2, “student_two”));
mapStudent.insert(map<int, string>::value_type (3, “student_three”));
iterator map<int, string>::iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first << " " << iter->second << end;
}
}
Terceiro:Aqui está um exemplo de como inserir dados usando o método de array.
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent[1] = “student_one”;
mapStudent[2] = "student_two";
mapStudent[3] = “student_three”;
iterator map<int, string>::iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first << " " << iter->second << end;
}
}
Embora essas três formas possam todas inserir dados, elas têm diferenças. Claro, a primeira e a segunda são idênticas em efeito, usando a função insert para inserir dados, envolve o conceito de unicidade do conjunto, ou seja, quando o map tiver essa chave, a operação insert não pode inserir dados. Mas usando o método de array, isso é diferente, ele pode substituir o valor correspondente a essa chave anteriormente. Vamos explicar isso com um programa.
mapStudent.insert(map<int, string>::value_type (1, “student_one”)); mapStudent.insert(map<int, string>::value_type (1, “student_two”));
Após a execução dessas duas linhas, o map1A chave correspondente tem o valor "student_one", a segunda instrução não entrou em vigor, então isso envolve como podemos verificar se a instrução insert foi bem-sucedida. Podemos usar o pair para obter isso, conforme o programa a seguir
Pair<map<int, string>::iterator, bool> Insert_Pair; Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, “student_one”));
Sabemos se a inserção foi bem-sucedida através da segunda variável do pair. A primeira variável retorna um iterador do map. Se a inserção for bem-sucedida, Insert_Pair.second deve ser true, caso contrário, false.
A seguir, fornecemos o código completo, demonstrando como verificar se a inserção foi bem-sucedida
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
Pair<map<int, string>::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_one”));
If(Insert_Pair.second == true)
{
Cout << "Insert Successfully" << endl;
}
Else
{
Cout << "Insert Failure" << endl;
}
Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_two”));
If(Insert_Pair.second == true)
{
Cout << "Insert Successfully" << endl;
}
Else
{
Cout << "Insert Failure" << endl;
}
iterator map<int, string>::iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first << " " << iter->second << end;
}
}
Vamos usar o seguinte programa para ver o efeito de inserção de dados em cima de dados existentes
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent[1] = “student_one”;
mapStudent[1] = "student_two";
mapStudent[2] = “student_three”;
iterator map<int, string>::iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
Cout<<iter->first << " " << iter->second << end;
}
}
3Tamanho do map
Depois de inserirmos dados no map, como podemos saber quantos dados já foram inseridos? Podemos usar a função size, conforme a seguir:
Int nSize = mapStudent.size();
4Navegação de dados
Também fornecemos três métodos para percorrer o map
Primeira opção: usar iteradores para frente, como no exemplo de programa acima, passaremos por alto
Segunda opção: usar iteradores de inversão, vejamos alguns exemplos. Para entender o efeito, por favor, execute o programa sozinho
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
map<int, string>::reverse_iterator iter;
for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
{
Cout<<iter->first << " " << iter->second << end;
}
}
Terceiro: usar o método de array, explicação do programa如下
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
int nSize = mapStudent.size()
//Aqui há um erro, deve ser for(int nIndex = 1; nIndex <= nSize; nIndex++)
//por rainfish
for(int nIndex = 0; nIndex < nSize; nIndex++)
{
Cout << mapStudent[nIndex] << end;
}
}
5. Busca de dados (inclusive a determinação de se essa chave aparece no map)
Aqui vamos sentir os benefícios de manter o map ordenado ao inserir dados.
Existem muitos métodos para determinar se um dado (chave) aparece no map, embora o título seja a busca de dados, aqui serão穿插大量的map basic usage.
Aqui estão três métodos de busca de dados
Primeiro:Usar a função count para determinar se a chave aparece, sua desvantagem é que não pode localizar a posição dos dados, devido às características do map, a relação de mapeamento um-a-um, determina que o valor de retorno da função count pode ser apenas dois, ou seja, 0, ou1, a situação de aparecimento, claro, é retornar1fim
Segundo:Usar a função find para localizar a posição dos dados, ela retorna um iterador, quando os dados aparecem, ela retorna o iterador da posição dos dados, se não houver dados a serem pesquisados no map, o iterador retornado é igual ao iterador retornado pela função end, explicação do programa
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
iterator map<int, string>::iter;
iter = mapStudent.find(1);
if(iter != mapStudent.end())
{
Cout << "Find, the value is " << iter->second<<endl;
}
Else
{
Cout << "Do not Find" << endl;
}
}
Terceiro:Este método é um pouco burro para determinar se os dados aparecem, mas, pretendo explicar aqui
Uso da função Lower_bound, esta função é usada para retornar o limite inferior da chave a ser pesquisada (é um iterador)
Uso da função Upper_bound, esta função é usada para retornar o limite superior da chave a ser pesquisada (é um iterador)
Por exemplo: o map já inseriu1,2,3,4Se lower_bound(2) retorna2, enquanto upper-bound(2Se)3
A função Equal_range retorna um par, onde o primeiro elemento é o iterador retornado pelo Lower_bound e o segundo elemento é o iterador retornado pelo Upper_bound. Se esses dois iteradores forem iguais, significa que essa chave não existe no map, explicação do programa
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent[1] = “student_one”;
mapStudent[3] = “student_three”;
mapStudent[5] = “student_five”;
iterator map<int, string>::iter;
iter = mapStudent.lower_bound(2);
{
//retorna o limite inferior3o iterador
Cout<<iter->second<<endl;
}
iter = mapStudent.lower_bound(3);
{
//retorna o limite inferior3o iterador
Cout<<iter->second<<endl;
}
iter = mapStudent.upper_bound(2);
{
//retorna o limite superior3o iterador
Cout<<iter->second<<endl;
}
iter = mapStudent.upper_bound(3);
{
//retorna o limite superior5o iterador
Cout<<iter->second<<endl;
}
Pair<map<int, string>::iterator, map<int, string>::iterator> mapPair;
mapPair = mapStudent.equal_range(2);
if(mapPair.first == mapPair.second)
{
cout<<”Do not Find”<<endl;
}
Else
{
Cout<<”Find”<<endl;
}
mapPair = mapStudent.equal_range(3);
if(mapPair.first == mapPair.second)
{
cout<<”Do not Find”<<endl;
}
Else
{
Cout<<”Find”<<endl;
}
}
6. Limpeza de dados e verificação de vazio
Para limpar os dados do map, use a função clear(), para determinar se há dados no map, use a função empty(), que retorna true se for um map vazio
7. Exclusão de dados
Aqui é necessário usar a função erase, que tem três sobrecargas, detalhadas no exemplo a seguir
#include <map>
#include <string>
#include <iostream>
Using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
//se você quiser demonstrar o efeito de saída, escolha uma das seguintes, o efeito que você verá será melhor
//se você quiser excluir1exclua usando o iterador
iterator map<int, string>::iter;
iter = mapStudent.find(1);
mapStudent.erase(iter);
//se você quiser excluir1exclua usando a palavra-chave
Int n = mapStudent.erase(1);//Se for excluído, retornará1de outra forma, retornará 0
//Use iteradores para excluir em bloco
//Este código limpa todo o map
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//Atenção ao excluir em bloco, também é uma característica da STL, a exclusão de intervalo é um conjunto de fechamento anterior e abertura posterior
//Adicione o código de iteração e imprima a saída
}
8. Outras formas de uso de funções
Aqui estão swap, key_comp, value_comp, get_allocator e outras funções, sente-se que essas funções não são usadas muito no código, então não serão detalhadas, mas quem tiver interesse pode estudá-las por conta própria
9. Ordenação
Aqui se trata de um uso mais avançado, problema de ordenação, o STL usa por padrão o operador < para ordenação, o código acima não tem problema algum na ordenação, pois a chave é do tipo int, que suporta operação <, em alguns casos especiais, como a chave for uma estrutura, e envolver ordenação, há problema, pois não há operação <, as funções insert e outras não passam na compilação, aqui estão duas maneiras de resolver este problema
Primeira opção: sobrecarga de operador <, exemplo de programa
#include <map>
#include <string>
Using namespace std;
Typedef struct tagStudentInfo
{
Int nID;
String strName;
}StudentInfo, *PStudentInfo; //学生信息
Int main()
{
int nSize;
//Mapeamento de informações de aluno
map<StudentInfo, int>mapStudent;
map<StudentInfo, int>::iterator iter;
StudentInfo studentInfo;
studentInfo.nID = 1;
studentInfo.strName = "student_one";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));
studentInfo.nID = 2;
studentInfo.strName = "student_two";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));
for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)
cout<<iter->first.nID<<endl<<iter->first.strName<<endl<<iter->second<<endl;
}
O programa acima não pode ser compilado, é só sobrecarregar o operador <, OK, como no exemplo a seguir:
Typedef struct tagStudentInfo
{
Int nID;
String strName;
Bool operator < (tagStudentInfo const& _A) const
{
//Esta função especifica a estratégia de ordenação, ordenando por nID, e se nID for igual, ordenando por strName
Se(nID < _A.nID) retornar true;
Se(nID == _A.nID) retornar strName.compare(_A.strName) < 0;
Return false;
}
}StudentInfo, *PStudentInfo; //学生信息
Segunda opção: aplicação de funções de emulação, neste momento a estrutura não possui sobrecarga direta de operador <, explicação do programa
#include <map>
#include <string>
Using namespace std;
Typedef struct tagStudentInfo
{
Int nID;
String strName;
}StudentInfo, *PStudentInfo; //学生信息
Classs sort
{
Public:
Bool operator() (StudentInfo const &_A, StudentInfo const &_B) const
{
Se(_A.nID < _B.nID) return true;
Se(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0;
Return false;
}
};
Int main()
{
//Mapeamento de informações de aluno
Map<StudentInfo, int, sort>mapStudent;
StudentInfo studentInfo;
studentInfo.nID = 1;
studentInfo.strName = "student_one";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));
studentInfo.nID = 2;
studentInfo.strName = "student_two";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));
}
10. Além disso
Como o STL é um todo unificado, muitos usos do map estão combinados com outros componentes do STL, por exemplo, na ordenação, aqui é usado o sinal de menor, ou seja, less<>, se você quiser ordenar do maior para o menor, isso envolve muitos aspectos, não posso explicar um a um aqui.
Também deve ser mencionado que, devido ao map ser internamente ordenado, garantido pela árvore rubro-negra, muitas funções têm complexidade de tempo log.2Se a função do map pode ser implementada, e o STL Algorithm também pode completar essa função, é recomendável usar as funções integradas do map, que são mais eficientes.
Vamos falar sobre as características espaciais do map, senão, você pode se sentir um pouco chato ao usá-lo, pois cada dado do map corresponde a um nó na árvore rubro-negra, e esse nó ocupa espaço quando não armazena seus dados16Um byte, um ponteiro de nó pai, ponteiros de filhos esquerdo e direito, e ainda um valor enum (sinaliza vermelho e preto, equivalente ao fator de equilíbrio em árvores binárias de busca balanceadas), acho que você deve saber, esses lugares consomem muita memória, não vou mais falar ...
Isso é o que o editor trouxe para você uma conversa breve sobre c++Todo o conteúdo detalhado do uso de map no STL e map, espero que todos apoiem e gritem tutorial ~