Recipientes exclusivos e ordenados em C ++

6, 10, 2, 8, 4 é um conjunto; 2, 4, 6, 8, 10 é um conjunto dos mesmos números inteiros, dispostos em ordem crescente. Na Matemática, um conjunto possui elementos únicos (elementos distintos), ou seja, nenhum elemento ocorre mais de uma vez. Além disso, um multiset é um conjunto, onde qualquer elemento pode ocorrer mais de uma vez. 6, 6, 10, 2, 2, 8, 4, 4, 4 é um multiconjunto. 2, 2, 4, 4, 4, 6, 6, 8, 10 é o mesmo multiconjunto, mas com os elementos dispostos em ordem crescente. Este artigo não trata de multiset. Ele lida com a estrutura de dados C ++ chamada, set.

Um mapa no software é como uma matriz, mas é uma matriz com duas colunas em vez de uma. A primeira coluna contém as chaves e a segunda coluna contém os valores. Cada linha é um par, formando um par chave / valor. Uma chave está diretamente relacionada ao seu valor.

Um exemplo de mapa é 'c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10. O primeiro par chave / valor inserido aqui é 'c', 3, onde 'c' é a chave e 30 é o valor. Este mapa não está ordenado por chaves. Ordenar este mapa por chaves produz 'a', 10, 'b', 20, 'c', 30, 'd', 30, 'e', 40. Observe que pode haver valores duplicados, mas não chaves duplicadas. Um mapa ordenado é um mapa ordenado por chaves.

Um multiset está para um conjunto, assim como um multimapa está para um mapa. Isso significa que existem mapas com chaves duplicadas. Um exemplo de multimapa é 'a', 10, 'b', 20, 'b', 20, 'c', 30, 'c', 30, 'd ', 30, ' e ', 40. E, como afirmado acima, este artigo não trata de multimapa, mas sim da estrutura de dados C ++ chamada, map.

Em C ++, uma estrutura de dados é uma estrutura com propriedades (membros de dados) e métodos (funções de membro). Os dados da estrutura são uma lista; um conjunto é uma lista; um mapa é uma lista de pares chave / valor.

Este artigo discute os conceitos básicos de conjuntos e mapas em C ++ e, para entender melhor este artigo, o leitor deve ter um conhecimento básico de C++.

Conteúdo do artigo:

Classe e seus objetos
Criação de um conjunto ou mapa
Iterator Basics
Acesso ao elemento para conjunto e mapa
Ordem dos elementos em um conjunto ou mapa
Outras funções de membro comumente usadas
Conclusão

Classe e seus objetos:

Em C ++, o conjunto, o mapa e outras estruturas semelhantes são chamados de contêineres. Uma classe é uma unidade generalizada com membros de dados, que são variáveis e funções de membro relacionadas. Quando os membros de dados recebem valores, um objeto é formado. No entanto, um objeto é formado em um processo chamado de instanciação. Como uma classe pode levar a diferentes valores para as mesmas variáveis de membro de dados, diferentes objetos podem ser instanciados a partir da mesma classe.

Em C ++, um conjunto inutilizável é uma classe, assim como um mapa inutilizável. Quando um objeto é instanciado a partir do conjunto inutilizável ou do mapa inutilizável, o objeto se torna a estrutura de dados real. Com as estruturas de dados de conjunto e mapa, o membro de dados principal é uma lista. Bem, o conjunto e o mapa formam um grupo de contêineres chamados contêineres associativos ordenados. O conjunto não ordenado e o mapa não ordenado também existem, mas infelizmente não são abordados neste artigo.

Criação de um conjunto ou mapa:

Instanciar um conjunto de sua classe de conjunto é criar um conjunto; instanciar um mapa de sua classe de mapa é criar um mapa. O objeto assim criado recebe um nome de escolha do programador.

Para criar um conjunto, o programa deve começar com:

#incluir
#incluir
usando namespace std;

Observe a diretiva “#include ”, Que inclui a biblioteca de conjuntos que possui a classe de conjunto a partir da qual as estruturas de conjunto de dados serão instanciadas.

Para criar um mapa, o programa deve começar com:

#incluir
#incluir
usando namespace std;

Observe a diretiva “#include ”, Que inclui a biblioteca de mapas que possui a classe de mapa a partir da qual as estruturas de dados do mapa serão instanciadas.

A sintaxe para criar um conjunto vazio é:

definir objectName

Exemplo:

