Skip to content

Latest commit

 

History

History
268 lines (203 loc) · 10.1 KB

01-vector.md

File metadata and controls

268 lines (203 loc) · 10.1 KB
Raw

std::vector<T>

Tablica o dynamicznym rozmiarze

Coders School

Cechy std::vector<T>

  • Cache-friendly
    • Elementy są ZAWSZE ułożone obok siebie w pamięci, tak jak w zwykłej tablicy
    • Iterując po std::vector<T>, kolejne jego elementy będą ładowane do pamięci podręcznej procesora z wyprzedzeniem, co niesamowicie przyspieszy odczytywanie danych (oraz modyfikację, jeśli robimy to jednowątkowo)
  • Typ T może być dowolny. Zarówno typ wbudowany jak int, double, jak i własny zdefiniowany przez nas typ.
  • Dodawanie/usuwanie elementów na końcu jest:
    • szybkie jeśli size() < capacity()
    • kosztowne w przeciwnym przypadku, gdyż zachodzi alokacja dodatkowej pamięci na nowe elementy
  • Dodawanie/usuwanie z początku oraz środka jest kosztowne, gdyż należy przesunąć o 1 pozycję wszystkie kolejne elementy, aby zachować ciągłość wektora
  • W praktyce jednak pamięć cache tak bardzo przyspiesza pracę z std::vector, że nawet dodawanie/usuwanie elementów ze środka często będzie szybsze niż w innych kontenerach

Operacje na std::vector<T>

Operacja Metody
dodawanie elementu push_back(), emplace_back(), insert(), emplace()
modyfikowanie/dostęp do elementu at(), operator[]
pierwszy/ostatni element back(), front()
rozmiar size()
zarezerwowane miejsce capacity()
rezerwowanie miejsca w pamięci reserve()
wyczyszczenie nieużywanej pamięci z wektora shrink_to_fit()
odwrócony (ang. reverse) iterator rbegin(), rend()
stały iterator cbegin(), cend(), crbegin(), crend()
wyczyszczenie kontenera clear()
przygotowanie elementu do usunięcia std::remove() (nie jest metodą std::vector<T>)
wymazanie elementów z pamięci erase()

Wstawianie elementów na koniec

std::vector<T>::push_back()

void push_back( const T& value );
void push_back( T&& value );

std::vector<T>::emplace_back()

template< class... Args >
reference emplace_back( Args&&... args );
struct Point2D {
    int x;
    int y;
};

std::vector<Point2D> vec{{1, 1}, {2, 0}, {-3, 10}};
vec.push_back({5, 2});
vec.emplace_back(5, 2);

Wstawianie elementów #1

std::vector<T>::insert()

iterator insert( const_iterator pos, const T& value );

W celu dodania elementu do wektora, możemy wykorzystać iterator:

std::vector<int> vec{1, 2, 3, 4};
auto it = vec.begin();
vec.insert(it, 20); // {20, 1, 2, 3, 4};

Wstawianie elementów #2

std::vector<T>::insert()

iterator insert( const_iterator pos, size_type count, const T& value );

Możemy także określić ile elementów chcemy dodać:

std::vector<int> vec{1, 2, 3, 4};
auto it = vec.begin();
vec.insert(it, 5, 20); // {20, 20, 20, 20, 20, 1, 2, 3, 4};

Wstawianie elementów #3

std::vector<T>::insert()

template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );

Istnieje też możliwość wstawienia elementów z jednego kontenera do drugiego:

std::vector<int> vec{1, 2, 3, 4};
std::list<int> list{10, 20, 30, 40};
vec.insert(vec.begin() + 2, list.begin(), list.end());
// vec = {1, 2, 10, 20, 30, 40, 3, 4}

Iterowanie od końca

std::vector<T>::rbegin(), std::vector<T>::rend()

std::vector<int> vec {1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = vec.crbegin() ; it != vec.crend() ; ++it) {
    // cr = (r)everse iterator to (c)onst value
    std::cout << *it << ' ';
}

Output: 9 8 7 6 5 4 3 2 1

std::vector<int> vec {1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = vec.rbegin() ; it != vec.rend() ; ++it) {
    *it *= 2;
}
for (auto it = vec.crbegin() ; it != vec.crend() ; ++it) {
    std::cout << *it << ' ';
}

Output: 18 16 14 12 10 8 6 4 2

(Prawie) usuwanie 😉

std::remove() z nagłówka <algorithm>

template< class ForwardIt, class T >
ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

Ponieważ najszybciej usuwane są elementy z końca wektora, biblioteka STL umożliwia nam przygotowanie std::vector<T> do usunięcia elementów poprzez przeniesienie tych nieprzeznaczonych do usunięcia na początek kontenera. W wyniku tego część wartości do usunięcia jest nadpisywana wartościami z końca wektora, które nie powinny zostać usunięte. Na końcu wektora pozostają "śmieci", które należy wymazać (ang. erase) z pamięci.

std::vector<int> vec{1, 4, 2, 4, 3, 4, 5};
std::remove(vec.begin(), vec.end(), 4);
// for example: vec {1, 2, 3, 5, 3, 4, 5}

std::remove() zwróci nam iterator, który wskaże początek danych przeznaczonych do usunięcia.

Usuwanie

std::vector<T>::erase()

iterator erase( const_iterator first, const_iterator last );

Dzięki metodzie erase, możemy teraz usunąć niepotrzebne dane z kontenera:

std::vector<int> vec{1, 4, 2, 4, 3, 4, 5};
auto it = std::remove(vec.begin(), vec.end(), 4);
vec.erase(it, vec.end());
// vec {1, 2, 3, 5}

Możemy też zapisać to wszystko w jednej linii (Erase-Remove Idiom)

vec.erase(std::remove(vec.begin(), vec.end(), 4), vec.end());

Zadanie 1

  • Otwórz dokumentację wektora na cppreference.com
  • Stwórz nowy plik i napisz funkcję main()
  • Stwórz wektor o wartościach {1, 2, 4, 5, 6}
  • Usuń pierwszą wartość
  • Dodaj wartość 5 na końcu wektora
  • Dodaj wartość 12 na początku wektora metodą emplace
  • Wypisz rozmiar wektora i maksymalny możliwy rozmiar
  • Wypisz zawartość wektora
  • Wyczyść wektor
  • Wypisz rozmiar wektora

Zadanie 2

  • Otwórz dokumentację wektora na cppreference.com
  • Stwórz nowy plik i napisz funkcję main()
  • Stwórz pusty wektor
  • Wypisz rozmiar i pojemność wektora
  • Zmień rozmiar wektora na 10 i wypełnij go wartościami 5
  • Wypisz rozmiar i pojemność wektora
  • Zarezerwuj pamięć na 20 elementów
  • Wypisz rozmiar i pojemność wektora
  • Zredukuj pojemność wektora metodą shrink_to_fit()
  • Wypisz rozmiar i pojemność wektora

Q&A