我有一个基于对象的邻接列表图，它由存储在vector中的nodes和edges组成。
class Graph
{
struct NodePrivate
{
QVector<int> m_FromEdges, m_ToEdges;
};
struct EdgePrivate
{
int m_iFrom, m_iFromIndex, m_iTo, m_iToIndex;
};
//...
private:
QVector<NodePrivate> m_Nodes;
QVector<EdgePrivate> m_Edges;
};
为了确保移除时图形元素的连续性(和恒定速度)，我通过将最后一个元素与要移除的元素交换来进行移除。
现在，当图的用户访问元素时，他通过Node和Edge类进行访问，这些类实际上只是图(和int)索引的包装器。
class Item
{
//...
private:
int m_Index = -1; //or QSharedPointer<int>, see below
const Graph *m_Graph = nullptr;
};
class Node : public Item {};
class Edge : public Item {};
通过移除node或edge，这些索引可能会变得无效。我希望这些是持久的，并且已经尝试了(成功的)两种策略，但我不太喜欢它们中的任何一种：
1) 通过分别在构造函数和析构函数中注册和注销Node和Edge类型的所有对象来跟踪它们。然后，每当相关索引发生变化时，就会使用这些索引来更新内部索引。这样做最大的缺点是有很多不必要的临时登记。
2) 另一种选择是通过使索引动态(std::shared_ptr<int>)来使用智能指针方法。然后通过更新索引，这可以说比更新所有对象更好，但要以动态内存为代价。
有没有其他选择来实现这一点或改进这两种设计？
首先，我必须承认，我认为这个问题不能完美地解决。如果您真的想定期对图形进行大量的小更改，那么您应该切换到将所有内容存储在链表中，而不是数组中。此外，您可以放弃并明确地说，所有Node和Edge句柄都是无效的，就像向std::vector添加元素时std::vector::iterator-s是无效的一样。
一般性讨论
在您的情况下，顶点和邻接列表存储在阵列中。此外，您还有Node和Edge辅助对象，允许用户随时指向实际节点和边。我将把它们称为句柄(它们就像没有任何迭代功能的C++迭代器)。我看到了在更改后维护句柄的两种不同方法。
第一种方法是在每个句柄中存储指向物理对象的直接指针(或索引)，就像现在所做的那样。在这种情况下，无论何时移动对象，都必须更改对象的所有控制柄。这就是为什么你必须在某个地方注册你提供的所有句柄。这正是您建议的第一个解决方案，它会导致"沉重"的句柄：无论是否实际移动了任何对象，创建、删除和复制句柄的成本都会很高。
第二种方法是将指向某个中间事物的指针存储在Handle中。然后确保在对象的生存期内，即使对象移动，这个东西也不会被更改。很明显，句柄中指向的对象必须与边节点的实际物理索引不同，因为它们会发生变化。在这种方法中，每次取消引用句柄时都必须为间接访问付费，因此句柄访问量会稍微增加一些。
您提出的第二个解决方案是遵循第二种方法。中间事物(由句柄指向)是动态分配的int-s，封装在shared_ptr中，每个对象永远不会移动int。对于每个创建的对象，您至少要经历单独的动态分配(+deallocation)，以及引用计数器更新。引用计数器可以很容易地删除：在NodePrivate和EdgePrivate对象中存储unique_ptr-s，在Node和Edge对象中存储原始指针。
新方法
遵循第二种方法的另一种解决方案是使用ID作为指向句柄的中间事物。无论何时创建节点，都要为其指定一个新的节点ID，对于边也是如此。按顺序分配ID，从零开始。现在，您可以维护物理索引和这些ID之间的双向对应关系，并在更改时在O(1)时间内更新它。
struct NodePrivate
{
QVector<int> m_FromEdges, m_ToEdges;
int id; //getting ID by physical index
};
struct EdgePrivate
{
int m_iFrom, m_iFromIndex, m_iTo, m_iToIndex;
int id; //getting ID by physical index
};
private:
QVector<NodePrivate> m_Nodes;
QVector<EdgePrivate> m_Edges;
QVector<int> m_NodeById; //getting physical index by ID
QVector<int> m_EdgeById; //getting physical index by ID
请注意，这些新的m_NodeById和m_EdgeById矢量在创建对象时会增长，但在删除对象时不会收缩。因此，这些数组中有空单元格，只有在删除图形时才会释放这些单元格。因此，只有当您确信在图的生命周期中创建的节点和边的总量相对较小时，才能使用此解决方案，因为每个这样的对象需要4字节的内存。
提高内存消耗
您可能已经注意到了刚才提出的新解决方案和基于shared_ptr的解决方案之间的相似性。事实上，如果我们不区分C指针和数组索引，那么它们是相同的，只是：在您的解决方案中，int-s是在堆中分配的，但在所提出的解决方案中将int-s分配在池分配器中。
对无空闲池分配器的一个非常著名的改进是称为"空闲列表"的技术，我们可以将其应用于上述解决方案。我们不总是为创建的对象分配新的ID，而是允许重用它们。为了实现这一点，我们存储了一个空闲ID堆栈，当一个对象被移除时，我们将其ID添加到该堆栈中。当创建一个新对象时，我们从堆栈中获取它的ID。如果堆栈为空，则我们分配一个新的ID。
struct EdgePrivate
{
int m_iFrom, m_iFromIndex, m_iTo, m_iToIndex;
int id; //getting ID by physical index
};
private:
QVector<EdgePrivate> m_Edges;
QVector<int> m_EdgeById; //getting physical index by ID
QVector<int> m_FreeEdgeIds; //freelist: stack of IDs to be reused
这一改进确保了内存消耗与同时活动的对象的最大数量成比例(而不是创建的对象总数)。当然，它会进一步增加每个对象的内存开销。它为您节省了malloc/免费成本，但在多次操作后，大型图的内存碎片可能会出现问题。