definir setObj;

Um exemplo para criar um conjunto com conteúdo é:

definir setObj (6, 10, 2, 8, 4);

A sintaxe para criar um mapa vazio é:

mapa objectName

Exemplo:

mapa mapObj;

Um exemplo para criar um mapa com conteúdo é:

mapa mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Noções básicas do iterador:

Um iterador é um ponteiro elaborado, que pode ser usado para percorrer a lista da estrutura de dados do início ao fim.

A função de membro begin ()

A função de membro begin () retorna um iterador que aponta para o primeiro elemento da lista. O exemplo a seguir ilustra isso para o conjunto:

definir setObj (6, 10, 2, 8, 4);
definir:: iterator iter = setObj.começar();
cout << *iter << '\n';

Observe que a maneira como begin () foi usada com setObj e o operador ponto. iter é o objeto iterador retornado. Além disso, observe a maneira como foi declarado. * é o operador de indireção. Conforme usado com iter, ele retorna o primeiro elemento do conjunto; o primeiro elemento é 2 em vez de 6 - veja a explicação abaixo.

O exemplo a seguir ilustra o uso da função begin () para o mapa:

mapa mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: iterator iter = mapObj.começar();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Observe que a maneira como begin () foi usada com mapObj e o operador de ponto. iter é o objeto iterador retornado. Além disso, observe a maneira como foi declarado. “Primeiro”, conforme usado aqui, refere-se à chave. “Segundo” refere-se ao valor correspondente à chave. Observe como eles foram usados com o iter para obter os componentes do elemento inicial da lista. O primeiro elemento é a, 10 em vez de c, 30 - veja a explicação abaixo.

A função membro “begin () const”

A função de membro “begin () const” retorna um iterador que aponta para o primeiro elemento da lista quando a declaração do conjunto começa com const (para constante). Sob esta condição, o valor na lista, referido pelo iterador retornado, não pode ser alterado pelo iterador. O exemplo a seguir ilustra seu uso para o conjunto:

const set setObj (6, 10, 2, 8, 4);
definir:: const_iterator iter = setObj.começar();
cout << *iter << '\n';

Observe que a maneira como begin () foi usada com setObj e o operador ponto. Nenhum “const” foi digitado logo após begin (). No entanto, “const” precedeu a declaração. iter aqui é o objeto iterador constante retornado, que é diferente do iterador normal. Além disso, observe a maneira como foi declarado. * é o operador de indireção; como usado com iter, ele retorna o primeiro elemento do conjunto. O primeiro elemento é 2 em vez de 6 - veja a explicação abaixo.

O exemplo a seguir ilustra o uso da função “begin () const” para o mapa:

mapa const mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: const_iterator iter = mapObj.começar();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Observe que a maneira como begin () foi usada com mapObj e o operador de ponto. Nenhum “const” foi digitado logo após begin (). No entanto, “const” precedeu a declaração. iter aqui é o objeto iterador constante retornado, que é diferente do iterador normal. Além disso, observe a maneira como foi declarado. “Primeiro”, conforme usado aqui, refere-se à chave; “Segundo”, conforme usado aqui, refere-se ao valor correspondente à chave. Observe como eles foram usados com o iter para obter os componentes do elemento inicial da lista. O primeiro elemento é a, 10 em vez de c, 30 - veja a explicação abaixo.

A função de membro end ()

A função de membro end () retorna um iterador que aponta logo após o final da lista. O exemplo a seguir ilustra isso para o conjunto:

definir setObj (6, 10, 2, 8, 4);
definir:: iterator iter = setObj.fim();
cout << *iter << '\n';

Observe a maneira como end () foi usado com setObj e o operador ponto. iter é o objeto iterador retornado. Além disso, observe a maneira como foi declarado. * é o operador de indireção; como usado com iter, ele retorna o último elemento + 1 do conjunto. No computador do autor, este último elemento + 1 é 5, que não está na lista. Portanto, cuidado para não usar este elemento.

O exemplo a seguir ilustra o uso da função end () para o mapa:

mapa mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: iterator iter = mapObj.fim();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Observe a maneira como end () foi usado com mapObj e o operador ponto. iter é o objeto iterador retornado. Além disso, observe a maneira como foi declarado. * é o operador de indireção; como usado com o iter, ele retorna o último + 1 elemento do mapa. No computador do autor, este último elemento + 1 é , 0, que não está na lista. Portanto, cuidado para não usar este elemento.

