Newsgroup: it.comp.lang.c++
Titolo: Raggruppamento elementi

Salve a tutti, ho una lista di oggetti da visualizzare, di cui è
importante preservare l'ordine. Vorrei raggrupparli in modo da
visualizzare solo 1 occorrenza di ogni elemento, seguita dal numero di
volte che si ripete nella lista. In pratica da una sequenza di
stringhe:
ciao
io
ciao
lei
vorrei ottenere:
ciao [2]
io [1]
lei [1]
Non potendo usare un map (visto che voglio mantenere l'ordinamento
originario) e non volendo usare contenitori non standard ho definito:
....
typedef std::list <Oggetto*>  objList; // lista degli oggetti
typedef std::vector <std::pair<std::string,int> > doubVect;
....
  doubVect raggruppaNomi(objList& seq, uInt dim = 0) {
    doubVect v;
    for (objIter It=seq.begin(); It != seq.end(); ++It)
      if ((*It)->getDimensione() >= dim &&
!cercaDoubVect(v,(*It)->getNome()))
v.push_back(make_pair((*It)->getNome(),count_if(seq.begin(),seq.end(),nomi_uguali<Oggetto>(*It))));
    return v;
  }
....
  bool cercaDoubVect(doubVect& v, string s) {
    for (doubVect::iterator It = v.begin(); It != v.end(); ++It)
      if (It->first == s) return true;
    return false;
  }
....
  template <class T> class nomi_uguali : public unary_function<T,bool>
{
    T* arg2;
  public:
    explicit nomi_uguali(T* const&x)   { arg2 = x; }
    bool operator() (T* const&x) const { return arg2->getNome() ==
x->getNome(); }
  };
getNome è chiaramente il metodo della classe Oggetto per raggruppo.
La visualizzazione della lista di oggetti diventa quindi:
doubVect v = raggruppaNomi(oggetti);
for (doubVect::iterator vIt=v.begin(); vIt != v.end(); ++vIt)
   cout << "elemento: " << vIt->first << " ripetizioni: " <<
vIt->second << endl;
L'approccio da me utilizzato non mi soddisfa pienamente, essendo ad
occhio O(n^2) nel caso peggiore (dato che ogni volta che inserisco un
elemento nel vettore di doubvect lo scorro in modo lineare per
assicurarmi che l'elemento non sia gia' presente). Dati i requisiti a
me necessari (ordinamento e utilizzo di contenitori standard) qualcuno
ha in mente un modo piu' elegante ed efficiente per eseguire la stessa
cosa, magari in un O(2*n) ? Sono apprezzati anche commenti / critiche
sullo stile :-)
Grazie

 sullo stile :-)
Nota che O(2n) = O(n).
Penso che il limite teorico, usando i confronti, sia O(nlogn) (come per 
l'ordinamento).
Usa pure una mappa oppure ordina la lista. Col primo passaggio determini 
la molteplicità degli elementi, mentre col secondo ristabilisci l'ordine 
(reinterrogando nuovamente la mappa). Usando puntatori addizionali qua e 
là puoi risparmiare qualcosa, ma non credo ne valga la pena.
Kiuhnm

Si certo, O(2n) è dello stesso ordine di grandezza di O(n), tuttavia
per come ho strutturato le cose il caso peggiore (elementi della lista
originaria tutti diversi) è O(n^2). Non ho capito come faresti a
ristabilire l'ordine iniziale (che non è quello alfabetico) scorrendo
una seconda volta la mappa di appoggio.

Gianni Valdambrini ha scritto:

Scorri la lista, non la mappa.
L = lista (piena)
M = mappa (vuota)
per ogni l in L
   se l in M => M.l.count++
   altrimenti
     inserisci l in M
     M.l.count = 1
L = lista (piena)
S = lista (vuota)
per ogni l in L
   se l in M
     inserisci (l,M.l.count) in S
     rimuovi M.l da M
... o qualcosa del genere...
Kiuhnm

 volte che si ripete nella lista. In pratica da una sequenza di
std::stable_sort
O(n log n) se c'č abbastanza memoria extra, altrimenti O( n log^2 n )

 O(n log n) se c'è abbastanza memoria extra, altrimenti O( n log^2 n )
Lo stable_sort mi garantisce l'ordinamento di elementi uguali. A me
invece serve che elementi diversi mantengano l'originario ordinamento
(che non è quello alfabetico ma è l'ordine di inserimento degli
oggetti nella lista), e che n elementi uguali vengano raggruppati in
un'unico elemento.