Dependência mútua de modelo C++?

Question

Eu gostaria de ter duas estruturas que apontem uma para a outra.Especificamente, gostaria de ter o seguinte:

template<typename Key, typename Value> 
class MyStructure {
public:
  typedef map<Key, list<pair<Value, typename ListType::iterator>>> MapType;
  typedef list<typename MapType::element_type::iterator> ListType;
private:
  MapType map_;
  ListType list_;
}

Obviamente, isso não funcionará, pois ListType não foi declarado anteriormente como um tipo.Como eu poderia fazer isso?Como você pode ver, estou usando os tipos de iteradores como ponteiros para os elementos dessas duas estruturas.

Eu estava pensando em usar o padrão de modelo curiosamente recorrente, mas não consegui chegar a lugar nenhum com isso.Alguém em ##c++ também sugeriu o uso de aliases de modelo, mas também falhou (pelo menos não sei como usar essa ideia).

Estou fazendo algo errado, conceitualmente?Ou talvez "não esteja de acordo com os conceitos de C++"?Eu certamente poderia fazer isso com void*s, mas estou tentando fazer as coisas da maneira certa :)

Obrigado!

Answer 1

Embora eu suspeitasse que isso pudesse ser uma duplicata (e em muitos aspectos é), "Cheers and hth.- Alf" está certo ao apontar que a possível questão duplicada era especificamente sobre o uso de typedef para esse tipo de coisa.

No entanto, na presente questão, o OP gostaria de saber como lidar de forma geral com a inclusão mútua no cenário descrito na questão.

Aqui está uma sugestão:

#include <list>
#include <map>

template <typename Key, typename Value>
class MyElement;

template <typename Key, typename Value>
class MyStructure
{
public:
  typedef std::map<Key,MyElement<Key,Value> > MapType;
  typedef std::list<MyElement<Key,Value> >    ListType;
};

template <typename Key, typename Value>
class MyElement {
public:
  typename MyStructure<Key,Value>::MapType::iterator  map_iterator;
  typename MyStructure<Key,Value>::ListType::iterator list_iterator;
};

Como você pode ver, introduzi um novo tipo de dados MyElement, que contém o iterador de lista e também o iterador de mapa.Como se trata de uma classe e não de um typedef, ela pode ser declarada posteriormente.

Answer 2

Infelizmente, isso não é possível, da forma como você o expressa.

Por outro lado, parece-me que (dadas as suas necessidades) você poderia reverter o armazenamento.

E se você usasse um list do Values, e então o mapa apontava para esta lista?

Isso quebraria a dependência cíclica.

typedef std::list< std::pair<Key, Value> > ListType;
typedef std::multiset<typename ListType::iterator, CmpFirst> MapType;

(Não tenho certeza se realmente entendi o que você estava tentando alcançar...)

Outra solução que você provavelmente deveria considerar é ver se você consegue expressar isso em termos de Boost.MultiIndex.Quando várias iterações/padrões de pesquisa são necessárias, Boost.MultiIndex costuma ser uma alternativa melhor do que a solução artesanal, pois intercala os índices dentro dos valores para minimizar o armazenamento.Além disso, a consistência (ou seja, ter todos os índices referenciando o mesmo conjunto de elementos) é um dado adquirido.