data-structures - estructura - ejemplo de colas
Implementar una estructura de datos de tipo gráfico en Rust (3)
En realidad, para una estructura de tipo gráfico, la solución más simple es usar un escenario como TypedArena .
La duración de los nodos dependerá únicamente de la duración de la instancia de la arena tipada desde la que se crearon, lo que simplificará enormemente la gestión de los recursos.
Advertencia : evite una situación en la que agregue / elimine dinámicamente nodos en el gráfico, ya que los nodos NO se eliminarán de la arena hasta que se suelte dicha arena, por lo que el tamaño de la arena crecerá, sin límites.
Si se encuentra en una situación en la que agregará / eliminará nodos en el tiempo de ejecución, otra solución es:
- tener una colección de
Resources - los bordes solo se refieren indirectamente a los
Resources(no a los propietarios, ni tampoco a los prestatarios)
Dos ejemplos:
-
HashMap<ResourceId, (Resource, Vec<ResourceId>)> -
type R = RefCell<Resource>,Vec<Rc<R>>yVec<(Weak<R>, Vec<Weak<R>>)>
en cualquier caso, usted es responsable de limpiar los bordes al eliminar un recurso, y el olvido puede provocar una pérdida de memoria y pánico (al desreferenciar) pero, de lo contrario, es seguro.
Hay, probablemente, infinitas variaciones en lo anterior.
Tengo una estructura de datos que se puede representar como un gráfico unidireccional entre algunas estructuras vinculadas con objetos de enlace porque los enlaces contienen metadatos.
Se ve algo como esto:
struct StateMachine {
resources: Vec<Resource>,
links: Vec<Link>,
}
struct Resource {
kind: ResourceType,
// ...
}
enum LinkTarget {
ResourceList(Vec<&Resource>),
LabelSelector(HashMap<String, String>),
}
struct Link {
from: LinkTarget,
to: LinkTarget,
metadata: SomeMetadataStruct,
}
Toda la estructura debe ser mutable porque necesito poder agregar y eliminar enlaces y recursos en tiempo de ejecución. Debido a esto, no puedo usar el modelo de vida normal y vincular los recursos a la vida de la estructura principal.
Entiendo que debo "elegir mi propia garantía" eligiendo el tipo apropiado, pero no estoy seguro de cuál es la mejor manera de resolver este problema.
Modelar estructuras similares a gráficos en Rust no es un problema simple. Aquí hay dos discusiones valiosas de Nick Cameron y Niko Matsakis (dos desarrolladores principales de Rust en Mozilla).
La solución más simple para una estructura tipo gráfico es usar una biblioteca que modele gráficos . Petgraph es una buena opción:
extern crate petgraph;
use std::rc::Rc;
use std::collections::HashMap;
use petgraph::Graph;
struct Resource;
enum LinkTarget {
ResourceList(Vec<Rc<Resource>>),
LabelSelector(HashMap<String, String>),
}
struct SomeMetadataStruct;
fn main() {
let mut graph = Graph::new();
let n1 = graph.add_node(LinkTarget::LabelSelector(Default::default()));
let n2 = graph.add_node(LinkTarget::LabelSelector(Default::default()));
let l2 = graph.add_edge(n1, n2, SomeMetadataStruct);
}
Las garantías que tiene que elegir aquí se centran en el miembro de ResourceList . Supongo que desea tener Resource compartidos inmutables de un solo hilo.
- si necesita compartirlos entre subprocesos, use un
Vec<Arc<Resource>> - si no se comparten,
Vec<Resource>-Vec<Resource> - si necesitan ser mutables, use un
Vec<Rc<RefCell<Resource>>>(O unMutexsi también es multihilo)