我正在开发一个旨在渲染大量形状的应用程序。每个形状都可以分配给一个特定的层。

我将输入数据作为形状列表获取，其中对于每个形状，我都有一个 string 属性，表示该形状所属的图层。

现在，我需要开发一种方法，允许我只选择(绘制)那些属于给定选定图层列表的形状。 在伪代码中:

void draw_if(sorted_list shapes, list<string> selected_layers)
{
   for each shape in shapes
   {
      if (shape.layer in selected_layers)
        shape.draw();
   }
}

关键是我想尽快执行这个操作；因此我需要选择正确的数据结构和合适的算法。

所选层的列表是一个字符串列表(1÷100 个不同的层)，但如果出于性能原因需要，它可以转换为其他数据类型。

形状根据它们的 z 顺序排序。

最佳答案

在寻找复杂的数据结构和算法时，基本的侵入式解决方案经常被忽略，但通常是最快的。

假设您别无选择，只能将选择分开，如果您想要一个非常快速的解决方案，请在每一层中存储一个 bool 选择标志(可以是一个位)。当您形成选择时，除了形成列表外，还要设置这些标志。取消选择图层不仅会将其从您的选择中删除，还会将该选择标志设置为 false。

接下来，将那些用于指示所选层的字符串转换为随机访问结构中的索引(例如:std::vector 或什至是一个普通的旧数组，如果大小可以在编译时确定的话)，像这样(简化):

struct Layer
{
    string name;

    // Set this to true when the layer is selected, false 
    // when it is deselected. Use atomics if thread safety 
    // is required.
    bool selected;
};

... 并将 shape.layer 转换为图层的索引(或指针/迭代器)。如果您别无选择，只能从图层字符串开始识别形状属于哪个图层，因为您最初获得了字符串输入(例如:来自您正在加载的文件)，然后将这些字符串转换为图层索引/指针/迭代器当您从这些字符串输入创建形状时。在此处使用哈希表或至少 std::set/map(初始形状构造上的字符串搜索应为对数或更好)将这些层字符串转换为层索引/指针/迭代器。

如果除了图层选择状态之外还需要图层选择列表，那么可以这样做(伪代码):

void select(Layer layer, LayerList& layer_selection)
{
     if (!layer.selected)
     {
          layer.selected = true;
          layer_selection.insert(&layer);
     }
}

void deselect(Layer layer, LayerList& layer_selection)
{
     if (layer.selected)
     {
          layer.selected = false;
          layer_selection.erase(&layer);
     }
}

... 您的图层选择将索引/指针/迭代器存储到图层的位置。选择和取消选择列表的插入/删除都可以在恒定时间内完成(即使在最坏的情况下)，没有散列开销，并且如果您喜欢层选择并使用固定的，则同时保留插入顺序分配器(这是一个涉及 placement new、union 和内存池的复杂主题，所以如果需要我会深入研究它，但为了简洁暂时忽略它)。

现在你的主要伪代码变成了这样的东西:

void draw_if(list shapes, list layers)
{
   for each shape in shapes
   {
      if (layers[shape.layer].selected)
        shape.draw();
   }
}

...或者如果你使用指针/迭代器的话:

void draw_if(list shapes, list layers)
{
   for each shape in shapes
   {
      if (shape.layer->selected)
        shape.draw();
   }
}

就性能而言，很难击败它，因为即使是最优化的哈希表也无法击败对内存的简单索引数组访问，除了哈希之外，您仍然需要访问内存。现在如果你能巩固“选择形状”的思想，通过选择/取消选择图层的过程预先形成选择的形状，那么你可以这样做:

void draw_selected(list selected_shapes)
{
   for each shape in selected_shapes
       shape.draw();
}

... 这可能会更快，前提是形成所选形状列表的额外成本可以通过在必须更改之前重复使用它来补偿。请注意，在这种情况下，您仍然希望将这些字符串转换为索引，因为您不希望您的“选定形状”列表不仅仅是一个简单的数组。形成选定的形状列表:

ShapeList selected_shapes(ShapeList all_shapes, LayerList layers)
{
     // Forming this in advance will help if it is reused for
     // numerous drawing frames before it needs to change (ex:
     // before the Z-order changes, before new elements are inserted
     // or existing ones removed, before the layer selection changes).
     ShapeList results;
     for each shape in all_shapes:
          if layers[shape.layer].selected)
             results.push_back(shape);
     return results;
}

...由于我们现在存储在层中的选择状态，它的形成和访问(由于完美紧凑的形状选择数组的空间局部性)仍然比哈希表更便宜。

这使一切缓存友好，并避免昂贵的(相对而言)数据结构，如哈希表，除了在初始字符串->索引/指针转换部分(您只需要在从字符串输入创建形状时)。在这种情况下，唯一需要进行任何类型的搜索(对数或恒定时间哈希/trie)的地方是当您将从用户输入获得的那些形状层字符串转换为索引/指针/迭代器时。其他一切都是 O(1)(甚至是最坏情况下的复杂度)并且甚至不需要散列。

关于c++ - 根据属性从列表中选择元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30945464/