Quando é aceitável uma referência circular a um ponteiro pai?

Esta pergunta sobre estouro de pilha é sobre um filho que faz referência ao pai, por meio de um ponteiro.

Os comentários foram bastante críticos inicialmente, pois o design era uma ideia horrível.

Entendo que essa provavelmente não seja a melhor ideia em geral. De uma maneira geral, parece justo dizer: "não faça isso!"

No entanto, estou imaginando que tipos de condições existiriam onde você precisaria fazer algo assim. Esta pergunta aqui e as respostas / comentários associados sugerem que mesmo os gráficos não façam algo assim.

A chave aqui não é se dois objetos têm referências circulares, mas se essas referências indicam propriedade um do outro.

Dois objetos não podem ser "proprietários" um do outro: isso causa um dilema intratável para a ordem de inicialização e exclusão. Um deve ser uma referência opcional ou, de outra forma, indicar que um objeto não gerenciará a vida útil do outro.

Considere uma lista duplamente vinculada: dois nós se ligam um ao outro, mas nenhum "possui" o outro (a lista possui os dois). Isso significa que nenhum nó aloca memória para o outro ou é responsável pelo gerenciamento de identidade ou vida útil do outro.

As árvores têm um relacionamento semelhante, embora os nós de uma árvore possam alocar filhos e os pais possuam filhos. O link de um filho para o pai ajuda na travessia, mas novamente não define a propriedade.

Na maioria dos projetos de OO, uma referência a outro objeto como membro de dados de um objeto implica propriedade. Por exemplo, suponha que tenhamos as classes Car e Engine. Nenhum dos dois é muito útil por si só. Podemos dizer que esses objetos dependem um do outro: eles exigem a presença do outro para realizar um trabalho útil. Mas qual é o "dono" do outro? Nesse caso, diríamos que o carro possui motor porque o carro é o "contêiner" no qual vivem todos os componentes automotivos. Tanto no design OO quanto no mundo real, o carro é a soma de suas partes e todas essas partes são conectadas no contexto do carro. O mecanismo pode ter uma referência de volta ao carro ou uma referência ao TorqueConverter,

Referências circulares podem ser um mau cheiro para o design, mas não necessariamente. Quando usados ​​criteriosamente e documentados corretamente, eles podem facilitar o uso de estruturas de dados.

Tente atravessar uma árvore sem referências nos dois sentidos entre pais e filhos. Claro, você pode criar uma abordagem baseada em pilha que seja quebradiça e complexa, ou você pode usar a abordagem baseada em referência que é trivialmente simples.

Existem vários aspectos a considerar em um design como esse:

• as dependências estruturais
• a relação de propriedade (composição i vs. outro tipo de associação)
• as necessidades de navegação

Dependência estrutural entre classes:

Se você pretende reutilizar classes de componentes, evite dependência desnecessária e estruturas circulares fechadas.

No entanto, às vezes duas classes são conceitualmente fortemente interligadas. Nesse caso, evitar a dependência não é uma opção real. Exemplo: uma árvore e suas folhas, ou mais geralmente um composto e seus componentes .

Propriedade dos objetos:

Um objeto possui o outro? Ou de outra forma: se um objeto for destruído, o outro também será destruído?

Este tópico foi abordado em profundidade pelo Snowman, portanto não o abordarei aqui.

Necessidades de navegação entre objetos:

Uma última questão é a necessidade de navegação. Vamos dar o meu exemplo favorito, o padrão de design composto do Gang of four .

Gama e outros. mencione explicitamente a necessidade potencial de ter uma referência pai explícita: " Manter a referência dos componentes filhos para seus pais pode simplificar a travessia e o gerenciamento de uma estrutura composta " É claro que você pode imaginar uma travessia sistemática de cima para baixo, mas para objetos compostos muito grandes pode desacelerar significativamente as operações e de maneira exponencial. Uma referência direta, mesmo circular, pode facilitar significativamente a manipulação de seus compósitos.

Um exemplo pode ser um modelo gráfico de um sistema eletrônico. Uma estrutura composta pode representar as placas eletrônicas, circuitos, elementos. Para exibir e manipular o modelo, você precisará de alguns proxies geométricos em uma visualização da GUI. Portanto, é certamente muito mais fácil navegar do elemento GUI selecionado pelo usuário para o componente, descobrir qual é o pai e com os elementos irmão / irmã relacionados, do que iniciar uma pesquisa de cima para baixo.

