QVector vs QList

Mam listę liczb całkowitych, które muszę powtórzyć, ale tablica jest nieodpowiednia. Jakie są różnice między vectorsi i listsczy jest coś, co muszę wiedzieć, zanim wybiorę typ?

Żeby było jasne, przeczytałem dokumentację QT, ale to jest zakres tego, co wiem:

QList<T>, QLinkedList<T>i QVector<T>zapewniają podobną funkcjonalność. Oto przegląd:

• W większości przypadków QListjest to właściwa klasa do użycia. Jego interfejs API oparty na indeksach jest wygodniejszy niżQLinkedList's interfejs API oparty na iteratorach i zwykle jest szybszy niż QVectorze względu na sposób, w jaki przechowuje swoje elementy w pamięci. Rozwija się również do mniejszej ilości kodu w pliku wykonywalnym.
• Jeśli potrzebujesz prawdziwej listy połączonej, z gwarancjami wstawiania w stałym czasie na środku listy i iteratorami do elementów zamiast indeksów, użyj QLinkedList .
• Jeśli chcesz, aby elementy zajmowały sąsiednie pozycje w pamięci, użyj QVector.

QVectorjest w większości analogiczny do std::vector, jak można się domyślić z nazwy. QListjest bliżej boost::ptr_deque, pomimo pozornego skojarzenia z std::list. Nie przechowuje obiektów bezpośrednio, ale zamiast tego przechowuje do nich wskaźniki. Zyskujesz wszystkie korzyści wynikające z szybkiego wstawiania na obu końcach, a realokacje obejmują tasowanie wskaźników zamiast konstruktorów kopiujących, ale tracisz lokalność przestrzenną rzeczywistego std::dequelub std::vectori zyskujesz dużo alokacji sterty. Ma pewne decyzje, aby uniknąć alokacji sterty dla małych obiektów, odzyskać lokalność przestrzenną, ale z tego, co rozumiem, dotyczy to tylko rzeczy mniejszych niż int.

QLinkedListjest analogiczny do std::listi ma wszystkie wady. Ogólnie rzecz biorąc, powinien to być Twój ostatni wybór pojemnika.

Biblioteka QT bardzo sprzyja używaniu QListobiektów, więc faworyzowanie ich we własnym kodzie może czasami uniknąć niepotrzebnej nudy. Dodatkowe użycie sterty i losowe rozmieszczenie rzeczywistych danych może teoretycznie zaszkodzić w niektórych okolicznościach, ale często jest niezauważalne. Sugerowałbym więc używanie, QListdopóki profilowanie nie zasugeruje zmiany na QVector. Jeśli spodziewasz się, że ciągła alokacja będzie ważna [czytaj: łączysz się z kodem, który oczekuje a T[]zamiast a QList<T>], może to być również powód, aby zacząć od QVectorrazu.

Jeśli pytasz ogólnie o kontenery i właśnie użyłeś dokumentów QT jako odniesienia, powyższe informacje są mniej przydatne.

An std::vectorto tablica, której rozmiar można zmieniać. Wszystkie elementy są przechowywane obok siebie i masz szybki dostęp do poszczególnych elementów. Wadą jest to, że wstawki są skuteczne tylko na jednym końcu. Jeśli umieścisz coś w środku lub na początku, musisz skopiować inne obiekty, aby zrobić miejsce. W notacji duże-o, wstawienie na końcu to O (1), wstawienie gdziekolwiek indziej to O (N), a dostęp swobodny to O (1).

An std::dequejest podobny, ale nie gwarantuje, że obiekty są przechowywane obok siebie i umożliwia wstawianie na obu końcach O (1). Wymaga również jednoczesnego przydzielania mniejszych fragmentów pamięci, co czasami może być ważne. Dostęp losowy to O (1), a wstawienie w środku to O (N), tak samo jak w przypadku a vector. Lokalność przestrzenna jest gorsza niżstd::vector , ale obiekty są zwykle skupione, więc zyskujesz pewne korzyści.

