[C++] Szybkie (optymalne) "przesuwanie" tablicy


(Harry127) #1

Przykład:

Mam tablicę 5-elementową: ([element] = wartość)

[0] = 12; [1] = 24; [2] = 48; [3] = 96; [4] = 192;

Chcę dodać do niej element 127 i przesunąć tablicę w lewo, aby otrzymać:

[0] = 24; [1] = 48; [2] = 96; [3] = 192; [4] = 127;

Jak najszybciej (najbardziej optymalnie) to zrobić?


(B Brachaczek) #2

Chyba raczej najpierw przesunąć, a potem dodać element.

Generalnie to takie coś dla dużych tablic zawsze będzie kosztowne. Wiele lepiej niż za pomocą memmove() z raczej tego nie zrobisz. Gdybyś chciał coś takiego naprawdę szybko załatwić, to najlepiej zrobić listę zamiast zwykłej tablicy.


(Harry127) #3

A jest sposób na sprawdzenie, czy element jest na liście? Znam tylko funkcję usuwającą z listy element o danej wartości...


(B Brachaczek) #4

Jeśli korzystasz z STL-owej listy to śmiało możesz posłużyć się funkcją std::find() z .

if(std::find(lista.begin(), lista.end(), wartosc) != lista.end())

    std::cout << "Element jest na liscie\n";

Żeby zachować możliwość odnoszenia się do elementów jak w tablicy, możesz użyć std::deque.

Co do przesuwania, to robisz pop_front() i push_back().

A jeśli implementujesz listę samodzielnie (jeśli nigdy tego nie robiłeś - polecam), to chyba sam powinieneś wiedzieć.


(pebal) #5

Wcale nie trzeba jej przesuwać. Wystarczy wstawić element na początku i zmodyfikować logiczne indeksy początku i końca tablicy.


(B Brachaczek) #6

Racja, to jest najtańsze rozwiązanie (chociaż niewiele bardziej od dwustronnej kolejki (czy jak to tam po polsku się nazywa) zaimplementowanej w STL-u, a jest mniej pisania jeśli korzystamy z STL-a). Jeśli chciałbyś wykorzystywać tę tablicę w wielu miejscach programu, to najlepiej opakować ją w klasę, która sama zajęłaby się zarządzaniem logicznymi indeksami (kwestia jednej dodatkowej zmiennej w klasie i dodawania/odejmowania jej od indeksu).