Obviamente, como Gamma e cols. Apontaram, você deve garantir os invarientes do relacionamento circular. Isso pode ser complicado, como a pergunta SO a que você se refere mostrou. Mas é perfeitamente gerenciável e de maneira segura.

Conclusão

A necessidade de navegação não deve ser subestimada. Não é sem razão que a UML o abordou explicitamente na notação de modelagem. E sim, há uma situação perfeitamente válida em que referências circulares são necessárias.

O único ponto é que, às vezes, as pessoas tendem a ir nessa direção rapidamente. Portanto, vale a pena considerar todos os três aspectos envolvidos antes de tomar a decisão de fazê-lo ou não.

Geralmente, as referências circulares são uma péssima idéia, porque significam dependências circulares. Você provavelmente já sabe por que as depedências circulares são ruins, mas, para completar, a versão tl; dr é que sempre que as classes A e B dependem uma da outra, é impossível entender / corrigir / otimizar / etc, A ou B sem também entender / consertar / otimizar / etc a outra classe ao mesmo tempo. O que leva rapidamente a bases de código onde você não pode alterar nada sem alterar tudo.

No entanto, é possível ter uma referência circular sem criar dependências circulares ruins. Isso funciona desde que a referência seja estritamente opcional em um sentido funcional. Com isso, quero dizer que você poderia removê-lo facilmente das classes e elas ainda funcionariam, mesmo que funcionassem mais devagar. O principal caso de uso que eu conheço para essas referências circulares de criação de não dependência é permitir a passagem rápida de estruturas de dados baseadas em nós, como listas vinculadas, árvores e pilhas. Por exemplo, em princípio, qualquer operação que você pode executar em uma lista duplamente vinculada, você também pode executar em uma lista vinculada unicamente, acontece que existem algumas operações (como retroceder na lista) que têm um tamanho muito melhor. O com a versão duplamente vinculada.

O motivo pelo qual geralmente não é uma boa idéia fazer isso é porque ele viola o Princípio de Inversão de Dependência . As pessoas escreveram muito sobre isso com muito mais detalhes do que eu posso abordar adequadamente neste post, mas tudo se resume a dificultar a manutenção, porque o acoplamento é muito apertado. Alterar uma classe quase sempre exige uma mudança na outra, enquanto que se as dependências apontarem apenas para um lado, as alterações de um lado da interface serão isoladas. Se ambas as classes apontam para uma interface abstrata, melhor ainda.

A única exceção principal é quando você não tem duas classes diferentes em diferentes níveis de abstração, mas dois nós da mesma classe, como em uma árvore, uma lista duplamente vinculada etc. Aqui é mais um relacionamento estrutural do que um relacionamento de abstração. Referências circulares em prol da eficiência algorítmica são aceitáveis ​​e até encorajadas nesses tipos de casos.

[...] sugere até que os gráficos não façam algo assim.

Às vezes, você só precisa acessar as coisas de baixo para cima a partir de uma estrutura de dados diferente da árvore, enquanto a árvore precisa acessar as coisas de cima para baixo.

Como exemplo, um quadtree pode armazenar elementos em um software de gráficos vetoriais. No entanto, a seleção do usuário é armazenada em uma lista de seleção separada de referências / ponteiros de elementos vetoriais. Quando o usuário deseja excluir essa seleção, temos que atualizar o quadtree, e pode ser muito mais eficiente atualizar a árvore de baixo para cima, começando pelas folhas e não de cima para baixo. Caso contrário, você precisará, para cada elemento, trabalhar da raiz para a folha e fazer backup novamente.

Doom 3 tem um exemplo de um objeto filho com um ponteiro para um objeto pai. Especificamente, ele usa listas intrusivas . Para resumir, uma lista intrusiva é como uma lista vinculada, exceto que cada nó contém um ponteiro para a própria lista.

Vantagens:

• Quando objetos podem existir em várias listas simultaneamente, a memória para os nós da lista precisa ser alocada e desalocada apenas uma vez.

• Quando um objeto precisa ser destruído, você pode removê-lo facilmente de todas as listas em que está, sem pesquisar cada uma das listas de maneira linear.

Acho que esse é um cenário bastante específico, mas se entendi sua pergunta, é um exemplo de uso aceitável de um objeto filho que contém um ponteiro para o objeto pai.