Jak skutecznie wybrać kontener biblioteki standardowej w C ++ 11?

Jest dobrze znany obraz (ściągawka) o nazwie „Wybór kontenera w C ++”. Jest to schemat blokowy wyboru najlepszego pojemnika do zamierzonego zastosowania.

Czy ktoś wie, czy istnieje już wersja C ++ 11 tego?

To jest poprzednie:

Nie żebym o tym wiedział, ale myślę, że można to zrobić tekstowo. Poza tym wykres jest nieco zepsuty, ponieważ listw ogóle nie jest tak dobrym pojemnikiem, ani nie jest forward_list. Obie listy są bardzo wyspecjalizowanymi kontenerami do zastosowań niszowych.

Aby zbudować taki wykres, potrzebujesz tylko dwóch prostych wskazówek:

• Najpierw wybierz semantykę
• Gdy dostępnych jest kilka opcji, wybierz najprostszy

Martwienie się o wydajność jest zwykle na początku bezużyteczne. Wielkie rozważania dotyczące O pojawiają się dopiero wtedy, gdy zaczniesz zajmować się kilkoma tysiącami (lub więcej) przedmiotów.

Istnieją dwie duże kategorie kontenerów:

• Kontenery asocjacyjne : mają findoperację
• Proste kontenery sekwencji

a następnie można zbudować kilka adapterów na nich: stack, queue, priority_queue. Zostawię tutaj adaptery, są wystarczająco wyspecjalizowane, aby można je było rozpoznać.

Pytanie 1: Stowarzyszenie ?

• Jeśli chcesz łatwo wyszukiwać za pomocą jednego klucza, potrzebujesz kontenera asocjacyjnego
• Jeśli chcesz posortować elementy, potrzebujesz uporządkowanego kontenera asocjacyjnego
• W przeciwnym razie przejdź do pytania 2.

Pytanie 1.1: Zamówione ?

• Jeśli nie potrzebujesz konkretnego zamówienia, użyj unordered_kontenera, w przeciwnym razie skorzystaj z jego tradycyjnie zamówionego odpowiednika.

Pytanie 1.2: Oddzielny klucz ?

• Jeśli klucz jest oddzielony od wartości, użyj a map, w przeciwnym razie użyj aset

Pytanie 1.3: Duplikaty ?

• Jeśli chcesz zachować duplikaty, użyj a multi, w przeciwnym razie nie rób tego.

Przykład:

Załóżmy, że mam kilka osób z przypisanym do nich unikalnym identyfikatorem i chciałbym uzyskać dane osoby z jego identyfikatora tak prosto, jak to możliwe.

1. Chcę findfunkcji, a więc kontenera asocjacyjnego

   1.1. Nie mogłem mniej przejmować się porządkiem, więc unordered_kontenerem

   1.2. Mój klucz (ID) jest niezależny od wartości, z którą jest powiązany, a zatem amap

   1.3. Identyfikator jest unikalny, więc żaden duplikat nie powinien się wkradać.

Ostateczna odpowiedź brzmi: std::unordered_map<ID, PersonData>.

Pytanie 2: Pamięć stabilna ?

• Jeśli elementy powinny być stabilne w pamięci (tj. Nie powinny się poruszać, gdy sam kontener jest modyfikowany), użyj niektórych list
• W przeciwnym razie przejdź do pytania 3.

Pytanie 2.1: Które ?

• Zgódź się na list; a forward_listjest przydatna tylko w przypadku mniejszego zużycia pamięci.

Pytanie 3: Rozmiar dynamiczny ?

• Jeśli kontener ma znany rozmiar (w czasie kompilacji), a rozmiar ten nie zostanie zmieniony w trakcie działania programu, a elementy są domyślnie konstruowalne lub możesz podać pełną listę inicjalizacyjną (używając { ... }składni), użyj array. Zastępuje tradycyjną tablicę C, ale oferuje wygodne funkcje.
• W przeciwnym razie przejdź do pytania 4.

Pytanie 4: Podwójnie zakończone ?

• Jeśli chcesz mieć możliwość usuwania przedmiotów zarówno z przodu, jak iz tyłu, użyj a deque, w przeciwnym razie użyj vector.

