Newsgroup: it.comp.lang.c++
Titolo: MODA.....

Salve e grazie a tutti...
il mio problema è il seguente: devo riuscire a tirar fuori da un array di
numeri il numero che compare più volte. Vi prego E' URGENTISSIMO!!!!
GRAZIE

 numeri il numero che compare più volte.
Usa un altro array che conterrà ad ogni posizione le volte che il numero
corripondente all'indice è apparso nel primo array. Alla fine cerca il
numero più grande e restituisci l'indice a cui lo hai trovato.
Se il range di numeri è troppo elevato per utilizzare questa tecnica
puoi sempre usare delle varianti che memorizzino anche il numero (ad es.
un array parallelo o un array di struct) e quindi occupino solo lo
spazio corrispondente ai numeri effettivamente trovati.
EMG

 GRAZIE
Prova questo.
Va bene per piccole quantita' di numeri (intorno ai 10 milioni).
Per quantita' superiori devi utilizzare le tecniche che ti sono 
state suggerite in un'altro post.
Fausto
----------------------------------------------------
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
#include <time.h>
int main(int argc, char* argv[])
{
	// Un po di numeri per fare il test
	vector<int>                        ary;
	vector<int>::iterator              vtor;
	srand( (unsigned)time( NULL ) );
	for ( int i = 0; i < 10000; i++ )
		ary.push_back(rand());
 
    // algoritmo per il  calcolo
	map<int,int>                       counter;
	pair<int,int>                      p;
	map<int,int>::iterator             result;
	pair<map<int,int>::iterator,bool>  bp;
	clock_t start, end;
	start = clock();
	vtor = ary.begin();
	for( ; vtor != ary.end(); vtor++) {
		p.first = *vtor;
		p.second = 1;
		bp = counter.insert(p) ;
		if ( !bp.second ) 
			(*(bp.first)).second++;
	}
	map<int,int>::iterator  itor = counter.begin();
	p = *itor;
	// Cerca il numero che compare piu' volte.
	// P.S.: Trovo un solo numero. Potrebbero essere piu' di uno
	for ( ; itor != counter.end(); itor++ )
		if ( p.second < (*itor).second )
			p = *itor;
	end = clock();
	// Un po di stampe
	cout << "Tempo impiegato:  " << ((double)(end - start) / CLOCKS_PER_SEC
) << endl;
	cout << "Numero: " << p.first << "\tchiamato: " << p.second << " volte"
<< endl;
	// Elenco dei numeri
	cout << "---- Elenco dei numeri ------" << endl;
	itor = counter.begin();
	for ( ; itor != counter.end(); itor++ )
		cout << "Numero: " << (*itor).first 
		     << "\tchiamato: " << (*itor).second << " volte" << endl;
 
	return 0;
}

 
Se a qualcuno può servire, ecco un possibile approccio generico basato
sulla stessa idea del programma di Fausto (funziona sia con array che con
vettori, che con qualsiasi cosa che disponga di un forward iterator e con
qualsisi tipo di valore che possa fuzionare come chiave in una map).
 template< typename ForIter >
  iterator_traits< ForIter >::value_type &
  most_frequent_element( ForIter start, ForIter end )
  {
    ForIter most_freq = start;
    int max_count = 0;
    map< iterator_traits< ForIter >::value_type, int> hits;
 
    for( ForIter i = start; i != end; ++i )
    {
        int & count = hits[ *i ];
        if( max_count < ++count )
        {
            max_count = count;
            most_freq = i;
        }
    }
    return *most_freq;
  }
 //  array
 cout << most_frequent_element( &array[0], &array[0] + length ) << endl;
 //  vector
 cout << most_frequent_element( vect.begin(), vect.end() ) << endl;
Max

   }
