C++ - 删除指针引用的向量元素

Question

好吧，我不知道这是否可能，但问题是：

struct stPiece
{
  /* some stuff */
  stPiece *mother; // pointer to the piece that created this one
};

vector<stPiece> pieces;

是否可以从片段中删除“mother”引用的片段，仅以该指针作为引用？如何？

它会与其他参考资料混淆吗？ （即，如果它不是向量中的最后一个元素，则通过将下一个元素移动到其他内存位置，而其他“*mothers”保持不变）。当然，我假设所有子块都将被删除（因此我不需要更新任何指向同一个母块的指针）。

谢谢！

Answer 1

如果你的mother指针直接指向pieces向量的元素，你将会遇到各种各样的麻烦。

从 pieces 中删除一个元素将会移动索引较高的元素的所有位置。即使插入元素也会使所有指针无效，因为向量可能需要重新分配其内部数组，这可能会将所有元素转移到内存中的新位置。

要回答您的主要问题：您无法直接删除指针指向的元素，您首先需要在向量中搜索以找到它，或者计算它在向量中的索引。

不将指针存储到 pieces 中作为 mother 而是将元素的索引存储起来会使其更加健壮，这样至少插入新元素不会破坏现有的 母亲的。但从 pieces 中删除仍然会将元素转移到新索引。

使用 std::list 作为 片段并将迭代器存储到其中作为mother可能是一个解决方案。如果删除/添加该列表中的其他元素，std::list 的迭代器不会失效。如果不同的元素可以具有相同的 mother ，那么您仍然无法确定何时删除 mother 元素，而不是使用 boost::shared_ptr 会更简单。

Answer 2

目前尚不清楚整个数据结构是如何组织的以及会产生什么后果，但完全有可能通过指向该元素和向量本身的指针来从向量中删除该元素。您只需首先将指针转换为迭代器即可。例如，拥有一个向量

vector<stPiece> pieces; 

和一个指向该向量的指针，

stPiece *mother;

您可以将指针转换为索引

vector<stPiece>::size_type i = mother - &pieces[0];
assert(i < pieces.size());

，然后将索引转换为迭代器

vector<stPiece>::iterator it = pieces.begin() + i;

，然后擦除元素

pieces.erase(it);

，仅此而已。

但是，在您的数据结构中，您可能有多个长期存在的指针指向同一个向量。任何从此类向量中删除元素的尝试都会立即使所有这些指针无效。理论上，如果你小心翼翼地做每件事，是可以“恢复”它们的有效性的，但这将影响到一个主要的 PITA。

我不确定我是否理解“假设所有子片段都将被删除”的意思。

Answer 3

是的，你可以删除妈妈引用的那篇文章。

如果您删除“mother”引用的块，则其所有子项中的mother 指针将变得悬空，您必须注意这一点。

关于向量中元素的移动，你不需要这样做，它由向量类处理。

Answer 4

简短的回答：不。

这些片段按值存储在向量中。因此，向量迭代器是指向片段的指针。这意味着，指向母块的指针与母块处向量的迭代器相同。向量迭代器在插入（所有迭代器）和擦除（所有经过擦除迭代器的迭代器）时无效，这意味着内存位置将发生变化，并且几乎不可能保持所有指针更新。

您可以在向量中存储动态分配的片段，即：

vector<stPiece*> pieces

当向向量添加片段或从向量中删除片段时，母指针不会改变。缺点是：

• 您现在必须管理内存（新建/删除每个片段），
• 每个片段使用更多内存（片段中的指针），
• 它可能会变慢，因为您失去了空间局部性（缓存效率），因为它不再是连续的数组stPiece 对象的组成

后两点在您的应用程序中可能很重要，也可能不重要。

Answer 5

您编写的代码是一棵单链接树。您可能不希望一个对象包含所有 stPiece，因为这会妨碍实现创建和删除语义。

我猜您想在所有孩子都消失后删除mother。

set< stPiece * > all_pieces;

struct stPiece {
    boost::shared_ptr< stPiece > const mother;
    stPiece( boost::shared_ptr< stPiece > &in_mother )
     : mother( in_mother ) {
        all_pieces.insert( this );
    }
    ~stPiece() {
        all_pieces.erase( this );
    }
};

关键点是包含某些对象和仅仅能够迭代它们之间是有区别的。如果使用最明显的方式创建和删除对象不使用容器，那么它们可能不应该在其中。