Zauważysz, że domyślnie, jeśli nie potrzebujesz kontenera asocjacyjnego, Twoim wyborem będzie plik vector. Okazuje się, że jest to również rekomendacja Suttera i Stroustrupa .

Podoba mi się odpowiedź Matthieu, ale zamierzam powtórzyć schemat blokowy w następujący sposób:

Kiedy NIE używać std :: vector

Domyślnie, jeśli potrzebujesz pojemnika z rzeczami, użyj std::vector. Zatem każdy inny kontener jest uzasadniony tylko przez zapewnienie jakiejś funkcjonalności alternatywnej dla std::vector.

Konstruktorzy

std::vectorwymaga, aby jego zawartość była możliwa do zbudowania, ponieważ musi mieć możliwość tasowania przedmiotów wokół. Nie jest to strasznym obciążeniem dla zawartości (pamiętaj, że domyślne konstruktory nie są wymagane , dzięki emplaceitd.). Jednak większość pozostałych kontenerów nie wymaga żadnego konkretnego konstruktora (ponownie dzięki emplace). Więc jeśli masz obiekt, w którym absolutnie nie możesz zaimplementować konstruktora przenoszenia, będziesz musiał wybrać coś innego.

A std::dequebyłby ogólnym zamiennikiem, mającym wiele właściwości std::vector, ale można wstawić tylko na obu końcach deque. Wkładki w środku wymagają przesuwania. A std::listnie nakłada żadnych wymagań na zawartość.

Potrzebuje Bools

std::vector<bool>nie jest. Cóż, to standard. Ale nie jest to vectorw zwykłym sensie, ponieważ operacje, które std::vectorzwykle na to pozwalają, są zabronione. I z całą pewnością nie zawiera bools .

Dlatego jeśli potrzebujesz prawdziwego vectorzachowania z pojemnika bools, nie uzyskasz go z std::vector<bool>. Więc będziesz musiał spłacić std::deque<bool>.

Badawczy

Jeśli potrzebujesz znaleźć elementy w kontenerze, a tag wyszukiwania nie może być tylko indeksem, być może będziesz musiał porzucić std::vectorna korzyść seti map. Zwróć uwagę na słowo kluczowe „ może ”; posortowany std::vectorjest czasem rozsądną alternatywą. Lub Boost.Container's flat_set/map, który implementuje sortowany plik std::vector.

Obecnie istnieją cztery ich odmiany, każda z własnymi potrzebami.

• Użyj a, mapgdy tag wyszukiwania nie jest tym samym, co przedmiot, którego szukasz. W przeciwnym razie użyj pliku set.
• Użyj, unorderedgdy masz dużo elementów w kontenerze i wydajność wyszukiwania absolutnie musi być O(1), a nie O(logn).
• Użyj, multijeśli potrzebujesz wielu elementów, które mają ten sam tag wyszukiwania.

Zamawianie

Jeśli chcesz, aby kontener elementów był zawsze sortowany na podstawie określonej operacji porównania, możesz użyć pliku set. Lub multi_setjeśli chcesz, aby wiele elementów miało tę samą wartość.

Lub możesz użyć posortowanego std::vector, ale będziesz musiał to posortować.

Stabilność

Czasami problemem jest unieważnienie iteratorów i odwołań. Jeśli potrzebujesz listy elementów, takiej, że masz iteratory / wskaźniki do tych elementów w różnych innych miejscach, to std::vectorpodejście do unieważniania może nie być odpowiednie. Każda operacja wstawiania może spowodować unieważnienie, w zależności od bieżącego rozmiaru i pojemności.

std::listoferuje solidną gwarancję: iterator i powiązane z nim odniesienia / wskaźniki są unieważniane tylko wtedy, gdy sam element zostanie usunięty z kontenera. std::forward_listjest, jeśli pamięć jest poważnym problemem.

Jeśli jest to zbyt mocna gwarancja, std::dequeoferuje słabszą, ale użyteczną gwarancję. Unieważnienie wynika z wstawień w środku, ale wstawienia na początku lub końcu powoduje unieważnienie tylko iteratorów , a nie wskaźników / odwołań do elementów w kontenerze.

