Newsgroup: it.comp.lang.c++
Titolo: Domanda su standard

Come sono implementate le map e std::sort() nello standard???
Cioe che algoritmo e sort()???
E le map sono implementate che Hash????
Tnk
-- 
Kleidemos
C++ Programmer
kleidemo...@altervista.org
http://kleidemos.altervista.org/

  E le map sono implementate che Hash????
Se non sbaglio, lo standard non obbliga nessuna implementazione,
fornisce solo dei vincoli come complessita' computazionale.
Cmq, per sapere come sono implementate sulla tua implementazione delle
librerie standard, direi di guardare la loro documentazione. Ad es., in
quelle GNU se non sbaglio e' specificata l'implementazione (ma potrei
sbagliare).
-- 
/**
 * Mattia Belletti - Undergraduate student @ 
cs.unibo.it
 * ICQ: 33292311   - email: 
mbel...@cs.unibo.it
 * IRC: BluShine   - site(s): 
http://cs.unibo.it/~mbellett
 * Linux registered user 299762 @ Linux registered machine 184987
 */

 Se non sbaglio, lo standard non obbliga nessuna implementazione,
Non sbagli. ;-)
-- 
---
*************** | Have you ever retired a human by mystake?
*** Azathot *** |
*************** | To contact me, ask me gently. Thanks.

 fornisce solo dei vincoli come complessita' computazionale.
Davvero?


 Come sono implementate le map e std::sort() nello standard???
Estratto da "
http://www.sgi.com/tech/stl/complexity.html
":
STL Complexity Specifications
STL container, algorithm, and concept specifications include asymptotic 
complexity specifications. For example, iterators are required to take 
constant time, that is the time required by an iterator operation should be 
no more than a fixed constant, independent of the size of the container to 
which it refers. 
Clearly programs will still function if a program component ignores the 
complexity specifications. Nonetheless, these specifications are an 
important part of the interface between STL components and code that uses 
them. If they are ignored, the performance of the resulting program will 
often render it useless. 
[...]
Concept specifications (e.g. Forward Iterator or Container) specify 
complexity requirements that should be met by all instances of the concept. 
This is the minimum behavior required by operations (e.g. sort) 
parameterized with respect to the concept. Any specific instance (e.g. 
vector) is likely to perform better in at least some cases. 
[...]
Algorithms specify either worst-case or average case performance, and 
identify which. Unless otherwise stated, averages assume that container 
elements are chosen from a finite type with more possible values than the 
size of the container, and that container elements are independently 
uniformly distributed. 
[...]
Ciao!


 E le map sono implementate che Hash????
Eh? Che italiano e' questo?!
Ad ogni modo pensavo di averti risposto nel post:
http://groups.google.it/groups?hl=it&lr=&ie=UTF-8&selm=bsrmcl%24t0c%241%40hercules.btinternet.com&rnum=12
quando ho detto:
<QUOTE>
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).
</QUOTE>
Magari vuoi rileggerti quel post per intero....
Tommy

 Davvero?
Che domanda e'? 
Non credo Mattia si diverta a dire cose che sa essere false...
Ovvio che lui crede siano vere!!
Poi il "se non sbaglio" e' per addossarsi meno responsabilita', in un
certo senso, visto che non e' pronto a metterci la mano sul fuoco!
IMHO non credo affatto che lui sbagli (anche questo e' un modo per
prendersi meno responsabilita';-), lol!
Il discorso e' pero' che i "vincoli di complessita' computazionale"
spesso non lasciano grande possibilita' di scelta; spesso la scelta e'
molto ristretta. Come ad esempio per le map...
Tommy
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG