Kontener C++ bardzo efektywny w dodawaniu elementów do końca

Question

Prowadziłem program C++ dla celów naukowych, a teraz patrzę na jego optymalizację.

Wąskie gardło wydaje się być funkcją, w której muszę układać pary liczb całkowitych. Ich liczba jest niemożliwa do uzyskania od początku, a ja korzystam z std::vector z niestandardowej struktury zawierającej dwa ints. Czy istnieje bardziej wydajny kontener danych do powtarzalnego dodawania elementów na końcu? Czy powinienem używać go z dwoma ints zamiast pary lub niestandardowej struktury?

edycja: Po ustaleniu czasu i profilowaniu mojego programu, mogę powiedzieć, że dla mojego użytku, vector jest nieco szybszy niż deque (tylko 3%). Mój świecki wniosek jest taki, że CPU dobrze wykorzystuje bliskość danych. Optymalizacja jest dla mnie bardziej niż kiedykolwiek czarem! A to może pomóc: Naprawdę znacznie poprawiłem mój czas pracy, przełączając generator liczb losowych STL C++ 11 na BOOST.

Answer 1

Koszt logarytmicznej liczby ponownych przydziałów, które musisz zrobić, to: prawdopodobnie nieistotny:. Możesz jednak rozważyć użycie std::deque, która gwarantuje wstawienie O(1) z przodu i na końcu. Straciłbyś przynależność, ale zachowano łatwość obsługi pamięci podręcznej. A deque to zwykle przyzwoity kompromis, szczególnie jeśli musisz pop z przodu.

Należy również rozważyć oszacowanie liczby elementów, które będzie przechowywać wektor, oraz użycie wartości reserve. Uważaj jednak, aby nie marnować zbyt dużo pamięci, bo inaczej uzyskasz odwrotny efekt.

Answer 2

Jak już wspomniano przez gd1, std::deque (podwójna kolejka końcowa) umożliwia szybkie wstawianie i usuwanie na obu końcach. Ponadto wstawianie i usuwanie na każdym końcu bloku danych nigdy nie unieważnia wskaźników ani odniesień.

W twoim przypadku można na przykład użyć std::deque z std::pair (zdefiniowanego w <utility>) do własnych potrzeb:

// Small example: 
deque<pair<int, int>> deq; 
deq.push_back({1234, 4321}); 
cout << deq.at(0).first << " " << deq.at(0).second; 

// using 'at' above, should normally be inside a try block as it may throw 
// out_of_range exception