Se date in pasto questo codice al Visual, otterrete degli errori, in 
quanto non riesce a risolvere il tipo dell'iteratore passato come 
parametro all'overload del map "... operator[] (...)"
( e cioe' il codice hits[ *i ] ) ed il tipo del ritorno della
template function.
Se provate ad aiutarlo facendogli fare un cast esplicito 
(iterator_traits< ForIter >::value_type) otterrete un bel
INTERNAL COMPILER ERROR. Era un bel pezzo che non lo vedevo.
----------------------------------------------------------------------
C:\temp\prova.cpp(100) : fatal error C1001: INTERNAL COMPILER ERROR
  (compiler file 'E:\8447\vc98\p2\src\P2\ehexcept.c', line 577)
    Please choose the Technical Support command on the Visual C++
    Help menu, or open the Technical Support help file for more
information
Error executing cl.exe.
Creating browse info file...
----------------------------------------------------------------------
Questa mail voleva solo evidenziare il fatto che il Borland Builder 4
e' piu' in linea con lo standard del Visual nonostante quest'ultimo
abbia 3 service pack alle spalle. 
Fausto

 >   most_frequent_element( ForIter start, ForIter end )
A rigor di standard, questo codice non dovrebbe compilare,
mi sembra, poiche` manca un typename alla seconda riga.
Per chiarire: nello standard C++, il parsing viene fatto una
volta per tutte PRIMA di istanziare i tipi-parametri dei
template.  Qualunque costrutto simile a
    unparametro::pippo
o
    pataccone<unparametro>::pippo
ecc ecc, viene dunque preso come NON caratterizzante un
nome di tipo; se E` un nome di tipo, cio` va esplicitato:
    typename unparametro::pippo
o
    typename pataccone<unparametro>::pippo
e la keyword typename e` stata introdotta proprio per
questo specifico scopo.
Portare un esempio di codice che NON dovrebbe compilare,
e che invece un certo compilatore erroneamente "manda
giu`", per sostenere che quel compilatore "e` standard",
e` un comportamento veramente molto, molto curioso.
Alex

 mi sembra, poiche` manca un typename alla seconda riga.
Perche'??  
Direi il contrario visto che le dichiarazioni dei typedef in
iterator_traits  sono tutte precedute da typename
Inoltre iterator_traits nel Borland e' definito come nello
standard, nel visual no.
Dove sta il codice non standard????
Fausto

 template function.
Invece (strano a dirsi) con il DJGPP funziona (incredibile dictu)
perfettamente.
EMG

 Dove sta il codice non standard????
Nelle tre righe sopra citate, "il codice non standard"
sta presumibilmente nella seconda, per l'omissione di
"typename" (ma questa keyword avrebbe anche potuto
venire posta sulla prima riga, o su di una a se stante
in posizione intermedia fra la prima e la seconda).
Alex

 "typename" (ma questa keyword avrebbe anche potuto
Ribadisco non e' omessa. Guarda lo standard al
paragrafo [24.3.1].
Fausto

 
A questo punto, indipendentemente dall'aderenza o meno allo standard dei
due compilatori in oggetto, mi piacerebbe capire come rendere standard il
pezzettino di codice che avevo postato ieri. E' sufficiente aggiungere
'typename' nei due punti in cui c'è un riferimento al value_type ?
Questo codice, in sostanza, è accettabile?
 template< typename ForIter > 
  typename iterator_traits< ForIter >::value_type > &
  most_frequent_element( ForIter start, ForIter end )
  {
    ForIter most_freq = start;
    int max_count = 0;
    map< typename iterator_traits< ForIter >::value_type, int> hits;
    for( ForIter i = start; i != end; ++i )
    {
        int & count = hits[ *i ];
        if( max_count < ++count )
        {
            max_count = count;
            most_freq = i;
        }
    }
    return *most_freq;
  }                      
Max

 mi sembra, poiche` manca un typename alla seconda riga.
Ecco, per una volta che il DJGPP si comportava bene... :-(
EMG


A questo punto, indipendentemente dall'aderenza o meno allo standard dei
due compilatori in oggetto, mi piacerebbe capire come rendere standard il
pezzettino di codice che avevo postato ieri. E' sufficiente aggiungere
'typename' nei due punti in cui c'è un riferimento al value_type ?
Questo codice, in sostanza, è accettabile?
    [codice snippato]
Se non mi sbaglio, dovrebbe essere proprio cosi`; cioe`, il codice
teste` ripostato dovrebbe avere corretto la discordanza dallo standard
presente nella versione precedente (che, a mio vedere, era solo la
mancanza di typename).
Potrebbe essere il caso di chiedere ai VERI guru, su comp.std.c++,
perche` io non ho proprio il tempo (e forse neppure la competenza
di estremo dettaglio necessaria...) per verificarlo meglio...!-)
Alex

 paragrafo [24.3.1].
Ribadisco che non c'entra; vedi 14.6, soprattutto il
punto 3 ma anche quelli circonvicini.
Non-normativo, ma forse convincente, l'esempio al
punto 3 di 24.3.1.  ***LO VEDI QUEL typename CHE
E` USATO PER QUALIFICARE**
    iterator_traits<BidirectionalIterator>::value_type
IN QUESTO ESEMPIO***?!
Secondo me quel typename SERVE, cioe` NON e`
stato messo solo per bellezza, e allo stesso identico
modo serve quello che tu vuoi che venga omesso
(perche` il compilatore che cerchi di dimostrare che
"e` standard" non lo richiede...).
Alex

Tanto per infilarmi in mezzo alla discussione (e prender botte da tutti
e due :-), qualche tempo fa l'uso di "typename" e' stato discusso sui
newsgroup Borland dove e' stato detto che la "facoltativita'" di
typename in condizioni particolari e' un estensione Borland.
Ciao,
Nicola

   typename iterator_traits< ForIter >::value_type > &
                                                    ^
... penso che questo sia una svista. In secondo luogo, se assumi che
ForIter sia un iteratore ben formato, non e' sufficiente
ForIter::value_type (per carita', con typename davanti) ?
Ciao,
Nicola

 wrote in message
news:38E99550...@divalsim.it...

Aha, bene.
Quindi, come appunto sostenevo: ironia della sorte!  FF vanta
"quanto e` standard Borland" proprio esibendo un pezzo di
codice che un compilatore standard NON accetterebbe, e quello
Borland invece manda giu` liscio, VIOLANDO gli standard che
gli richiederebbero invece di emettere un messaggio d'errore.
Bello mostrare una VIOLAZIONE dello standard come "prova"
di ADERENZA allo standard. Orwell avrebbe da imparare...
Alex

 wrote in message
news:38E99668...@divalsim.it...

E` piu` generale la forma usata da Max M: essa, infatti,
permette di usare come parametro del template un qualsiasi
T* (per qualsivoglia T), grazie alla specializzazione parziale
di iterator_traits che lo standard prevede per i puntatori; e
inoltre altre arbitrarie classi "simili ma non equipollenti ad
iteratori" se si e` specializzato iterator_traits per esse.
Piu` in generale, l'idioma "Traits" e` fondamentale per l'uso
dei template in C++ (e supportarlo appieno e` la principale
motivazione per l'esistenza delle specializzazioni parziali).
Alex

 
No, perchè ForIter potrebbe essere un T*, nel qual caso quella forma non
andrebbe bene, mentre per iterator_traits<T*> esiste un'apposita 
specializzazione.
Max

fare le "contorsioni", o sputando fuori valanghe di Warning.
Rispondo solo ora perche` ho avuto (ed ho) problemi con
tiscali...
Il fatto che BCB compili un certo pezzo di codice che un altro 
compilatore non compila, non significa che sia standard.
Ripeto... tempo fa sottoposi un pezzo di codice che doveva essere
standard ad una persona che disponeva di BCB 4.0... a quanto mi fu
detto il codice non venne compilato.
Che poi BCB in tutte le altre cose sia standard, non puo` farmi che
piacere...
Paolo
--------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
--------------------------------------------------