Come rompere questo typedef circolare?

Voglio dichiarare un paio di tipi (interni a una classe su modelli su K e V e fornendo qualche comportamento della cache):Come rompere questo typedef circolare?

typedef std::map< 
    long long, 
    typename key_to_value_type::iterator // Ooops... not declared yet 
> timestamp_to_key_type; 

typedef std::map< 
    K, 
    std::pair<V,typename timestamp_to_key_type::iterator> 
> key_to_value_type;

Naturalmente questo non è possibile in quanto è, a causa della definizione circolare . Potrei hackerarlo con un void*, ma mi chiedo se ci sia qualche magia in avanti o altra tecnica che farà meglio il lavoro.

(Sì, so che uno boost::bimap aggirerebbe il problema).

fonte

2010-11-12 timday

Stai cercando di creare una mappa con i dati e quindi un indice di quella mappa in un ordine diverso? (Presumibilmente per una rapida consultazione) –

La domanda è venuta fuori mentre stavo scherzando con un codice di cache LRU già funzionante (fondamentalmente una mappa valore-chiave integrata con il tracciamento in modo che i record utilizzati meno di recente possano essere eliminati quando necessario). La versione originale ha il valore di ogni mappa per contenere il tipo di chiave dell'altra mappa, ma alcuni accessi O (log n) potrebbero essere schiacciati per dirigere gli accessi iteratore usando il modulo sopra. Ma non voglio che questa domanda si trasformi in un dibattito sui meriti delle implementazioni della cache di LRU! È stato più che mi sono reso conto che non sapevo come gestire al meglio questo tipo di problema typedef/forward-declaration. – timday

+1 Questa è una buona domanda. Se solo sapessi qual è il tipo che stai cercando di esprimere. – wilhelmtell

Non è possibile, considerare che cosa sarebbero i tipi:

timestamp_to_key_type 
= map< long long, key_to_value_type::iterator > 
= map< long long, map< K, pair< V, timestamp_to_key_type::iterator > >::iterator > 
= map< long long, map< K, pair< V, map< long long, map< K, pair< V, map< long long, map< K, pair < V ...

Questo non è un problema con le dichiarazioni previsionali, si sono semplici cercando di descrivere un tipo che viene definita ricorsivamente su se stessa. Non è diverso da:

struct A { B b; }; 
struct B { A a; };

L'unico modo per aggirare questo è quello di perdere alcune informazioni di tipo statico. Come hai detto, puoi usare void* oppure puoi provare a definire la tua interfaccia astratta, cancellata dal tipo. La tua scelta.

fonte

2010-11-12 22:38:37

non è più come avere ogni struttura ha puntatori all'altra struttura? Ha degli iteratori, non il tipo in sé, quindi non penso che il problema risieda nel fatto che gli iteratori – rtpg

non sono necessariamente un puntatore. Possono essere, e spesso sono, classi. Peter ha ragione nella sua analisi. –

Ha T = map dove il tipo di B è definito in termini di T. Non è strutturalmente ricorsivo come la mia analogia, ma i tipi sono ricorsivi, e il C++ non supporta i tipi ricorsivi. –

Rompere la definizione circolare con uno solo di essi contiene il V e l'altra contenente l'iteratore:

typedef map<K, V> KVMap; 
typedef map<long long, typename KVMap::iterator> TSMap;

Se è necessario utilizzare una chiave per cercare un timestamp, e che timestamp non viene memorizzata in V, allora è possibile duplicare che nel KVMap:

typedef map<K, pair<V, long long> > KVMap;

Da un K, è possibile utilizzare KVMap :: trovare, ottenere il timestamp, e quindi utilizzare TSMap :: trovare e ottenere un handle sulla voce corrispondente (ad esempio per cancellarlo).

fonte

2010-11-13 00:17:24

Come rompere questo typedef circolare?

risposta

Problemi correlati