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

185

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.

c++ stl container-data-type

— Daniel Sloof
źródło

masz na myśli mapę, vectot, set itp?

— Thomas Tempelmann

Nawet patrząc na ten diagram, nie mogę powiedzieć, który byłby najlepszy do użycia w moim

— quizie

2

@sbi: Usuwanie tagu Faq C ++ z tego i dodawanie go do nowszej wersji i włącznie z C ++ 11 Jak mogę efektywnie wybrać standardowy kontener biblioteki w C ++ 11?

— Alok Zapisz

338

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}

— zdan
źródło

14

Ten schemat blokowy jest złoty, chciałbym mieć coś takiego w c #

— Bruno

2

Zaktualizowany link: Ściągawka do kontenerów C ++ .

— Bill Door

3

Punkt początkowy musi być vectorraczej niż pusty. stackoverflow.com/questions/10699265/…

— eonil

5

Masz teraz unordered_mapi unordered_set(i ich wiele wariantów), których nie ma na schemacie, ale są dobrym wyborem, gdy nie dbasz o porządek, ale musisz znaleźć elementy według klucza. Ich wyszukiwanie to zwykle O (1) zamiast O (log n).

— Aidiakapi

2

@ Shuttle87 nie tylko ten rozmiar nigdy się nie zmieni, ale co ważniejsze, rozmiar jest określany w czasie kompilacji i nigdy się nie zmienia.

— YoungJohn

188

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:

wprowadź opis zdjęcia tutaj

— Mikael Persson
źródło

4

Czy możesz udostępnić oryginał? To doskonały wykres. Może przykleisz się do bloga lub GitHub?

— kevinarpe

1

To doskonały wykres. Czy ktoś może mi wyjaśnić, co należy rozumieć przez „uparte stanowiska”?

— IDDQD

3

@STALKER Trwałe pozycje oznaczają, że jeśli masz wskaźnik lub iterator do elementu w kontenerze, ten wskaźnik lub iterator pozostaną ważne (i będą wskazywać ten sam element) niezależnie od tego, co dodasz lub usuniesz z kontenera (o ile nie jest tym elementem).

— Mikael Persson

1

To naprawdę świetny wykres, jednak myślę, że vector (sorted)jest trochę niespójny z resztą. To nie jest inny typ kontenera, tylko ten sam, std::vectorale posortowany. Co ważniejsze, nie rozumiem, dlaczego nie można użyć std::setpolecenia dla uporządkowanej iteracji, jeśli jest to standardowe zachowanie iteracji przez zestaw. Jasne, jeśli odpowiedź mówi o uporządkowanym dostępie do wartości koryta kontenera [], to ok, możesz to zrobić tylko z sotowanym std::vector. Ale w obu przypadkach decyzję należy podjąć zaraz po pytaniu „potrzebne zamówienie”

— RA

1

@ user2019840 Chciałem ograniczyć wykres do standardowych kontenerów. Zamiast „posortowanego wektora” powinien pojawić się „flat_set” (z Boost.Container ) lub równoważny (każda większa biblioteka lub podstawa kodu ma odpowiednik flat_set, AFAIK). Ale są to niestandardowe i rażące pominięcie w STL. A powodem, dla którego nie chcesz iterować przez std :: set lub std :: map (przynajmniej nie często) jest to, że jest to bardzo nieefektywne .

— Mikael Persson

41

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.

— David Thornley
źródło

1

Jednak .. uważaj, aby nie usuwać / wstawiać elementów podczas iteracji ... użyj const_iterator tak daleko, jak to możliwe, aby tego uniknąć ..

— vrdhn

11

Hmm ... Myślę, że ludzie nadmiernie wykorzystują wektor. Powodem jest to, że skrzynka „nie działa” nie stanie się łatwo - więc ludzie trzymają się najczęściej używanego kontenera i niewłaściwie go używają do przechowywania list, kolejek ... W moim przeciwieństwie - co odpowiada schematowi blokowemu - należy wybrać pojemnik na podstawie zamierzonego zastosowania zamiast stosować „jeden wydaje się pasować do wszystkich”.