Wydajność wstawiania

std::vector zapewnia tylko tanie wkładanie na końcu (a nawet wtedy staje się drogie, jeśli wydmuchujesz moc).

std::listjest drogi pod względem wydajności (każdy nowo wstawiony element kosztuje alokację pamięci), ale jest spójny . Oferuje również czasami niezbędną możliwość tasowania przedmiotów praktycznie bez kosztów wydajności, a także wymiany przedmiotów z innymi std::listpojemnikami tego samego typu bez utraty wydajności. Jeśli potrzebujesz dużo tasować rzeczy , użyj std::list.

std::dequezapewnia ciągłe wkładanie / wyjmowanie z głowy i ogona, ale wprowadzenie w środku może być dość kosztowne. Więc jeśli chcesz dodać / usunąć rzeczy z przodu, jak iz tyłu, std::dequemoże być tym, czego potrzebujesz.

Należy zauważyć, że dzięki semantyce przenoszenia std::vectorwydajność wstawiania może nie być tak zła, jak kiedyś. Niektóre implementacje implementowały formę opartego na semantyce przenoszenia elementów (tzw. „Swaptimizacja”), ale teraz, gdy przenoszenie jest częścią języka, jest narzucone przez standard.

Brak alokacji dynamicznych

std::arrayjest dobrym kontenerem, jeśli chcesz mieć jak najmniej alokacji dynamicznych. To tylko opakowanie wokół tablicy C; oznacza to, że jego rozmiar musi być znany w czasie kompilacji . Jeśli możesz z tym żyć, użyj std::array.

Biorąc to pod uwagę, używanie std::vectori określanie reserverozmiaru będzie działać równie dobrze w przypadku ograniczonego std::vector. W ten sposób rzeczywisty rozmiar może się różnić i masz tylko jedną alokację pamięci (chyba że wydmuchasz pojemność).

Oto wersja powyższego schematu blokowego w języku C ++ 11. [pierwotnie opublikowany bez podawania autora, Mikaela Perssona ]

Oto szybki obrót, chociaż prawdopodobnie wymaga pracy

Should the container let you manage the order of the elements?
Yes:
  Will the container contain always exactly the same number of elements? 
  Yes:
    Does the container need a fast move operator?
    Yes: std::vector
    No: std::array
  No:
    Do you absolutely need stable iterators? (be certain!)
    Yes: boost::stable_vector (as a last case fallback, std::list)
    No: 
      Do inserts happen only at the ends?
      Yes: std::deque
      No: std::vector
No: 
  Are keys associated with Values?
  Yes:
    Do the keys need to be sorted?
    Yes: 
      Are there more than one value per key?
      Yes: boost::flat_map (as a last case fallback, std::map)
      No: boost::flat_multimap (as a last case fallback, std::map)
    No:
      Are there more than one value per key?
      Yes: std::unordered_multimap
      No: std::unordered_map
  No:
    Are elements read then removed in a certain order?
    Yes:
      Order is:
      Ordered by element: std::priority_queue
      First in First out: std::queue
      First in Last out: std::stack
      Other: Custom based on std::vector????? 
    No:
      Should the elements be sorted by value?
      Yes: boost::flat_set
      No: std::vector

Możesz zauważyć, że różni się to znacznie od wersji C ++ 03, głównie ze względu na fakt, że naprawdę nie lubię połączonych węzłów. Połączone kontenery węzłów mogą zwykle być lepsze od wydajności niepołączonego kontenera, z wyjątkiem kilku rzadkich sytuacji. Jeśli nie wiesz, jakie są te sytuacje i masz dostęp do przyspieszenia, nie używaj kontenerów połączonych węzłów. (std :: list, std :: slist, std :: map, std :: multimap, std :: set, std :: multiset). Ta lista skupia się głównie na kontenerach o małych i średnich ścianach, ponieważ (A) to 99,99% tego, co mamy do czynienia w kodzie, a (B) Duża liczba elementów wymaga niestandardowych algorytmów, a nie różnych kontenerów.