如何在c++中实现这个数据结构

Question

我正在从 C#/Java 转向 C++，但我无法找到正确的做事方式。

我正在构建一种数据结构来支持算法和功能。所以假设一个外部对象持有一个 std::vector<Widget> vecW 和一个 std::vector<Vidget> vecV。它创建了一些 Widget 类型的对象，并将它们添加到 vecW。它随后生成了 Vidget 的多个实例，并将它们添加到 vecV。（以防万一：为这些对象分配的内存应该在 外部对象 被销毁时释放。）

现在，有一些自定义逻辑规定，对于列表中每个类型 Widget 的对象，它需要访问某些类型 Vidget 的对象。（反之亦然，如果 widget w 可以访问 vidget v，那么 vidget v 需要访问 widget w。）

在 C# 中，我会在每个 Widget 中保留一个 List<vidget> ListOfVidgets，在每个 Vidget 中保留一个 List<Widget> ListOfWidgets，并根据自定义逻辑实例化这些列表.类似于 Java（我相信 C# 中的 List<Vidget> 类似于 java 中的 arraylist<Vidget>，有点像 C++ 中的 std::vector<Vidget*>/std::vector<Vidget>。

所以我可以在每个小部件中使用 std::vector<Vidget*>，根据自定义逻辑进行实例化。这是最好的方法吗？或者是否有首选的智能指针方法（或什至其他方法）？

编辑：生命周期如下：1) 创建并填充外部对象（widgets/vidgets）。 2) 自定义逻辑决定关系。 3）使用数据结构。（所以在使用过程中没有改变关系 and/or added/removed 小部件。） 4）（仅）当外部对象被销毁时，需要释放内存。

Answer 1

不要乱用指针。那是旧的 C 风格的思维方式。

如果您要使用 C++ 中的对象，则将 Widget 和 Vidget 设为 lists/vectors/maps，并让 STL 容器拥有相关对象。然后你永远不必担心取消引用坏指针等

至于您的下一个要求，即 Widgets 需要访问 Vidgets，反之亦然，您需要在映射中实现该逻辑。我认为在数据库方面，所以我有一个 table 映射 W-to-V 和 V-to-W，方法 return references 到必要的对象。当谈到 C++ 时，我可能会使用 std::map 和小部件或 vidget 的某种 ID（如果需要是人工的）来实现它。

Answer 2

一般来说，我会先寻找一种重新设计的方法来消除这个要求。对象通常不需要通过这种方式通过其上方的对象找到其他对象。有时您可以安排在每次执行对象时通过其所有者传递对象信息。

但假设您不能更改设计，您就不想使用指针或引用。您不想使用它们，因为向量可以在内存中移动它们的对象，从而使指针和引用都无效。此外，普通指针使所有权不明确。

相反，对对象使用 std::shared_ptr 的向量。如果可能，使用 std::make_shared 创建对象。这将管理对象的生命周期以持续存在，直到它从向量中移除。

对于一个对象需要访问另一个对象，您有两种选择。如果您可能想延长所引用对象的生命周期，直到持有对它的引用的对象被销毁，请对同一对象使用另一个 std::shared_ptr。

如果您不想延长对象的生命周期，请使用 std::weak_ptr - 请记住，如果目标的生命周期结束，弱指针可能会变得陈旧。您要么需要确保这种情况永远不会发生，要么在每次访问弱指针时都检查它。最好始终检查它，以便理智地处理错误情况。

按照我个人喜好的顺序，你可以：

重新架构，以便不需要存储这些引用。例如，外部对象可以拥有关系并在每次调用内部对象时传递对内部对象的引用。甚至可能有更好的选择。外部对象可以提供内部对象可以使用的 API，内部对象可以保留对外部对象的引用。
使用shared_ptr和weak_ptr。这很干净，易于理解，并且可以清楚地捕获任何错误。它有一些开销，但仅限于设置和拆卸，如果这些对象是长期存在的，这应该无关紧要。
使用自定义智能指针。外部对象可以为内部对象提供自定义智能指针，从而为内部对象提供访问所需对象的简便方法。
使用unique_ptr和原始指针向量。

Answer 3

这是我要做的。

class Widget {
  ...
    void AddVidget(Vidget* vidget);
  private:
    std::vector<Vidget*> vigets_;
};
std::vector<std::unique_ptr<Vidget>> vidgets;
// Since widgets will have references to vidgets, safet
// to instantiate after vidgets (so widgets is cleaned up
// first).
std::vector<std::unique_ptr<Widget>> widgets;
...
widgets[i].add_vidget(vidjets[j].get());

这使您的指针稳定。

Answer 4

使用 std::vector 的主要问题是当向量发生变化时，包含的对象的地址可能会发生变化 - 特别是在您填充它时。

鉴于您的生命周期特征，您的对象将在之前建立任何关系并且在之后处理之前完全创建超过。这意味着使用关系指针没有问题。

在这种情况下，我可能会这样做：

class Widget
{
public:

private:
    std::vector<class Vidget*> ListOfVidgets;
};

class Vidget
{
public:

private:    
    std::vector<class Widget*> ListOfWidgets;
};

class OuterObject
{
public:

private:
    std::vector<Widget> vecW;
    std::vector<Vidget> vecV;
};

随着所有权语义的确立，这应该非常有效。外部向量拥有一切，内部对象向量仅包含非拥有关系指针。

如何在c++中实现这个数据结构

How to implement this data structure in c++

c++

pointers

smart-pointers