W jakim scenariuszu mogę użyć konkretnego kontenera STL?

Oto schemat inspirowany wersją Davida Moore ' a (Patrz wyżej), którą stworzyłem, która jest aktualna (głównie) z nowym standardem (C++11). To jest tylko moje osobiste podejście do tego, to nie jest niepodważalne, ale pomyślałem, że może być cenne w tej dyskusji: {]}

Prosta odpowiedź: użyj wektora do wszystkiego, chyba że masz prawdziwy powód, aby zrobić inaczej.

Kiedy znajdziesz przypadek, w którym myślisz, "Gee, vector nie działa dobrze tutaj z powodu X", Przejdź na podstawie X.

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

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

Jeśli chcesz przechowywać nieokreśloną liczbę obiektów, ale będziesz je dodawać i usuwać, to pewnie chcesz listę...ponieważ można usunąć element bez przesuwania kolejnych elementów-w przeciwieństwie do wektora. Wymaga to jednak więcej pamięci niż wektor i nie można sekwencyjnie uzyskać dostępu do elementu.

Jeśli chcesz wziąć kilka elementów i znaleźć tylko unikalne wartości tych elementów, odczytanie ich wszystkich w zbiorze to zrobi, a to posortuje je również dla Ciebie.

Jeśli masz wiele par klucz-wartość i chcesz je posortować według klucza, przydatna jest mapa...ale będzie zawierać 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ć mapy multimap.

Nie znajduje się w STL, ale jest w aktualizacji TR1 do STL: jeśli masz wiele par klucz-wartość, które chcesz sprawdzić według klucza, i nie obchodzi cię ich kolejność, możesz użyć hash-który jest tr1:: unordered_map. Używałem go z Visual C++ 7.1, gdzie nazywał się stdext:: hash_map. Ma o (1) zamiast Wyszukiwania O (log n) dla mapy.

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 napowietrzaniem pamięci na zawarty obiekt. Wydajny do iteracji. Dołączanie, wstawianie i kasowanie może być kosztowne, szczególnie w przypadku złożonych obiektów. Tanio znaleźć zawarty obiekt po indeksie, np. myVector[10]. Użyj gdzie użyłbyś tablicy w C. Dobrze, gdzie masz wiele prostych obiektów(np. int). Nie zapomnij użyć reserve() przed dodaniem wielu obiektów do kontenera.

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

set (and multiset): znaczący nadmiarowy napór pamięci na zawarty obiekt. Użyj miejsca, w którym musisz szybko dowiedzieć się, czy kontener zawiera dany obiekt, lub połącz kontenery skutecznie.

map (i multimap): znaczący nadmiarowy napór pamięci na zawarty obiekt. Użyj miejsca, w którym chcesz przechowywać pary klucz-wartość i szybko wyszukuj wartości według klucza.

SCHEMAT BLOKOWY na ściągaczu sugerowany przez zdan zawiera bardziej wyczerpujący przewodnik.

Ważnym punktem, o którym do tej pory krótko wspomniano, jest to, że jeśli potrzebujesz sąsiedniej pamięci (Jak daje tablica C), możesz użyć tylkovector, array, lub string.

Użyj array, Jeśli rozmiar jest znany podczas kompilacji.

Użyj string, jeśli potrzebujesz tylko pracować z typami znaków i potrzebujesz ciągu znaków, a nie tylko kontenera ogólnego przeznaczenia.

Użyj vector we wszystkich innych przypadkach (vector powinien być domyślnym wyborem kontenera w większości przypadków).

Ze wszystkimi trzema z tych możesz użyć funkcji data() member, aby uzyskać wskaźnik do pierwszego elementu kontenera.

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

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

Nie kosztuje wiele z góry i oszczędza czas w debugowaniu, gdy chcesz się złamać, gdy ktoś wykonuje operację x na tej strukturze.

Przy wyborze 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), itd.

Zasadniczo musisz zgadnąć, które operacje będą wykonywane najczęściej, i użyć struktury danych, która ma tę operację jako O(1).

Proste, prawda (- :

Rozszerzyłem Mikaela Perssona fantastyczny SCHEMAT BLOKOWY. Dodałem kilka kategorii kontenerów, kontener tablicy i kilka uwag. Jeśli chcesz własną kopię, Tutaj jest rysunek Google. Dzięki, Mikael za wykonanie prac ziemnych! C++ Container Picker