Lista std::listjest połączona. Wymaga największego narzutu pamięci spośród trzech standardowych kontenerów sekwencyjnych, ale oferuje szybkie wstawianie w dowolnym miejscu ... pod warunkiem, że wiesz z wyprzedzeniem, gdzie należy wstawić. Nie oferuje losowego dostępu do poszczególnych elementów, więc musisz iterować w O (N). Ale kiedy już tam jest, rzeczywiste wstawienie to O (1). Największą korzyścią std::listjest to, że można je szybko połączyć ... jeśli przesuniesz cały zakres wartości do innego std::list, cała operacja to O (1). Znacznie trudniej jest również unieważnić odniesienia do listy, co czasami może być ważne.

Generalnie wolę std::dequeto std::vectorrobić, chyba że muszę mieć możliwość przekazania danych do biblioteki, która oczekuje surowej tablicy. std::vectorjest gwarantowana ciągłość, więc &v[0]działa w tym celu. Nie pamiętam, kiedy ostatnio użyłem a std::list, ale prawie na pewno dlatego, że potrzebowałem silniejszej gwarancji, że referencje pozostaną ważne.

Rzeczy się zmieniły

Jesteśmy teraz w Qt 5.8 i wiele się zmieniło, więc dokumentacja. Daje jasną i inną odpowiedź na to pytanie:

QVectorpowinien być Twoim domyślnym pierwszym wyborem. QVector<T>zazwyczaj daje lepszą wydajność niż QList<T>, ponieważ QVector<T>zawsze przechowuje swoje elementy sekwencyjnie w pamięci, gdzie QList<T>alokuje swoje elementy na stercie, chyba że sizeof(T) <= sizeof(void*)zadeklarowano T jako a Q_MOVABLE_TYPElub a Q_PRIMITIVE_TYPEusing Q_DECLARE_TYPEINFO.

Zobacz wady i zalety używania, QListaby uzyskać wyjaśnienie. Jednak QListjest używany w całym API Qt do przekazywania parametrów i zwracania wartości. Służy QListdo łączenia się z tymi interfejsami API.

W QVectorjest podobny do std::vector. QLinkedListjest podobny do std::list. QListjest wektorem indeksowanym, ale pozycja pamięci nie jest gwarantowana (podobnie jak std::deque).

Z dokumentu QtList:

• QList do użycia w większości przypadków. W przypadku struktur z tysiącem elementów umożliwia wydajne wstawianie w środku i zapewnia indeksowany dostęp. prepend()i append()bardzo szybko, ponieważ pamięć jest wstępnie alokowana na obu końcach wewnętrznej tablicy. QList<T>jest tablicą wskaźników typu T. Jeśli T ma wskaźnik lub Qt współdzielony typ wskaźnika, obiekt jest przechowywany bezpośrednio w tablicy

• QVectorbyć preferowanym w przypadku wielu append()lub insert()nowych elementów o rozmiarze większym niż wskaźnik, ponieważ QVectorprzydziela pamięć dla swoich elementów w jednej alokacji sterty. W przypadku QListwstawienia lub dołączenia nowego elementu wymaga alokacji pamięci nowego elementu na stercie. Krótko mówiąc, jeśli chcesz, aby elementy zajmowały sąsiednie pozycje w pamięci lub jeśli Twoje elementy są większe niż wskaźnik i chcesz uniknąć narzutu związanego z przydzielaniem ich pojedynczo na stercie w czasie wstawiania, użyj QVector.

QVector jest jak tablica, która może zmieniać rozmiar (zwiększać lub zmniejszać), ale wiąże się z dużymi transakcjami, obliczeniami i czasem.

Na przykład, jeśli chcesz dodać element, tworzona jest nowa tablica, wszystkie elementy są kopiowane do nowej tablicy, nowy element jest dodawany na końcu, a stara tablica jest usuwana. I odwrotnie, aby również usunąć.

Jednak QLinkedListdziała ze wskaźnikami. Tak więc, kiedy tworzony jest nowy element, przydzielana jest tylko nowa przestrzeń pamięci i jest ona łączona z jedynym fragmentem pamięci. Ponieważ działa ze wskaźnikami, jest szybszy i wydajny.

Jeśli masz listę elementów, których nie spodziewasz się zmienić rozmiaru, QVectorprawdopodobnie jest dobra, ale zwykle QLinkedListjest używana do większości celów.