W jakim scenariuszu używam określonego kontenera STL?

Czytałem o kontenerach STL w mojej książce o C ++, a konkretnie w sekcji o STL i jego kontenerach. Teraz rozumiem, że każda z nich ma swoje specyficzne właściwości i jestem blisko zapamiętywania ich wszystkich ... Ale nie rozumiem jeszcze, w którym scenariuszu każdy z nich jest używany.

Jakie jest wyjaśnienie? Przykładowy kod jest znacznie preferowany.

Ta ściągawka stanowi całkiem dobre podsumowanie różnych pojemników.

Zobacz schemat blokowy na dole, jako przewodnik do użycia w różnych scenariuszach użycia:

_{Stworzony przez Davida Moore'a i licencjonowany CC BY-SA 3.0}

Oto schemat blokowy zainspirowany wersją Davida Moore'a (patrz wyżej), która jest aktualna (głównie) z nowym standardem (C ++ 11). To tylko moje osobiste podejście do sprawy, nie jest to bezdyskusyjne, ale pomyślałem, że może być cenne w tej dyskusji:

Prosta odpowiedź: używaj std::vectordo wszystkiego, chyba że masz prawdziwy powód, aby zrobić inaczej.

Kiedy znajdziesz przypadek, w którym myślisz: „Ojej, std::vectortutaj nie działa dobrze z powodu X”, idź na podstawie X.

Spójrz na Effective STL autorstwa Scotta Meyersa. Jest dobry w wyjaśnianiu, jak używać STL.

Jeśli chcesz przechowywać określoną / nieokreśloną liczbę obiektów i nigdy nie zamierzasz ich usuwać, to wektor jest tym, czego chcesz. Jest to domyślny zamiennik tablicy C i działa jak jeden, ale nie przepełnia się. Możesz również wcześniej ustawić jego rozmiar za pomocązerawienia ().

Jeśli chcesz przechowywać nieokreśloną liczbę obiektów, ale będziesz je dodawać i usuwać, prawdopodobnie chcesz mieć listę ... ponieważ możesz usunąć element bez przenoszenia kolejnych elementów - w przeciwieństwie do wektora. Jednak zajmuje więcej pamięci niż wektor i nie można uzyskać sekwencyjnego dostępu do elementu.

Jeśli chcesz wziąć kilka elementów i znaleźć tylko unikalne wartości tych elementów, wczyta je wszystkie w zestaw, a także posortuje je dla ciebie.

Jeśli masz wiele par klucz-wartość i chcesz je posortować według klucza, mapa jest przydatna ... ale będzie zawierała tylko jedną wartość na klucz. Jeśli potrzebujesz więcej niż jednej wartości na klucz, możesz mieć wektor / listę jako wartość na mapie lub użyć multimapy.

Nie ma go w STL, ale jest w aktualizacji TR1 do STL: jeśli masz wiele par klucz-wartość, które będziesz sprawdzać według klucza, a nie obchodzi ich kolejność, możesz chcę użyć skrótu - który jest tr1 :: unordered_map. Użyłem go z Visual C ++ 7.1, gdzie nazywał się stdext :: hash_map. Ma odnośnik O (1) zamiast odnośnika O (log n) dla mapy.

Przeprojektowałem schemat blokowy, aby miał 3 właściwości:

1. Myślę, że kontenery STL są podzielone na 2 główne klasy. Kontenery podstawowe i te wykorzystują kontenery podstawowe do wdrożenia polityki.
2. Na początku schemat blokowy powinien podzielić proces decyzyjny na główne sytuacje, w których powinniśmy podjąć decyzję, a następnie opracować każdy przypadek.
3. Niektóre pojemniki rozszerzone mają możliwość wyboru innego pojemnika podstawowego jako pojemnika wewnętrznego. Schemat blokowy powinien uwzględniać sytuacje, w których można użyć każdego z podstawowych pojemników.

Schemat blokowy:

Więcej informacji pod tym linkiem .

Ważnym punktem tylko krótko wspomniano dotąd, jest to, że jeśli wymagają pamięci ciągłej (jak tablica C daje), a następnie można użyć tylko vector, arrayalbo string.

Użyj, arrayjeśli rozmiar jest znany w czasie kompilacji.

Użyj, stringjeśli potrzebujesz pracować tylko z typami znaków i potrzebujesz łańcucha, a nie tylko kontenera ogólnego przeznaczenia.

Użyj vectorwe wszystkich innych przypadkach (i tak vectorpowinien być domyślnym wyborem kontenera).

Za pomocą wszystkich tych trzech elementów można użyć data()funkcji członka, aby uzyskać wskaźnik do pierwszego elementu kontenera.

Wszystko zależy od tego, co chcesz przechowywać i co chcesz zrobić z pojemnikiem. Oto kilka (bardzo niewyczerpujących) przykładów klas kontenerów, których najczęściej używam:

vector: Kompaktowy układ z niewielkim lub zerowym obciążeniem pamięci dla każdego zawartego obiektu. Wydajny w iteracji. Dołączanie, wstawianie i usuwanie może być kosztowne, szczególnie w przypadku złożonych obiektów. Tanie znaleźć obiekt zawarty w indeksie, np. MyVector [10]. Użyj tam, gdzie użyłbyś tablicy w C. Dobrze, gdzie masz wiele prostych obiektów (np. Int). Nie zapomnij użyć reserve()przed dodaniem wielu przedmiotów do kontenera.

list: Mały narzut pamięci na zawarty obiekt. Wydajny w iteracji. Dołączanie, wstawianie i usuwanie są tanie. Użyj tam, gdzie użyłbyś połączonej listy w C.

set(i multiset): Znaczny narzut pamięci na zawarty obiekt. Użyj tam, gdzie musisz szybko dowiedzieć się, czy ten kontener zawiera dany obiekt, lub wydajnie scalaj kontenery.

map(i multimap): Znaczny narzut pamięci na zawarty obiekt. Użyj tam, gdzie chcesz przechowywać pary klucz-wartość i szybko wyszukiwać wartości według klucza.

Schemat blokowy na ściągawki sugerowany przez zdan zapewnia bardziej wyczerpujący przewodnik.

Jedna lekcja, której się nauczyłem, to: spróbuj zawinąć w klasę, ponieważ zmiana rodzaju pojemnika jednego dobrego dnia może przynieść duże niespodzianki.

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

Nie kosztuje dużo z góry i oszczędza czas podczas debugowania, gdy chcesz przerwać za każdym razem, gdy ktoś wykonuje operację x na tej strukturze.

Jeśli chodzi o wybranie idealnej struktury danych dla zadania:

Każda struktura danych zapewnia pewne operacje, które mogą mieć różną złożoność czasową:

O (1), O (lg N), O (N) itp.

Zasadniczo musisz zgadnąć, które operacje zostaną wykonane najbardziej, i użyć struktury danych, która ma tę operację jako O (1).

Proste, prawda? (-:

Rozszerzyłem fantastyczny schemat blokowy Mikaela Perssona . Dodałem kilka kategorii kontenerów, kontener tablicowy i kilka notatek. Jeśli chcesz mieć własną kopię, oto rysunek Google. Dzięki, Mikael za wykonanie prac przygotowawczych! Selektor kontenerów w C ++

Odpowiedziałem na to w innym pytaniu, które jest oznaczone jako duplikat tego. Uważam jednak, że miło jest odwołać się do dobrych artykułów na temat wyboru standardowego pojemnika.

Jak odpowiedział @David Thornley, std :: vector to droga, jeśli nie ma innych specjalnych potrzeb. Jest to rada udzielona przez twórcę C ++, Bjarne Stroustrup na blogu w 2014 roku.

Oto link do artykułu https://isocpp.org/blog/2014/06/stroustrup-lists

i cytat z tego,

I tak, zalecam domyślnie użycie std :: vector.

W komentarzach użytkownik @NathanOliver zapewnia również kolejny dobry blog, który zawiera bardziej konkretne pomiary. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html .