Newsgroup: it.comp.lang.c++
Titolo: [LONG]Vector o Map

// Parse.hpp
#ifndef PARSE_HPP_
#define PARSE_HPP_
#include "Define.hpp"
#include <cstdio>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
N_BEG
/**
  <b>Name</b>:<i>SInfo</i>  \n
  <b>Author</b>:<i>Kleidemos</i> \n
  <b>Description</b>:<i>Configurazione</i>  \n
*/
typedef struct SInfo
{
 string key;
 string value;
} Info;
/**
  <b>Name</b>:<i>CParse</i>  \n
  <b>Author</b>:<i>Kleidemos</i> \n
  <b>Description</b>:<i>Parser classs for generic text</i>  \n
*/
class CParse
{
        public:
                CParse(){ _filename = "prog.conf"; };
                CParse(string name){ _filename = name; };
                CParse(char * name){ _filename = name; };
                ~CParse(){};
                virtual void Read(char separator = 'v');
                virtual void Write(char separator = 'v', string key = "",
string value = "");
      void Test();
      virtual string Find(string key);
        private:
                string _filename;
                vector<Info> conf;
};
N_END
#endif
// Parse.cpp
#include "Parse.hpp"
N_BEG
/**
  <b>Name</b>:Read\n
  <b>Return</b>: -\n
  <b>Argoments</b>: A separator [ DEFAULT: v ] \n
  <b>Description</b>:Puts a generic config into internal buffer\n
*/
void CParse::Read(char separator)
{
 ifstream IN(_filename.c_str());
 char code;
 string key, value;
 Info inf;
 while(IN)
 {
  IN >> code;
  if(code == separator) // a key find
  {
   IN >> key >> value;
   inf.value = value;
   inf.key = key;
   conf.push_back(inf);
  }
  else
  {
   key = " ";
   value = " ";
   // conf.push_back(inf);
  }
 }
 IN.close();
}
/**
  <b>Name</b>:Write\n
  <b>Return</b>:-\n
  <b>Argoments</b>:
  - The name of options
  - The value\n
  - A separator [ DEFAULT: v ]
  <b>Description</b>:Write a generic config value
*/
void CParse::Write(char separator, string key, string value)
{
 ofstream OUT(_filename.c_str(), ios::app);
 OUT << separator << " " << key << " " << value << "\n";
 OUT.close();
}
/**
  <b>Name</b>:Find\n
  <b>Return</b>:A Value of option\n
  <b>Argoments</b>: The name of option \n
  <b>Description</b>: Findo a option\n
*/
string CParse::Find(string key)
{
 string ret;
 vector<Info>::iterator It = conf.begin();
 for(; It != conf.end();++It)
 {
  if(It->key == key)
   ret = It->value;
 }
 return ret;
}
/**
  <b>Name</b>:Test\n
  <b>Return</b>:-\n
  <b>Argoments</b>: -
  <b>Description</b>: Test the class\n
  <b>ONLY FOR DEBUG</b>
*/
void CParse::Test()
{
 // Inserting
 Write('v', "prova", "si"); // write prova
 Write('v', "provas", "no");// write provas
 Write('v', "Schermo", "1024x768");// write Schermo
    Write('n', "Schermos", "1024x768");// write error value
 // Reading
 Read('v'); // puts read file
 // Printing
 typedef vector<Info>::iterator It;
 It it = conf.begin();
 for(;it != conf.end();++it) // iterator
 {
  cout << it->key << " => " << it->value << "\n";
 }
 // Finding
 cout << "Finding prova => " << Find("prova") << "\n";
 cout << "Finding provas => " << Find("provas") << "\n";
 cout << "Finding Schermo => " << Find("Schermo") << "\n";
 cout << "Finding Schermos => " << Find("Schermos") << "\n";// try to find
error value
}
N_END
Se usassi map al posto di vector sarei + veloce o sarebbe + semplice????
Tnk
-- 
Kleidemos
C++ Programmer
kleidemo...@altervista.org

 
Sarebbe quasi sicuramente piu' veloce.
Inoltre std::map in questo caso mi sembra decisamente piu' appropriato, 
proprio perche' std::map e' fatto apposta per contenere dati associati 
ad una chiave.
Non avresti nemmeno bisogno di SInfo, basta fare:
std::map<std::string, std::string>
-- 
Roal Zanazzi


