c++ - 如何改进这些嵌套的 for 循环

Question

我有以下代码:

// vector of elements
vector<Graphic> graphics;

// vector of indexes of the selected graphic elements
vector<int> selected_indexes;

// vector according to which the graphic elements have to be "sorted" and parsed
vector<short> order;

for (auto o : order)
{
    for (auto i : selected_indexes)
    {
        const auto& g = graphics[i];

        if (g.position() == o)
        {
            // parse g
        }
    }
}

我有一个自定义元素的 vector 以及已选择要解析的元素的索引，但是必须解析这些元素的顺序取决于它们的 position()根据第三个 vector 的值。

有没有办法改进这些嵌套循环，避免对将被跳过的元素反复迭代，因为它们的位置不等于当前顺序？

Answer 1

假设只有一个 Graphic具有给定 position() 的对象:

构建 unordered_map : int → Graphics* ，你称之为例如gp ，所以 gp[i]->position() = i .

构建 map 是线性时间，对每个索引使用它大致是恒定时间。

for( auto o : order )
{
    auto const& g = *gp[o];
    // parse g
}

如果可以有多个 Graphics给定位置的对象，构建 unordered_map : int → vector<Graphic*> ，然后使用类似的使用代码

for( auto o : order )
{
    for( auto const p : gp[o] )
    {
        auto const& g = *p;
        // parse g
    }
}

或者，对于最后一种情况，您可以使用 unordered_multimap .