Как улучшить эти вложенные для циклов

У меня есть следующий код:

// 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
        }
    }
}

У меня есть вектор пользовательских элементов, а также индексы элементов, которые были выбраны для синтаксического анализа, но порядок, в котором эти элементы должны быть проанализированы, зависит от их значения position() в соответствии с третьим вектором.

Есть ли способ улучшить эти вложенные циклы, избегая повторного итерации элементов, которые будут пропущены, потому что их позиция не равна текущему порядку?

Ответы

Ответ 1

Предполагая, что существует только один объект Graphic с заданным position():

Создайте unordered_map: int → Graphics*, который вы вызываете, например. gp, так что gp[i]->position()= i.

Построение карты - это линейное время, использующее для каждого индекса постоянное время, примерно.

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.

Ответ 2

Вы уже знаете, сколько элементов вы хотите обработать, поэтому вы можете использовать вектор, который содержит указатели на экземпляры Graphic, уже выделенные соответствующим количеством элементов:

vector<Graphic*> selected(selected_indexes.size(), nullptr);

Затем вы можете заполнить этот вектор элементами, отсортированными с помощью order:

for (auto index: selected_indexes) {
  auto where = std::find_if(order.begin(), order.end(), [&graphics, index] (short i) { return i == graphics[index].position(); });
  selected[*where] = &graphics[index];
}

Ответ 3

Вместо их вложения вы можете создать временный вектор и сделать это шаг за шагом.

vector<Graphic> selectedGraphics; //maybe use ptr here
selectedGraphics.reserve(selected_indexes.size());
for(auto i : selected_indexes)
    selectedGraphics.push_back(graphics[i]);

//then sort according to your order
std::sort(selectedGraphics.begin(),selectedGraphics.end(),[order](auto left, auto right)
{
    //the iterator of the position of "left" is further in front of the position of "right"
    return order.find(left.position()) < order.find(right.position());
});

//then process
for(auto graphic : selectedGraphics)
    //do whatever

Сорт предполагает, что элементы вектора order и те, которые соответствуют selectedGraphics. Я не уверен, будут ли какие-либо странные побочные эффекты, если выбранный графический объект имеет позицию, которая не находится в векторе order.