A função membro “end () const”

A função de membro “end () const” retorna um iterador que aponta logo após o final da lista quando a declaração do conjunto começa com const (para constante). Sob esta condição, o valor na lista, referido pelo iterador retornado, não pode ser alterado pelo iterador. O exemplo a seguir ilustra seu uso para o conjunto:

const set setObj (6, 10, 2, 8, 4);
definir:: const_iterator iter = setObj.fim();
cout << *iter << '\n';

Observe a maneira como end () foi usado com setObj e o operador ponto. Nenhum “const” foi digitado logo após o final (). No entanto, “const” precedeu a declaração. iter é o objeto iterador retornado. Além disso, observe a maneira como foi declarado. * é o operador de indireção; como usado com iter, ele retorna o último elemento + 1 do conjunto.

O exemplo a seguir ilustra o uso da função “end () const” para o mapa:

mapa const mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapa:: const_iterator iter = mapObj.fim();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Observe a maneira como end () foi usado com mapObj e o operador ponto. Nenhum “const” foi digitado logo após o final (). No entanto, “const” precedeu a declaração. iter é o objeto iterador constante retornado, que é diferente do iterador normal. Além disso, observe cuidadosamente a forma como foi declarado.

Acesso ao elemento para conjunto e mapa:

Definir

Com o conjunto, o elemento é lido usando o operador de indireção. Os primeiros dois elementos de um conjunto são lidos no seguinte exemplo:

definir setObj (6, 10, 2, 8, 4);
definir:: iterator iter = setObj.começar();
cout << *iter << '\n';
++iter;
cout << *iter << '\n';

O resultado é 2, seguido por 4 - veja a explicação abaixo. Para apontar para o próximo elemento da lista, o iterador é incrementado.

Nota: Um elemento não pode ser alterado usando o operador de indireção para o conjunto. Por exemplo, “* iter = 9;” não é possível.

mapa

Um mapa consiste em pares de chave / valor. Um valor pode ser lido usando a chave correspondente e alterado usando a mesma chave. O seguinte segmento de código ilustra isso:

mapa mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
cout << mapObj['b'] << '\n';
mapObj ['b'] = 55;
cout << mapObj['b'] << '\n';

O resultado é:

20
55

O operador ponto não foi usado aqui. Em vez disso, é o operador de colchetes, que usa a chave como conteúdo, que foi usado.

Ordem dos elementos em um conjunto ou mapa:

Os elementos podem ser inseridos em um conjunto, em qualquer ordem. No entanto, uma vez inserido, o conjunto reorganiza seus elementos em ordem crescente. A ordem crescente é a ordem padrão. Se a ordem decrescente for necessária, o conjunto deve ser declarado como no exemplo a seguir:

definir > setObj (6, 10, 2, 8, 4);

Então, após o tipo, e.g., int, para o modelo, há uma vírgula, seguida por “maior”Nos colchetes angulares.

Os elementos podem ser inseridos em um mapa em qualquer ordem. No entanto, uma vez inserido, o mapa reorganiza seus elementos em ordem crescente por chave (apenas), enquanto mantém a relação entre cada chave e seu valor. A ordem crescente é a ordem padrão; se a ordem decrescente for necessária, o mapa deve ser declarado como no exemplo a seguir:

mapa > mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Então, após o par de tipos, e.g., “Char, int”, para o modelo, há uma vírgula, seguida por “maior”Nos colchetes angulares.

Atravessando um conjunto

O loop while ou loop for com o iterador pode ser usado para percorrer um conjunto. O exemplo a seguir usa um loop for para percorrer um conjunto que foi configurado em ordem decrescente:

definir > setObj (6, 10, 2, 8, 4);
para (definir:: iterator iter = setObj.começar(); iter != setObj.fim(); ++ iter)

cout << *iter << ";

O resultado é:

10 8 6 4 2

Incrementar um iterador aponta para o próximo elemento.

Atravessando um mapa

O loop while ou loop for com o iterador pode ser usado para percorrer um mapa. O exemplo a seguir usa um loop for para percorrer um mapa que foi configurado em ordem decrescente:

mapa > mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
para (mapa:: iterator iter = mapObj.começar(); iter != mapObj.fim(); ++ iter)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

O resultado é:

e, 40, d, 30, c, 30, b, 20, a, 10,

