c++ - 哪种数据结构按插入排序并具有快速的 “contains”检查？

Question

我正在寻找一种数据结构，该结构可以保留元素插入的顺序并提供快速的“包含”谓词。我还需要迭代器和随机访问。插入或删除期间的性能无关紧要。我也愿意接受内存消耗方面的开销。

背景:我需要存储对象列表。这些对象是称为Neuron的类的实例，并存储在Layer中。 Layer对象具有以下公共(public)接口(interface):

class Layer {
public:
    Neuron *neuronAt(const size_t &index) const;
    NeuronIterator begin();
    NeuronIterator end();
    bool contains(const Neuron *const &neuron) const;
    void addNeuron(Neuron *const &neuron);
};

软件运行时经常调用 contains()方法，我断言使用callgrind。我试图绕开对 contains()的调用，但是仍然是一个热点。现在，我希望完全优化此方法。

我想到了使用 std::set，使用template参数来提供我自己的比较器结构。但是 Neuron类本身并未放弃其在 Layer中的位置。另外，我希望 *someNeuronIterator = anotherNeuron可以正常工作而不会破坏顺序。

另一个想法是使用普通的旧C数组。由于我不在乎添加新的 Neuron对象的性能，因此我认为可以确保 Neuron对象始终线性存储在内存中。但这会使我传递给 addNeuron()的指针无效；至少我必须更改它以指向我创建的新副本，以保持事物线性对齐。对？

另一个想法是在 Layer对象中使用两个数据结构:用于订单的 vector /列表，以及用于查找的映射/哈希。但这与我希望有一个允许const引用而不带const引用的 operator*的迭代器的愿望相反，不是吗？

我希望有人可以提出一个满足我需求的数据结构或概念的想法，或者至少给我一个替代方案的想法。谢谢!

Answer 1

如果确实需要最快地执行contains检查，并且假设您对源代码有些不满，那么检查Neuron是否属于某个层的最快方法是在将其插入到层中时对其进行标记(例如:位标志)。

您已确保在此时进行O(1)检查，以查看Neuron是否属于某个层，并且在微级别上也很快。

如果可以有许多层对象，这可能会有点棘手，因为您需要为神经元可以属于的每个潜在层单独分配一个位，除非Neuron一次只能属于一个层。但是，如果层的数量在大小上相对固定，则这是合理可管理的。

如果后一种情况和一个Neuron一次只能属于一个层，那么您所需要的只是Layer*的反向指针。要查看神经元是否属于图层，只需查看该后向指针是否指向图层对象即可。

如果Neuron一次可以属于多个层，但一次不能属于多个层，那么您可以像这样存储少量的指向后方的数组:

struct Neuron
{
    ...
    Layer* layers[4]; // use whatever small size that usually fits the common case
    Layer* ptr;
    int num_layers;
};

如果 ptr属于4层或更少的图层，请初始化 layers以指向 Neuron。如果还有更多，请在免费商店中分配它。在析构函数中，如果 ptr != layers释放内存。如果常见情况是1层，您还可以优化 num_layers，在这种情况下，以null终止的解决方案可能会更好。要查看神经元是否属于图层，只需通过 ptr进行线性搜索。就神经元的数量而言，这实际上是恒定的时间复杂性，前提是它们不一次属于大量的层。

您还可以在此处使用 vector，但是在那些常见情况下，您可以减少缓存命中率，因为即使Neuron仅属于1层或2层，它也总是将其内容放在单独的块中。

这可能与您在通用，非介入式数据结构中寻找的内容有所不同，但是，如果您的性能需求确实偏向于此类设置操作，那么介入式解决方案通常将是最快的。它不是很漂亮，并将您的元素耦合到容器，但是，嘿，如果您需要最大的性能……

另一个想法是使用普通的旧C数组。由于我不在乎添加新的Neuron对象的性能，因此我认为可以确保Neuron对象始终以线性方式存储在内存中。但这会使我传递给addNeuron()的指针无效； [...]

是的，但是不会使索引无效。尽管使用起来不如指针方便，但是如果要处理诸如网格的顶点或发射器的粒子之类的海量数据，通常会在此处使用索引以避免无效，并可能在每个条目上节省32位64位系统。

更新资料

鉴于神经元一次仅存在于一个层中，我将使用后向指针方法。查看神经元是否属于一个层变得很简单，只需检查后指针是否指向同一层即可。

因为涉及到一个API，所以我建议，就好像听起来您正在推送大量数据并且已经对其进行了概要分析一样，您应该专注于围绕聚合(例如层)而不是单个元素的接口(interface)。 (神经元)。当您的客户端不在单个标量元素类型接口(interface)上执行操作时，这将为您留出很大的空间来交换基础表示。

有了O(1) contains实现和无序要求，我将使用一个简单的连续结构，例如 std::vector。但是，您确实会使自己在插入时可能会失效。

因此，如果可以的话，我建议在这里使用索引。但是，这变得有点笨拙，因为它要求您的客户端除了存储其索引之外还存储指向神经元所属层的指针(尽管如果这样做，由于客户端正在跟踪事物所属的位置，因此后向指针变得不必要了) 。

减轻这种情况的一种方法是简单地使用 std::vector<Neuron*>或 ptr_vector之类的东西(如果可用)。但是，这可能使您面临高速缓存未命中和堆开销的问题，并且如果您想对其进行优化，这就是固定分配器派上用场的地方。但是，这会给对齐问题带来一些麻烦，并且会涉及一些研究主题，到目前为止，看来您的主要目标是不像 contains检查那样优化插入或顺序访问，所以我从 std::vector<Neuron*>。