Non saprei come implementarlo :(
Cmq mi serviva solo una classe di configurazione portabile :)

 Se usassi map al posto di vector sarei + veloce o sarebbe + semplice????
Ammetto di non aver avuto voglia di cercar di capire per bene il tuo
programma....
(La prossima volta se riesci, al posto del codice, o oltre al codice, prova
a spiegare in due righe cosa fa il programma, cosa ti serve il vector, come
lo stai usando ora e come usereti il map? Cosi' eviterei di leggermi il tuo
codice e potrei aiutarti in un 5o del tempo.)
Ad ogni modo nota una:
struct Info
{
    string key;
    string value;
};
e poi un
vector<Info> conf;
poi inserisci i dati con:
inf.value = value;
inf.key = key;
conf.push_back(inf);
e..... li vuoi *trovare* con:
string CParse::Find(string key)
{
    string ret;
    vector<Info>::iterator It = conf.begin();
    for(; It != conf.end();++It){
        if(It->key == key)
            ret = It->value;
    }
    return ret;
}
Senza guardare il resto del programma spero di aver intuito perche' vorresti
usare std::map....
Ora come ora, l'inserimento di dati dentro il vector e' efficiente, quello
che non e' efficiente e' la funzione Find ovviamente!
Scorrere tutto un array non e' mai una buona soluzione!
Usare std::map renderebbe la funzione Find parecchio piu' efficiente. Le
altre operazioni  potrebbero risultare appena piu' lente,  ma dubito che
questo sia un problema (la differenza e' minima rispetto al miglioramento
che otterresti per la funzione Find).
In sostanza se find e' utilizzata abbastanza spesso allora usa le std::map.
Se find e' li solo per esserci e non verra' mai utilizzata (perche' puoi
benissimo leggere i dati uno alla volta nell'ordine in cui sono senza
problemi, ad esempio) allora continua ad usare std::vector perche' i suoi
tempi di inserimento sono minori (e valuta se ti conviene rimuovere del
tutto la funzione find).
Se vuoi usare vector devi pero' cercare di evitare la reallocation, quindi
riservare un  numero di elementi (v.reserve(1000) ad esempio). Se la
reallocation avviene spesso vector potrebbe diventare piu' lento di std::map
;-)
C'e' anche da dire che se come credo andrai a scrivere pochi elementi dentro
questo vector allora probabilmente la tua implementazione gia' riservera'
abbastanza spazio (forse troppo) e quindi non ti serve questo "trucchetto"
e... per essere sincero tutto questo discorso di performance tra std::map e
std::vector non servirebbe piu' a nulla! Se hai 15 elementi tra scorrerli
tutti in un vector e trovarli in un albero ordinato non e' che cambi
molto....
std::map e std::multimap sono generalmente implementate come "balanced binay
trees" (non e' detto pero' che vengano implementate cosi' in tutti i
casi...). Per questo motivo sono molto utili; tale struttura dati permette
un mucchio di operazioni. Se pero' cerchi "performance" allora puoi
sacrificare il numero delle operazioni per ottenere maggiori prestazioni....
e costruirti una tua hash table..... (per ora le "hash tables" non fanno
parte della C++ standard library, ma se non vuoi scrivertene una puoi sempre
utilizzare quelle di altre librerie).
Le hash tables sono persino piu' veloci nel lookup degli elementi di map e
multimap..... (ma puoi farci meno cose con esse (non hanno ordering ad
esempio).... studiatele nel tuo libro algoritmi per maggiori dettagli).
std::map e std::multimap generalmente ordinano i valori nell'albero in base
alla loro key e quindi le operazioni di inserimento ovviamente metteranno
l'elemento nel giusto posto (un pochino di overhead) e... le operazioni per
trovare un elemento con una certa chiave funzioneranno come negli *alberi
binari di ricerca* dei libri che hai comprato.... (quindi veloci ma meno che
in una ht).
HTH,
Tommy

Kleidemos wrote:

Direi che e' giunta l'ora di imparare anche la std::map. ;-)
Non e' poi tanto difficile (alla fine il codice sara' anche piu' 
semplice di quello che hai scritto usando un vector).
Con l'aiuto di un buon libro e sse proprio ti sei incasinato, con il 
newsgroup, ce la farai. Te lo assicuro. ;-)
-- 
Roal Zanazzi

 Cmq mi serviva solo una classe di configurazione portabile :)
