Welcher Container wird durch den Adaptor std::stack umhüllt?

Welcher Container wird eigentlich durch den Adaptor std::stack umhüllt? std::vector, std::deque oder std::list? Wie gelingt es std::stack, dass immer nur bei push(...) ein Element auf dem Heap angelegt wird (copycon), das bei pop() wieder destruiert wird (dtor)? Gibt es in Tutorials, Büchern ein vereinfachtes Modell zum Nachempfinden dieses Adaptors?

Erhard Henkes

Welcher Container wird eigentlich durch den Adaptor std::stack umhüllt? std::vector, std::deque oder std::list?

std::stack< T, std::deque < T, std::allocator< T > > >

Also std::deque

Man kann aber auch andere Container verwenden, wenn man diese angibt, z.B. vector (nicht effizient wegen ständigem Verschieben von Objekten durch copycon/dtor) oder list (effizient). EDIT: Dies gilt nur "vom Objekt her gesehen" (s.u.)

Erhard Henkes

Man kann sich das (ohne exceptions) auch schnell selbst schreiben:

//stdafx.h

#pragma once
#define WIN32_LEAN_AND_MEAN		
#include <stdio.h>
#include <tchar.h>
#include <iostream>
inline void wait()
{
    std::cin.clear();
    std::streambuf* pbuf = std::cin.rdbuf();
    std::streamsize size = pbuf->in_avail();
    std::cin.ignore(size);
    std::cin.get();
}

//Testklasse xINT.h

#pragma once

#define _TEST_
//#include <windows.h>
#include <conio.h>
#include <iostream>

/*
void textcolor(WORD color)
{
    SetConsoleTextAttribute(::GetStdHandle(STD_OUTPUT_HANDLE), color);
}

const int farbe1 =  3;
const int farbe2 = 15;
*/

class xINT
{

private:
  int num;  
  static int countCtor;
  static int countDtor;  
  static int countCopycon;  
  static int countOpAssign;  

public:
  xINT()
  {
      #ifdef _TEST_  
      //textcolor(farbe1);
      std::cout << this << ": " << "ctor" << std::endl;  
      //textcolor(farbe2);
      #endif
      ++countCtor;
  }

 ~xINT()
  {
      #ifdef _TEST_
      //textcolor(farbe1);  
      std::cout << this << ": " << "dtor" << std::endl;
      //textcolor(farbe2);
      #endif      
      ++countDtor;
  }

  xINT(const xINT& x)
  {
      #ifdef _TEST_
      //textcolor(farbe1);  
      std::cout << this << ": " << "copycon von " << std::dec << &x << std::endl;
      //textcolor(farbe2);
      #endif  
      num = x.getNum();
      ++countCopycon;
  }

  xINT& operator=(const xINT& x)
  {
      if (&x == this) // Quelle und Ziel identisch ==> Selbstzuweisung!!!
      {
          #ifdef _TEST_
          //textcolor(farbe1);            
          std::cout << this << ": Achtung! Selbstzuweisung mit op=" << std::endl;
          //textcolor(farbe2);
          #endif
		  ++countOpAssign;
		  return *this; //Schutz
      }
      #ifdef _TEST_
      //textcolor(farbe1);
      std::cout << this << ": " << "op= von " << std::dec << &x << std::endl;
      //textcolor(farbe2);
      #endif
      num = x.getNum();
      ++countOpAssign;
      return *this;
  }
  int getNum() const {return num;}
  void setNum(int val) {num = val;}
  static void statistik(std::ostream&);
  static void reset();
};

int xINT::countCtor     = 0;
int xINT::countDtor     = 0;  
int xINT::countCopycon  = 0;  
int xINT::countOpAssign = 0;  

void xINT::statistik(std::ostream& os)
{
  //textcolor(farbe1);  
  os   << "Ctor:    " << countCtor    << std::endl
       << "Dtor:    " << countDtor    << std::endl
       << "Copycon: " << countCopycon << std::endl
       << "op=:     " << countOpAssign;  
  //textcolor(farbe2);    
}    

void xINT::reset()
{
    countCtor     = 0;
    countDtor     = 0;  
    countCopycon  = 0;  
    countOpAssign = 0;  
}

