Nick Nick - 3 months ago 13
C++ Question

How to improve these nested for loops

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

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

Build an unordered_map : intGraphics*, 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 : intvector<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.

Comments