Apresentação de Map na Disciplina de Competições.

fibomap.cpp

#include <iostream>
#include <string>
#include <map>

using namespace std;

//na primeira vez que esse código for executado, por exemplo, para um fib(4), 
//ele vai ter que calcular respectivamente o fib(2) e fib(3), porem, quando eu 
//chamar um fib(5), como os resultados anteriores ja estarão armazenados no map e o 
//valor será retornado sem nenhum calculo adicional, e com isso, teremos um bom ganho no tempo de execução.
//end Retorna um iterador referindo-se ao elemento final no  mapa. 

int fib_melhorado( int n ){

  map<int,int> resultado;


  //colocando limites!
  if resultado.max_size() > 100{
  


    if ( n == 0 || n == 1 )
     return 1;
      
      map<int,int>::iterator it = resultado.find( n );
      
  


      //ultimo elemento
      if ( it != resultado.end() )

        return it->second;

      else

        return resultado[ n ] = fib_melhorado( n -1 ) + fib_melhorado( n - 2 );
  
    }

}


int fib( int n ){

   if ( n <2 )
     return 1;
   else
     return fib( n - 1 ) + fib( n - 2 );
}


int main(){

    cout << fib_melhorado(3) << endl;
    cout << fib_melhorado(4) << endl;
    cout << fib_melhorado(5) << endl;

    cout << fib(3) << endl;

	return 0;
}

gistfile1.txt

A classe map é uma classe da STL (Standard Template Library).

Um mapa associa uma chave a um valor. Exemplo: o CPF de uma pessoa poderia ser a chave, cada CPF está associado ao nome de uma pessoa, então o nome seria o valor. 

O mapa utiliza pelo menos dois parâmetros templates: o tipo da chave K e o tipo de dado T. Os templates permitem que funções e classes operem com tipos genéricos.

A utilização de mapas possui a complexidade O(log(n)) para pesquisa e inserção.













Referencias :

http://www.geeksbr.com/2012/10/programacao-em-c-utilizando-mapa-map.html
http://www.cplusplus.com/reference/utility/pair/
http://jumpi.wordpress.com/2008/01/23/mais-fibonacci-usando-memoize-com-map-em-c/
http://www.cplusplus.com/reference/map/map/

map.cpp

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){

    map<string, string> meu_mapa;
    string cpf,nome;

    cout << "Digite o Cpf" << endl;
    cin >> cpf;

    cout << "Digite o nome" << endl;
    cin >> nome;

    //com pair tenho acesso aos alementos assim:
    //first	The first value in the pair
    //second	The second value in the pair

    //metodo insert
    meu_mapa.insert(pair <string,string> (cpf, nome));





    //mapa vazio ?
    if( !meu_mapa.empty() ) {
    	cout << "Map Ja não está mais vazio" << endl;
    }



    //declarando iterator
    map <string, string> :: iterator iterator;





    //metodo find busca o elemento passando a chave
    iterator = meu_mapa.find(cpf);


    cout  << "Meu cpf: " << iterator->first << endl;
    cout  << "Meu Nome: " << iterator->second << endl;






    //tamanho do mapa
    cout << "Tamanho do meu mapa " << meu_mapa.size() << endl;





    //quantidade de elementos no mapa com tal chave

    cout << "meu mapa tem = "<< meu_mapa.count("1") << " com a chave 1" << endl;
    cout << "meu mapa tem = "<< meu_mapa.count("0") << " com a chave 0" << endl;





    //pegar o inicio do mapa
    map <string, string> :: iterator inicio = meu_mapa.begin();

    //apagar o primeiro elemento
    meu_mapa.erase(inicio);


    //apagar tudo
    meu_mapa.clear();


   cout << "Tamanho do meu mapa apagando 1 elemento " << meu_mapa.size() << endl;

	return 0;
}

swapmap.cpp

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){

    map<int, int> map_impar;
    map<int, int> map_par;

    map_impar[0] = 1;
    map_par[0] = 2;

    map <int, int> :: iterator iterator;


    swap(map_impar,map_par);


    iterator = map_par.find(0);
    cout << "Meu numero par= " << iterator->second << endl;


    iterator = map_impar.find(0);
    cout << "Meu numero impar= " << iterator->second << endl;

	return 0;
}