std::ostream& operator<< (std::ostream& os, const xINT& x)
{
  os << x.getNum();
  return os;
}

std::istream& operator>> (std::istream& is, xINT& x)
{
  int i;
  is >> i;
  x.setNum(i);
  return is;
}

bool operator< (const xINT& a, const xINT& b)
{
    return a.getNum() < b.getNum();
}

bool operator> (const xINT& a, const xINT& b)
{
    return a.getNum() > b.getNum();
}

bool operator== (const xINT& a, const xINT& b)
{
    return a.getNum() == b.getNum();
}

bool operator!= (const xINT& a, const xINT& b)
{
    return a.getNum() != b.getNum();
}

//main

#include "stdafx.h"
#include "xINT.h"
#include <deque>

using namespace std;

template <class T>
class Stack
{
 private:
    std::deque<T> ct; //Umhuellter Container
 public:
    void      push (const T& i) { ct.push_back(i);   }
    void      pop()             { ct.pop_back();     }
    const T&  peek()  const     { return ct.back();  }
    bool      empty() const     { return ct.empty(); }
};

int _tmain()
{
    {
      Stack<xINT> stack;
      xINT x;

      cout << "\nStack wird gefuellt\n" << endl;
      for (int i=1; i<4; ++i)
      {
            x.setNum(i);
            stack.push(x);
            cout << stack.peek() << endl;
      }

      cout << "\nStack wird entleert\n" << endl;
      while ( stack.empty() == false )
      {
            cout << stack.peek() << endl;
            stack.pop();
      }

      wait();
    }
    wait();    
    return 0;
}

Ausgabe:

0012FF50: ctor

Stack wird gefuellt

003164C0: copycon von 0012FF50
1
003164C4: copycon von 0012FF50
2
003164C8: copycon von 0012FF50
3

Stack wird entleert

3
003164C8: dtor
2
003164C4: dtor
1
003164C0: dtor

0012FF50: dtor

So arbeitet auch std::stack, das per default std::deque umhüllt.

ok

HumeSikkins

Erhard Henkes schrieb:

Welcher Container wird eigentlich durch den Adaptor std::stack umhüllt? std::vector, std::deque oder std::list?
std::stack< T, std::deque < T, std::allocator< T > > >
Also std::deque

Man kann aber auch andere Container verwenden, wenn man diese angibt, z.B. vector (nicht effizient wegen ständigem Verschieben von Objekten durch copycon/dtor)

Das ein Vektor für diesen Einsatz ineffizient ist, kann so nicht stehen bleiben.
std::stack adaptiert die Methode push_back, fügt also immer am Ende des Vektors ein. D.h. ein Verschieben der Objekte ist nur dann nötig, wenn die Kapazität des Vektors nicht mehr ausreicht. Das darf aber nicht jedes Mal passieren, da vector::push_back laut Standard eine amortized constant time Operation ist.

RHBaum

naja, beim vector werden die "Vorteile" durch die stackumhuellung eigentlich verdeckt. bei nem stack will ich meist keinen zugriff auf die datem im Block oder nen zugriff ueber den index. ansonsten sollt ma sich die verwendung des stacks noch mal ueberlegen.

der vector hat aber noch eine sache die list und deque nicht haben, und die ihn auch fuern stack sinvoll machen (um nicht den allokator der stl ueberschreiben zu muessen).
Der stack kann bei der konstruktion schon seinen speicher anfordern, bei der list oder dequeue ohne anpassung des allokators hat man darauf kaum einfluss und das erste mal passiert definitv erst bein einfuegen des ersten elements.
Also wenn man ne allocierung beim einfuegen generell auf die konstruktion vorverlegen will, und man bisserl verschwwenderich mitm speicher dafuer umgehen kann, geht das mit nem vector ziemlich einfach ...

Ciao ...

Erhard Henkes

Das ein Vektor für diesen Einsatz ineffizient ist, kann so nicht stehen bleiben.

