Vetor Associativo

Um vetor associativo é uma estrutura de dados composta de um conjunto  não ordenado de itens formados por um par chave e valor, no  qual a chave possui um valor associado. As chaves são definidas pelo usuário e são armazenadas na  própria estrutura. O relacionamento existente entre as chaves e seus respectivos valores é chamado  de mapeamento, pois para buscar um valor utiliza-se a chave como índice de busca.

A implementação de um vetor associativo em algumas linguagens de  programação, os elementos são armazenados e recuperados com funções de dispersões (funções hash). A implementação em C++ utiliza uma árvore binária balanceada  denominada árvore rubro-negra. Com esta  implementação, temos complexidade logarítmica tanto na inserção e busca de uma chave no vetor associativo.

Mas agora, temos o seguinte problema, como acessar os elementos do vetor associativo, sequecialmente, sem exposição de estruturas internas. Por  exemplo, considere um tipo vetor implementado como um vetor dinâmico. Um  iterador deve permitir o acesso a todos os elmentos da lista de uma forma  segura sem que ocorra perda de informação ou modificações não permitidas da
seguinte maneira: 

vector <int> v; 

v.push_back(3); 
v.push_back(5); 
v.push_back(4); 
v.push_back(6); 
vector <int>::iterator it; 

for(it = v.begin() ; it!= v.end(); it++){ 
   printf("%d",*it); 
} 

Na verdade, o iterator é um padrão de projeto. Os padrões de projeto  podem ser vistos como uma solução que já foi testada para um problema. Desta forma, um padrão de projeto geralmente descreve uma solução ou uma instância  da solução. O movimento ao redor de padrões de projeto ganhou popularidade
com o livro Design Patterns: Elements of Reusable Object-Oriented Software,  publicado em 1995. Os autores desse livro são Erich Gamma, Richard Helm,  Ralph Johnson e John Vlissides, conhecidos como a "Gangue dos Quatro" (Gang of Four) ou simplesmente "GoF".

O iterator permite a "iteração" e modo de acesso a elementos de uma coleção de objetos, sequencialmente, sem exposição de estruturas internas.

Além dos padrões de projetos, temos também os anti padrões de projetos. Vale a pena conhecê-los.

Exemplo de iterator + vetores associativos:

#include <vector>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;
int main(){
 map <string,int> mapa;
 mapa["brasil"] = 2;
 mapa["argetina"] = 3;
 mapa["inglaterra"] = 4;
 if(mapa["franca"])
   printf("%d\n",mapa["franca"]);
 if(mapa["brasil"])
   printf("%d\n",mapa["brasil"]);
 map<string,int>:: iterator mapit;
 for(mapit = mapa.begin(); mapit!=mapa.end(); mapit++)
  cout << mapit->first << " " <<mapit->second << endl;
 system("PAUSE");
} 

2
argetina 3
brasil 2
franca 0
inglaterra 4
Pressione qualquer tecla para continuar. . .

Em Java, temos a classe HashMap é uma das principais implementações da interface Map. Além de fornecer todas as operações opcionais de um map, esta classe permite a inserção de chaves e valores com o valor null. Em realidade, a classe HashMap é bem similar à classe Hashtable, com a diferença que HashMap não é sincronizada (tenha cuidado ao usuá-la em ambiente de múltiplas threads) e permite valores e chaves null.

// hashmap_overview.jsl

import java.util.*;

public class Program
{
    public static void main(String[] args)
    {
        // Create a HashMap with three key/value pairs.
        HashMap hm = new HashMap();
        hm.put("One", "1");
        hm.put("Two", "2a");
        hm.put("Two", "2b");
        hm.put("Three", "3");

        // Iterate over the HashMap to see what we just put in.
        Set set = hm.entrySet();
        Iterator setIter = set.iterator();
        while (setIter.hasNext())
        {
            System.out.println(setIter.next());
        }

        // Print the size of the HashMap.  Hint, it won't be 4!
        if (!hm.isEmpty())
        {
            System.out.println("The HashMap contians " +
                hm.size() + " entries.");
        }
        else
        {
            System.out.println("The HashMap is empty!");
        }

        // Print out the keys and the values.
        Set keys = hm.keySet();
        Iterator keysIter = keys.iterator();
        while (keysIter.hasNext())
        {
            System.out.println("key: " + keysIter.next());
        }

        Collection values = hm.values();
        Iterator valuesIter = values.iterator();
        while (valuesIter.hasNext())
        {
            System.out.println("value: " + valuesIter.next());
        }

        // Look for a value corresponding to a key.
        if (hm.containsKey("Two"))
        {
            Object v = hm.get("Two");
            System.out.println("The value corresponding to the " +
                "key \"Two\" is " + v.toString());
        }

        // Look for the value "2a".
        if (!hm.containsValue("2a"))
        {
            System.out.println("The value \"2a\" does not exist " +
                "because it was replaced by the value \"2b\".");
        }

        // Remove an entry from the HashMap.
        if (hm.containsKey("Three"))
        {
            Object v = hm.remove("Three");
            System.out.println("The value " + v.toString() +
                " was removed from the HashMap.");
        }
    }
}

Output:

[One, 1]

[Two, 2b]

[Three, 3]

The HashMap contians 3 entries.

key: One

key: Two

key: Three

value: 1

value: 2b

value: 3

The value corresponding to the key "Two" is 2b

The value "2a" does not exist because it was replaced by the value "2b".

The value 3 was removed from the HashMap.