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

Question

嗯，我不知道这是否可能，但事情是这样的：

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

vector<stPiece> pieces;

有没有可能仅凭'mother'这个指针作为参考，从pieces中删除相应的元素？如何操作？

这样做会不会影响其他引用？（例如，如果它不是向量中的最后一个元素，则通过将下一个元素移动到其他内存位置，而其他 '*mothers' 保持不变）。当然，我假设所有子元素都将被删除（因此我不需要更新任何指向相同母亲的指针）。

谢谢！

- huff

---

你在做什么？如果你想删除元素而不影响其他元素，你可以尝试使用“列表”（list）代替。 - GManNickG

+1 GMan：说真的，你正在把工作复杂化！使用std::list或创建自定义链表类将是你所需要的...而不是一个向量。你为什么要尝试做这样的事情呢？ - Partial

没错，我会使用列表和迭代器，这也引出了另一个问题。谢谢大家！ - huff

Answer 1

整个数据结构的组织方式以及可能的后果并不十分清楚，但是通过具有指向该元素和向量本身的指针，完全可以从向量中删除一个元素。你只需要首先将指针转换为迭代器即可。例如，有一个向量

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);

就是这样。

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

我不确定我理解你所说的“假设所有子部分都将被删除”的意思。

- AnT stands with Russia

---

谢谢。看到它可以使用向量编程真是太好了，但正如许多答案所建议的那样，这可能需要另一种数据结构。当我说“假设所有子片段都将被删除”时，我指的是在销毁母体时销毁所有具有该母体的零件（以此类推，侄女们等等）。干杯！ - huff

Answer 2

如果您的母指针直接指向 pieces 向量的元素，您将遇到各种麻烦。

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

回答您的主要问题：您不能直接删除指向的元素，您需要先在向量中搜索该元素或计算出其在向量中的索引。

不将母指针存储为 pieces 的指针，而是存储元素的索引会使其更加健壮，因此至少插入新元素不会破坏现有的母指针。但是，从 pieces 中删除仍将使元素移动到新索引。

使用std::list来存储pieces并将其迭代器存储为mother可能是一个解决方案。如果从列表中删除/添加其他元素，则不会使std::list的迭代器失效。如果不同的元素可以有相同的mother，则仍然需要找出何时删除mother元素，那么使用boost::shared_ptr可能会更简单。

- sth

---

实际上，你可以直接使用“pieces.erase(the_piece.mother);”从向量中删除元素，因为指针与该片段的向量迭代器相同。然而，主要问题（无效）仍然存在，因为片段在向量中移动位置。 - Jason Govig

@Jason：是的，通常情况下应该是这样，但这只是向量类的一种实现细节，并不能完全保证。 - sth

@sth：你说得对，这是一些实现细节。然而，向量很可能被实现为数组，它们的迭代器是指针。Scott Meyers的《Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library》讨论了如何将向量数据传递给遗留（基于指针的）API，并建议使用&v[0]来获取指针。因此，即使迭代器不是指针，您也可以使用“mother - &pieces[0]”来获取删除的索引。但是，这两种技术都是我会避免使用的 ;) - Jason Govig

@Jason：你不能真的将指针用作向量的迭代器，虽然在STL的某些实现中可能是有效的，但在其他情况下则不是（例如，VS具有依赖于编译时选项的已检查迭代器，并且这些迭代器具有返回到容器的引用以检测修改）。 - David Rodríguez - dribeas

将迭代器计算为 std::advance(v.begin(), mother-&v[0]) 是更好的解决方案。指针算术是可靠的，并且将提供迭代器在数组中的位置，将该偏移量应用于起始迭代器将提供有效的迭代器（也就是说，在修改向量本身时忽略所有可能发生的迭代器/指针无效）。 - David Rodríguez - dribeas

Answer 3

简短回答：不行。

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

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

vector<stPiece*> pieces

当向量中添加/删除元素时，母指针不会改变。缺点是：

• 现在您必须管理内存（每个元素都要使用new/delete）
• 每个元素使用更多的内存（pieces中的指针）
• 它可能会变慢，因为您失去了空间局部性（缓存效率），因为它不再是一个连续的stPiece对象数组

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

- Jason Govig

---

如果他已经将指针存储在非C++图/树结构中，将它们存储在向量中将会有害。 - Potatoswatter

@Potatoswatter：使用图形数据结构时，通常需要一个节点的主列表（例如，pieces向量）。如果您无法从单个起始节点引用完整的图形（例如，考虑由多个未连接的子图组成的图形），这一点尤其重要。 - Jason Govig

哦，你说得对；我不确定我当时在想什么。我在我的回答中推荐了一个集合而不是一个向量... - Potatoswatter

Answer 4

你所编写的是一个单向链表。你可能不想让一个对象包含所有的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 );
    }
};

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

- Potatoswatter

---

我想我太习惯C，对OOP不是很擅长。问题在于之后我会按线性方式访问数据，而不是树结构本身，而是元素本身。但我认为这并不重要，因为可以编写函数以顺序访问它。此外，当母对象被删除时（现在我自相矛盾），我需要有选项使子对象保持活动状态，当然是孤儿...所以也许它们不应该包含在母对象的结构中。谢谢。 - huff

Answer 5

可以删除由 "mother" 引用的代码块。

如果删除由 "mother" 引用的代码块，则其所有子元素中的 mother 指针 都将变为悬空指针，您需要注意这一点。

关于向量中元素的移位，您不需要自己处理，因为向量类已经处理好了。

- codaddict

---

嗨，谢谢你的回复...那么...你会如何编码呢？移位可能会破坏其他引用，这意味着其他指针将变得无效，不是吗？ - huff

@huff：确切地说，它们将无效。如何修复？这取决于您希望在母亲去世后成为孩子母亲的人是谁？如果没有人，您可以将母亲指针设置为NULL。如果您希望祖母成为新的母亲，您可以在删除母亲之前将孩子的母亲指针更改为指向祖母。 - codaddict

问题比需要更新的悬空指针（即可能有相同母体的其他部分）更为严重。当删除母体时，向量中其他部分的移动可能会影响具有不同母体的其他部分。 - Jason Govig