HumeSikkins hat Recht. Der Verschiebaufwand (copycon/dtor) ist bei std::vector deutlich höher, dafür aber auch der Overhead geringer (elementarer Zeiger, Array) als bei std::deque (abstrakter Zeiger, Array von Arrays). Bezüglich des Speichermanagements sollte eigentlich deque die Nase vorn haben. Der Ausgang des Rennens zwischen vector und deque hängt also von verschiedenen Dingen ab, so dass das Resultat nicht ohne weiteres vorher gesagt werden kann. Bei einfachen Objekten und ausreichend Speicher kann vector effizienter sein. Wer selbst experimentieren will, siehe: http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.8._Die_Klasse_Stack_als_Wrapper_f�r

Jester

Erhard Henkes schrieb:

Der Verschiebaufwand (copycon/dtor) ist bei std::vector deutlich höher

Wie kommst Du eigentlich auf copycon/dtor? Was ist da so besonders aufwändig? Ich sehe ein, daß bei manchen pushs das Teil wachsen muß. Da es aber nicht wieder schrumpft kann es so richtig schlimme Szenarien garnicht geben. Unter Umständen ist das seltene neu allokieren (vector wächst exponentiell) ja sogar schneller, als die einzelnen kleinen Speicheranforderungen der queue.

Nachteil ist auf jeden Fall, daß der stack nicht automatisch wieder schrumpft.

Erhard Henkes

Wie kommst Du eigentlich auf copycon/dtor?

Hier beziehe ich mich auf die im vector gespeicherten Objekte.
Sieht man gut mit einer Testklasse, sozusagen ein Spion im Bauch des vector: http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.3._Unsere_Testklasse_im_Container

Bei 10.000.000 push_back erfolgen zusätzlich noch 23.917.373 copycon/dtor-Verschiebungen beim "Rumrödeln" des vector. deque hat das nicht nötig, legt stattdessen ständig neue Arrays an, kostet Overhead, so dass vector sogar gewinnt, zumindest bei kleinen Objekten.

N = 10000000

StackV wird gefuellt

time stackV: 0.468 sec

Ctor:    1
Dtor:    33917373
Copycon: 33917373
op=:     0

StackD wird gefuellt

time stackD: 0.656 sec

Ctor:    0
Dtor:    10000000
Copycon: 10000000
op=:     0

siehe: http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.8._Die_Klasse_Stack_als_Wrapper_f�r

camper

Erhard Henkes schrieb:

Wie kommst Du eigentlich auf copycon/dtor?

Hier beziehe ich mich auf die im vector gespeicherten Objekte.
Sieht man gut mit einer Testklasse, sozusagen ein Spion im Bauch des vector: http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.3._Unsere_Testklasse_im_Container

Bei 10.000.000 push_back erfolgen zusätzlich noch 23.917.373 copycon/dtor-Verschiebungen beim "Rumrödeln" des vector. deque hat das nicht nötig, legt stattdessen ständig neue Arrays an, kostet Overhead, so dass vector sogar gewinnt, zumindest bei kleinen Objekten.
N = 10000000

StackV wird gefuellt

time stackV: 0.468 sec

Ctor:    1
Dtor:    33917373
Copycon: 33917373
op=:     0

StackD wird gefuellt

time stackD: 0.656 sec

Ctor:    0
Dtor:    10000000
Copycon: 10000000
op=:     0
siehe: http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.8._Die_Klasse_Stack_als_Wrapper_f�r

das ist allerdings worst-case performance. in realen nutzungsprofilen wird vector noch deutlich besser abschneiden. der vollständigkeit halber, sollte das ganze auch mit einer list-implmentation getestet werden. grundsätzlich kann diese für hinreichend grosse objekte und optimierte allocatoren durchaus günstiger als eine deque-implementation sein.
nebenbei: im C++ forum solltest du dich besser auf reines C++ beschränken - die geposteten bzw. verlinken teile enthalten eine menge unwesentlichen müll.

Jester

camper schrieb:

der vollständigkeit halber, sollte das ganze auch mit einer list-implmentation getestet werden.

Naja, das ist ja nur bedingt sinnvoll. Die list gibt einen Haufen Vorteile auf, damit man effizient mittendrin sachen einfügen und rausnehmen kann. Wenn Du sie nun in nen stack reinpackst kann sie davon nichts ausspielen und hat trotzdem alle Nachteile. Im Gegensatz zu deque muß jedesmal ne neue Node geholt werden.

Erhard Henkes

