Comment casser ce typedef circulaire?

Je veux déclarer deux types (internes à une classe templated sur K et V et en fournissant un comportement de mise en cache):Comment casser ce typedef circulaire?

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;

Bien sûr, ce n'est pas possible est, en raison de la définition circulaire . Je pourrais le bidouiller avec un void*, mais je me demande s'il y a de la magie de déclaration avancée ou une autre technique qui fera mieux le travail.

(Oui, je sais qu'un boost::bimap contournerait le problème).

Source

2010-11-12 timday

Essayez-vous de créer une carte avec des données, puis un index de cette carte dans un ordre différent? –

La question a été soulevée alors que je me trompais avec un code de mise en cache LRU qui fonctionnait déjà (essentiellement une carte de valeur-clé complétée par un suivi afin que les enregistrements les moins récents puissent être purgés si nécessaire). La version originale a la valeur de chaque carte contenant le type de clé de l'autre carte, mais certains accès O (log n) peuvent être écrasés pour diriger les accès de l'itérateur en utilisant le formulaire ci-dessus. Mais je ne veux pas que cette question devienne un débat sur les mérites des implémentations de cache LRU! C'était plus que je me suis rendu compte que je ne savais pas comment gérer ce genre de problème typedef/forward-declaration. – timday

+1 C'est une bonne question. Si seulement je savais quel est le type que vous voulez exprimer. – wilhelmtell

Il est impossible, pensez à ce que les types seraient:

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 ...

Ce n'est pas un problème avec les déclarations avant, vous êtes simplement essayer de décrire un type qui est défini de manière récursive sur lui-même. Ce n'est pas différent de:

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

La seule façon de contourner ce problème est de perdre des informations de type statique. Comme vous l'avez dit, vous pouvez utiliser void*, ou vous pouvez essayer de définir votre propre interface abstraite, effacée par type. Votre choix.

Source

2010-11-12 22:38:37

n'est-ce pas plus comme si chaque structure avait des pointeurs vers l'autre structure? Il a des itérateurs, pas le type en lui-même, donc je ne pense pas que le problème réside dans ce – rtpg

les itérateurs ne sont pas nécessairement un pointeur. Ils peuvent être, et sont souvent, des classes. Peter a raison dans son analyse. –

Il a T = map où le type de B est défini en termes de T. Il n'est pas structurellement récursif comme mon analogie, mais les types sont récursifs, et C++ ne supporte pas les types récursifs. –

Briser la définition circulaire avec une seule d'entre elles contenant V et l'autre contenant le iterator:

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

Si vous avez besoin d'utiliser une clé pour rechercher un horodatage, et que l'horodatage ne sont pas stockées en V, alors vous pouvez dupliquer que KVMap:

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

D'un K, vous pouvez utiliser KVMap :: trouver, obtenir l'horodatage, puis utilisez TSMap :: trouver et obtenir une poignée sur l'élément correspondant (par exemple pour l'effacer).

Source

2010-11-13 00:17:24

Répondre

Questions connexes