Incrementar um iterador aponta para o próximo elemento. “Primeiro”, no código, refere-se à chave e “segundo” refere-se ao valor correspondente. Observe como esses valores foram obtidos para a saída.

Outras funções de membro comumente usadas:

A função size ()

Esta função retorna um inteiro, que é o número de elementos na lista. Defina o exemplo:

definir > setObj (6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

A saída é 5.

Exemplo de mapa:

mapa > mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
cout << mapObj.size() << '\n';

A saída é 5.

A função insert ()

definir

conjunto não permite duplicar. Portanto, qualquer duplicata inserida é rejeitada silenciosamente. Com o conjunto, o argumento para a função insert () é o valor a ser inserido. O valor é ajustado em uma posição, na qual a ordem no conjunto permanece crescente ou decrescente. Exemplo:

definir setObj (6, 10, 2, 8, 4);
setObj.inserir (6);
setObj.inserir (9);
setObj.inserção (12);
para (definir:: iterator iter = setObj.começar(); iter != setObj.fim(); ++ iter)

cout << *iter << ";

O resultado é:

2 4 6 8 9 10 12

Nota: A função de membro insert () pode ser usada para preencher um conjunto vazio.

mapa

o mapa não permite duplicação por chave. Portanto, qualquer duplicata inserida é rejeitada silenciosamente. Com o mapa, o argumento para a função insert () é o par chave / valor entre colchetes. O elemento é ajustado em uma posição por chave, na qual a ordem no mapa permanece crescente ou decrescente. Exemplo:

mapa mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapObj.inserir ('e', 80);
mapObj.inserir ('f', 50);
mapObj.inserir ('g', 60);
para (mapa:: iterator iter = mapObj.começar(); iter != mapObj.fim(); ++ iter)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

O resultado é:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

Nota: A função de membro insert () pode ser usada para preencher um mapa vazio.

A função empty ()

Esta função retorna verdadeiro se a lista estiver vazia e falso caso contrário. Defina o exemplo:

definir setObj (6, 10, 2, 8, 4);
bool ret = setObj.vazio();
cout << ret << '\n';

A saída é 0 para falso, o que significa que o conjunto aqui não está vazio.

Exemplo de mapa:

mapa mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
bool ret = mapObj.vazio();
cout << ret << '\n';

A saída é 0 para falso, o que significa que o mapa aqui não está vazio.

A função erase ()

definir

Considere o seguinte segmento de código:

definir setObj (10, 20, 30, 40, 50);
definir:: iterator iter = setObj.começar();
definir:: iterator itr = setObj.apagar (iter);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
itr = setObj.apagar (itr);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';

O resultado é:

novo tamanho: 4
próximo valor: 20
novo tamanho: 3
próximo valor: 30

A função erase () pega um iterador que aponta para um elemento como um argumento. Depois de apagar o elemento, a função erase () retorna um iterador que aponta para o próximo elemento.

mapa

Considere o seguinte segmento de código:

mapa mapObj ('a', 10, 'b', 20, 'c', 30, 'd', 40, 'e', 50);
mapa:: iterator iter = mapObj.começar();
mapa:: iterator itr = mapObj.apagar (iter);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
itr = mapObj.apagar (itr);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

O resultado é:

novo tamanho: 4
próximo par de valores: b, 20
novo tamanho: 3
próximo par de valores: c, 30

A função erase () pega um iterador que aponta para um elemento como um argumento. Depois de apagar o elemento, a função erase () retorna um iterador que aponta para o próximo elemento.

A função clear ()

A função clear () remove todos os elementos da lista. Defina o exemplo:

definir setObj (6, 10, 2, 8, 4);
setObj.Claro();
cout << setObj.size() << '\n';

A saída é 0.

exemplo de mapa:

mapa mapObj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapObj.Claro();
cout << mapObj.size() << '\n';

A saída é 0.

Conclusão:

Uma estrutura de dados definida em C ++ é uma estrutura na qual a lista de elementos é armazenada em ordem crescente por padrão, ou em ordem decrescente por escolha do programador. Todos os elementos do conjunto são únicos. Uma estrutura de dados de mapa em C ++ é uma estrutura em que a lista é um hash de pares de chave / valor, armazenado em ordem crescente de chaves por padrão ou em ordem decrescente de chaves por escolha do programador. As chaves também são únicas e podem haver valores duplicados. O principal membro de dados de qualquer uma das estruturas é a lista. Qualquer uma das estruturas tem funções-membro, algumas das quais são comumente usadas.