3. Unterschied zwischen STL vector und deque

Unterschied zwischen STL vector und deque

  • Z

    Hallo,

    in dem Buch "Die C++ Standardbibliothek" von Kuhlins&Schader wird behauptet,
    dass der wesentliche Unterschied zwischen einem STL vector und einer STL deque
    in dem Einfügen/Entfernen von Elementen an erster Position besteht. Diese
    Operation hat bei einem vector die Komplexität O(n), bei einer deque dagegen
    O(1). Des Weiteren schreiben die Autoren, dass wegen des komplexeren Aufbaus
    einer deque im Vergleich zu einem vector bei gleicher Funktionalität das
    Laufzeitverhalten bei Verwendung einer deque statt vector deshalb etwas
    schlechter ist.

    Leider wird der letzte Punkt nicht weiter ausgeführt. Könnt Ihr mir praktische
    Beispiele nennen, die der Performace-Verlust bei einer deque im Vergleich zu
    einem vector aussieht und wann eine deque einem vektor vorzuziehen ist, falls
    Einfügen/Entfernen vorne unwesentlich für die Anwendung ist.

    Vielen Dank.
    Gruß,
    Christian

    0
  • E

    Eine deque ist ein array von arrays, daher ist das "interne Management" aufwändiger als bei vector. Schau mal hier beim Thema Stack mit vector oder deque:
    http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.8._Die_Klasse_Stack_als_Wrapper_f�r

    0
  • B

    Hi!

    Bitte korrigiert mich, sollte ich falsch liegen. Soweit ich weiss, ist ein 'deque' auf zwei Arten implementierbar:
    1.) als Array (ein einzelnes sollte reichen), mit zusaetzlicher Speicherung der Indizes des 'heads' und des 'tails'.
    2.) als doppelt verkettete Liste. Damit ergibt sich auch O(1) bei Zugriff auf dass erste/letzte Element. Beim Zugriff auf ein anderes Element muss ueber die Liste iteriert werden, beim Vector laesst es sich per Index ansprechen, wodurch in diesem Fall der Vector Performancevorteile bietet.

    0
  • .

    bumbytie schrieb:

    1.) als Array (ein einzelnes sollte reichen), mit zusaetzlicher Speicherung der Indizes des 'heads' und des 'tails'.

    Stimmt, aber nur mit dynamischem Array.

    bumbytie schrieb:

    2.) als doppelt verkettete Liste. Damit ergibt sich auch O(1) bei Zugriff auf dass erste/letzte Element. Beim Zugriff auf ein anderes Element muss ueber die Liste iteriert werden, beim Vector laesst es sich per Index ansprechen, wodurch in diesem Fall der Vector Performancevorteile bietet.

    Der Standard sagt glaube ich, dass der Indexzugriff amortisiert O(1) sein muss, das ist aber mit einer Liste nicht implementierbar.
    Die g++ Implementierung ist, wie Erhard Henkes sagte, ein dynamisches Array von dynamischen Arrays, damit lässt sich das realisieren. Hier der (für den Indexzugriff wichtige) operator+= des Iteratortyps:

    Self& operator+=(difference_type n)
{
    const difference_type offset = n + (_current - _first);
    if  (offset >= 0 && offset < difference_type(_buffer_size()))
        _current += n;
    else
    {
        const difference_type node_offset =
	      offset > 0 ? offset / difference_type(_buffer_size())
	                 : -difference_type((-offset - 1) / _buffer_size()) - 1;
	    _set_node(_node + node_offset);
	    _current = _first + (offset - node_offset * difference_type(_buffer_size()));
    }
    return *this;
}

    (ich habe die Bezeichner etwas vereinfacht, das _-Präfix heißt Member)
    _set_node setzt die (normalen Zeiger) _first und _last auf die entsprechenden Elemente im neuen Knoten (welcher hier eines der eigentlichen Arrays ist), ist also quasi der Indexzugriff auf das darüberliegende Array. Fragen dazu?

    0
Anmelden zum Antworten