Jak poprawić te zagnieżdżone pętle

Question

Mam następujący kod:

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

Mam wektor elementów niestandardowych, jak również spis elementów, które zostały wybrane, aby być analizowany, ale porządek w które te elementy muszą zostać przeanalizowane, zależy od ich wartości position() według trzeciego wektora.

Czy istnieje sposób na ulepszenie tych zagnieżdżonych pętli, unikanie wielokrotnego powtarzania elementów, które zostaną pominięte, ponieważ ich pozycja nie jest równa aktualnej kolejności?

Answer 1

Zakładając, że jest tylko jedna Graphic obiekt o danym position():

Zbuduj unordered_map: int → Graphics*, że zadzwonisz na przykład gp, dzięki czemu gp[i]->position() = i.

Tworzenie mapy to czas liniowy, a użycie jej dla każdego indeksu to czas stały, w przybliżeniu.

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

Jeśli nie może być więcej niż jeden Graphics obiekt o danej pozycji, budować unordered_map: int → vector<Graphic*>, następnie z kodem użytkowania jak

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

albo na tym ostatnim przypadku można użyć unordered_multimap.

Answer 2

Wiesz już, ile elementów ma zostać przetworzona, dzięki czemu można używać wektor, który utrzymuje wskaźniki do swoich Graphic przypadkach już przydzielonych z odpowiednią ilość elementów:

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

Następnie można wypełnić ten wektor z elementów, sortowane przy użyciu 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]; 
} 

Answer 3

Zamiast gniazdowania te można utworzyć tymczasowy wektor i zrobić to krok po kroku.

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 

Sortowanie zakłada, że ​​order wpisy wektorowe i te, które są selectedGraphics mecz. Nie jestem pewien, czy wystąpią jakieś dziwne efekty uboczne, jeśli wybrany obiekt graficzny ma pozycję, która nie znajduje się w wektorze order.