vs deque wkładania w środkowej

Question

wiem, że deque jest bardziej efektywne niż wektora kiedy wstawki są z przodu lub na końcu i wektor jest lepiej, jeśli mamy do czynienia wskaźnik arytmetycznych. Ale który z nich należy użyć, gdy musimy wykonać wstawienia w środku.? i dlaczego.?

Answer 1

Można by pomyśleć, że a deque miałoby tę zaletę, ponieważ przechowuje dane podzielone na bloki. Jednak implementacja operator[] w stałym czasie wymaga, aby wszystkie te bloki miały taki sam rozmiar. Wstawienie lub usunięcie elementu w środku nadal wymaga zmiany wszystkich wartości po jednej stronie lub drugiej, tak jak w przypadku vector. Ponieważ kod vector jest prostszy i ma lepszą lokalizację do buforowania, powinien wyjść z przodu.

Answer 2

Deque będzie nadal wydajniejszy, ponieważ nie będzie musiał przesuwać połowy tablicy za każdym razem, gdy wstawi się element.

Oczywiście będzie to miało znaczenie, jeśli weźmie się pod uwagę dużą liczbę elementów, a nawet wtedy, gdy zalecane jest przeprowadzenie testu porównawczego i sprawdzenie, który z nich działa lepiej w danym przypadku. Pamiętaj, że premature optimization is the root of all evil.

Answer 3

std::dequemoże lepiej w dużych pojemnikach, ponieważ jest zwykle implementowany w postaci połączonej sekwencji ciągłych bloków danych, a nie do jednego bloku używanego w std::vector. Tak więc wstawienie w środku spowodowałoby skopiowanie mniejszej ilości danych z jednego miejsca do drugiego i potencjalnie mniejszą realokację.

Oczywiście, niezależnie od wielkości kontenerów i kosztów kopiowania przechowywanych elementów. Z C++ 11 przenieść semantykę, koszt tego drugiego jest mniej ważne. Ale w końcu jedynym sposobem poznania jest profilowanie za pomocą realistycznej aplikacji.

Answer 4

Kryteria wyboru z pojemników bibliotecznych standard jest, wybrać pojemnik zależnie od:

1. typ danych, które chcesz przechowywać &
2. rodzaju operacji, które chcesz wykonać na danych.

Jeśli chcesz wykonać dużą liczbę wstawek w środku, lepiej jest użyć opcji std::list.

Jeśli wybór jest tylko między std::deque i std::vector następnie Istnieje wiele czynników do rozważenia:

• Zazwyczaj jest jeszcze jedna droga pośrednia w przypadku deque dostępu do elementów, więc elementem dostęp a ruch iteratora jest zazwyczaj nieco wolniejszy.
• W systemach, w których ograniczenia wielkości bloków pamięci, blokada może zawierać więcej elementów, ponieważ wykorzystuje więcej niż jeden blok pamięci. Zatem max_size() może być większy dla kotów.
• Deques nie zapewniają wsparcia w zakresie kontroli wydajności i momentu realokacji. W szczególności, jakiekolwiek wstawienie lub usunięcie elementów innych niż na początku lub końcu unieważnia wszystkie wskaźniki, odwołania i iteratory, które odnoszą się do elementów zasobnika. Jednak realokacja może przebiegać lepiej niż dla wektorów, ponieważ zgodnie z ich typową wewnętrzną strukturą , deki nie muszą kopiować wszystkich elementów podczas realokacji.
• Bloki pamięci może się uwolniony, gdy nie są już używane, a więc wielkość pamięci o deque może się kurczyć (nie jest to warunek nałożony przez standardowy ale większość implementacji zrobić)