Provaci ti possiamo aiutare....
Magari prova con un problema piu' semplice (senza i/o su files etc..) un
problema solo per imparare.
std::map<std::string, std::string> non e' per nulla piu' difficile di quanto
tu non stia facendo con vector!!!
Tommy

 Tommy
Prova a vedere se sul fido Lippman c'è qualcosa :)


 Provaci ti possiamo aiutare....
Ok, ho scritto una cosina al volo che spero possa aiutarti.....
<CODE>
#include<iostream>
#include<string>
#include<map>
int main()
{
    std::map<std::string,std::string> m;
    m.insert(std::make_pair("COLORE SFONDO","BLUE"));
    m.insert(std::make_pair("COLORE TESTO","BIANCO"));
    m.insert(std::make_pair("LARGEZZA SCHERMO","80"));
    m.insert(std::make_pair("ALTEZZA SCHERMO","150"));
    m.insert(std::make_pair("TITOLO","MY PAGE"));
    m.insert(std::make_pair("FONT","ARIAL"));
    std::cout << m.find("TITOLO")->second << std::endl;
    // o ancora piu' semplice:
    m["IMMAGINE"] =  "CIGNO.GIF";
    m["ALARM"] = "00:00:00";
    m["ZOOM"] = "100%";
    std::cout << m["TITOLO"] << std::endl;
    std::cout << m["ALARM"] << std::endl;
    // pui sempre usare l'altro modo se vuoi:
    std::cout << m.find("ALARM")->second << std::endl;
    return 0;
}
</CODE>
Come vedi ho un:
std::map<std::string,std::string> m;
dopo di che posso inserire i valori con:
m.insert(std::make_pair("TITOLO","MY PAGE"));
oppure:
m["TITOLO"] = "MY PAGE";
il secondo metodo usa le maps come fossero "associative arrays".
In fine puoi trovare i dati con:
std::cout << m.find("TITOLO")->second << std::endl;
oppure:
std::cout << m["TITOLO"] << std::endl;
Nel primo metodo nota il ->second che serve per ottenere la "seconda parte"
ovvero il value della coppia key-value. In effetti find() ritorna un
iterator all' elemento in con la key specificata. Se l'elemento non viene
trovato allora ritorna end() del container.
Spero che questo banale esempio ti possa essere utile per incomiciare a
capire come usare std::map. Ovviamente per scorrere tutti gli elementi fai
come fai di solito.....
Tommy

Comincio a capire.
Quindi mi semplificherei di molto la mia classe e ne ottimizzerei la
ricerca????
Ma se la classe che ho scritto con vector mi servizze per diciamo 15-16
opzioni, con map avrei ancora vantaggi?


 Prova a vedere se sul fido Lippman c'# qualcosa :)
A questo punto mi chiedo che versione del Lippman tu abbia....
Io ho "C++ Primer, 3rd ed" e ti assicuro che nelle sezioni:
"Defining and Populating a Map" e "Finding and Retrieving a Map Element"
ho trovato tutto quello che ti serve....
Inoltre c'e' anche la sezione "Iterating across a Map" che ti puo' essere
utile piu' altre la cui utilita' nel tuo caso e' meno ovvia credo, come ad
esempio "Erasing Elements from a Map".
Quindi prova a cercare meglio oppure controlla di non aver comprato una
versione vecchia del libro....
Se puoi vuoi una trattazione piu' specifica dei vari containers e della
standard library in generale allora... ricordi la lista di libri che ti ho
dato? Beh, in quella lista c'e':
"The C++ Standard Library : A Tutorial and Reference - by Nicolai M.
Josuttis"
ma credo che per quello che devi fare ora il Lippman possa bastare.
Tommy

Trovato.
Ma nn è molto diverso da quello che penzavo allora.


 opzioni, con map avrei ancora vantaggi?
Quando gli elementi sono cosi' pochi l'ultima cosa a cui devi pensare e'
ottimizzare....
Quello a cui devi pensare invece e' rendere la scrittura del codice piu'
semplice, piu' elegante, meno error-prone etc...
In questo caso map e' adatto, ma non tanto per le prestazini di find(),
tanto quanto per la maggior eleganza e praticita'; visto che stai di fatto
emulando una truttura key-value usando un vector di una struct che ha un key
ed un value....
Spero di essermi spiegato.
Tommy