Beim Test mit 10.000.000 push_back mit unterliegendem std::list bricht der Rechner zusammen. Das Speichermanagement ist gegenüber std::deque mies.

camper

Jester schrieb:

camper schrieb:

der vollständigkeit halber, sollte das ganze auch mit einer list-implmentation getestet werden.

Naja, das ist ja nur bedingt sinnvoll. Die list gibt einen Haufen Vorteile auf, damit man effizient mittendrin sachen einfügen und rausnehmen kann. Wenn Du sie nun in nen stack reinpackst kann sie davon nichts ausspielen und hat trotzdem alle Nachteile. Im Gegensatz zu deque muß jedesmal ne neue Node geholt werden.

ich habe ja auch die bedingungen genannt, die erfüllt sein müssen, damit sich das lohnt - insbesonmder ein speziell optimierter allocator. schliesslich mag ein deque zwar mit weniger allocationen auskommen, aber die zugrunde liegende verwaltung ist auch nicht trivial. nur um mal im geposteten framework zu bleiben:

class xINT
{

private:
  int num; 
  struct { char dummy[500]; } dummy;
  static int countCtor;
  static int countDtor; 
  static int countCopycon; 
  static int countOpAssign; 

public:
  xINT()
      : num(), dummy()
  {
      ++countCtor;
  }
  xINT(const xINT& x)
      : num(x.num), dummy(x.dummy)
  {
      ++countCopycon;
  }
// usw.

um ein grosses T mit realisitischem kopierverhalten zu erhalten

const int N = 1000000; // machen wir etwas kleiner, sonst geht uns der speicher aus.

N = 1000000

StackV wird gefuellt

time stackV: 2.328 sec
Ctor: 1
Dtor: 3099788
Copycon: 3099788
op=: 0
StackD wird gefuellt

time stackD: 0.969 sec
Ctor: 0
Dtor: 1000000
Copycon: 1000000
op=: 0
StackL wird gefuellt

time stackL: 1.032 sec
Ctor: 0
Dtor: 1000000
Copycon: 1000000
op=: 0

das ergebnis ist plötzlich gar nicht mehr so eindeutig. zwar wird list hier immer noch geschlagen - aber der abstand ist nicht sonderlich groß. ich würde nie soweit gehen, zu behaupten, das list hier eine gute wahl sei - aber Erhard Henkes' kommentar bezogen auf eine einzige situation ist wohl kaum begründung genug.

Erhard Henkes

aber Erhard Henkes' kommentar bezogen auf eine einzige situation ist wohl kaum begründung genug.

Danke für den interessanten Hinweis, das muss wirklich breiter getestet und begründet werden, mit verschiedenen Objekten und sowohl an Speichergrenzen als auch weit weg davon.
Da STL std::deque gewählt hat, ist dies hoffentlich aufgrund intensiver Überlegungen und Tests erfolgt. Das sparsame Speichermanagement von std::deque ist sicher ein wichtiger Grund gewesen. Kennt jemand einen Link oder eine Literaturstelle, wo dieser Punkt untersucht bzw. diskutiert wird?

Eine interesante Stelle habe ich inzwischen (wieder) gefunden:
http://www.gotw.ca/gotw/054.htm

First, consider what happened for containers of a simple builtin type, int:
Times in ms     grow traverse      at  shuffle    sort
  ------------ ------- -------- ------- -------- -------
  vector<int>     1015       55     219      621    3624
  deque<int>       761      265     605     1370    7820
  list<int>       1595      420     n/a      n/a   16070
Here list was always the slowest, and the difference between vector and deque wasn't as great as several people had led me to expect. Of course, the performance differences between the containers will fade when you use a contained type that is more expensive to manipulate. What's interesting is that most of the differences go away even when the contained type is as simple (and common) as a struct E { int i; char buf[100]; };:
Times in ms     grow traverse      at  shuffle    sort
  ------------ ------- -------- ------- -------- -------
  vector<E>       3253       60     519     3825   17546
  deque<E>        3471      274     876     4950   21766
  list<E>         3740      497     n/a      n/a   15134
Now deque's performance disadvantage for even an intensive operation like sort is less than 25%.

Der untere Teil entspricht dem berechtigten Einwand von camper.

Erhard Henkes

Hier vergleicht man intensiv vector und deque:
http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp