How to improve these nested for loops [closed]

Question

I have the following code:

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

I have a vector of custom elements as well as the indexes of the elements that have been selected to be parsed, but the order in which these elements have to be parsed depends on their position() value according to a third vector.

Is there a way to improve these nested loops, avoiding to iterate over and over on elements that will be skipped because their position is not equal to the current order?

Answer 1

Assuming there's only one Graphic object with a given position():

Build an unordered_map : int → Graphics*, that you call e.g. gp, so that gp[i]->position() = i.

Building the map is linear time, using it for each index is constant time, roughly.

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

If there can be more than one Graphics object with a given position, build an unordered_map : int → vector<Graphic*>, then with usage code like

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

Or, for the last case you might use an unordered_multimap.

Answer 2

You already know how many elements you want to process, so you can use a vector that keeps pointers to your Graphic instances, already allocated with the appropriate number of elements:

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

Then you can fill this vector with the elements, sorted using 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];
}