— Czarny

13

@Black Point jest taki, że wektor jest zwykle szybszy nawet w przypadku operacji, które teoretycznie powinny działać wolniej.

— Bartek Banachewicz

1

@Vardhan std::remove_ifprawie zawsze przewyższa podejście „usuń podczas iteracji”.

— fredoverflow

1

Niektóre testy porównawcze naprawdę pomogłyby w mniej subiektywnej dyskusji.

— Felix D.

11

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.

— Mark Krenitsky
źródło

Słyszałem kilka anegdot sugerujących, że Microsoft hash_mapnie jest bardzo dobrą implementacją. Mam nadzieję, że poradzili sobie lepiej unordered_map.

— Mark Ransom,

3

Z list - „nie można uzyskać sekwencyjnego dostępu do elementu”. - Myślę, że masz na myśli, że nie możesz losowo uzyskać dostępu ani indeksować bezpośrednio do elementu ....

— Tony Delroy

^ Tak, ponieważ dostęp sekwencyjny jest dokładnie tym, co listrobi. Raczej rażący błąd.

— underscore_d

7

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

Myślę, że kontenery STL są podzielone na 2 główne klasy. Kontenery podstawowe i te wykorzystują kontenery podstawowe do wdrożenia polityki.
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.
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 .

— Ebrahim
źródło

5

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.

— Jonathan Wakely
źródło

3

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.

— Oferty
źródło

„Mały narzut pamięci na zawarty obiekt” nie jest prawdziwy dla listy. std :: list jest zaimplementowany jako podwójnie połączona lista, dlatego utrzymuje 2 wskaźniki na przechowywany obiekt, czego nie można zaniedbać.

— Hanna Khalil

Nadal liczyłbym dwa wskaźniki na przechowywany obiekt jako „małe”.

— Oferty

w porównaniu do czego? std :: forward_list to kontener, który sugerowano, że ma mniej metadanych przechowywanych na obiekt (tylko jeden wskaźnik). Podczas gdy std :: vector zawiera 0 metadanych na obiekt. Tak więc 2 wskaźniki nie podlegają negocjacjom w porównaniu z innymi pojemnikami

— Hanna Khalil

Wszystko zależy od wielkości twoich obiektów. Powiedziałem już, że wektor ma „Kompaktowy układ z niewielkim lub zerowym obciążeniem pamięci dla każdego zawartego obiektu”. Nadal powiedziałbym, że lista ma niewielki narzut pamięci w porównaniu do zestawu i mapy oraz nieco większy narzut pamięci niż wektor. Nie jestem do końca pewien, w jakim punkcie próbujesz stworzyć TBH!

— Oferty

Wszystkie kontenery oparte na trybie mają zwykle znaczny narzut ze względu na dynamiczny przydział, który rzadko przychodzi za darmo. O ile oczywiście nie używasz niestandardowego programu przydzielającego.

— MikeMB

2

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? (-:

— Vrdhn
źródło

5

Czy nie dlatego używamy iteratorów?

— Platinum Azure,

@PlatinumAzure Nawet iteratory powinny być członkami typedef .. Jeśli zmienisz typ kontenera, musisz także przejść i zmienić wszystkie definicje iteratorów ... naprawiono to w c ++ 1x!

— vrdhn

4

Dla ciekawskich jest to poprawka w C ++ 11: auto myIterator = whateverCollection.begin(); // <-- immune to changes of container type

— Czarny

1

Czy typedef Collection<Foo*> CollectionOfFoo;wystarczyłoby?

— Craig McQueen,

5

Jest raczej mało prawdopodobne, że możesz później zmienić zdanie i po prostu delegować do innego kontenera:

— strzeż się

1

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 ++

— John DiFini
źródło

1

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 .

— CS Pei
źródło