Speichererweiterung

RussianTux

int main(void)
{
	int * pointer;
	pointer = new int[10];

	pointer[1] = 10;
	pointer[2] = 2;
	pointer[3] = 37;
	//...

	int * buffer;
	buffer = new int[10];
	for(int c = 0; c < 10; c++)
	{
		buffer[c] = pointer[c];
	}

	delete [] pointer;
	pointer = new int[20];

	for(int c = 0; c < 10; c++)
	{
		pointer[c] = buffer[c];
	}
	delete [] buffer;

	delete [] pointer;
	return 0;
}

Der oben beschriebene Quellcode würde das dynamisches Array "pointer[]" um 10 Speicherstellen erweitern, das Problem ist nur, dass das Array erst umkopiert, gelöscht und dann wieder angelegt werden muss, was bei mehreren Millionen Elementen sehr teuer in Hinsicht auf Ressourcen werden könnte.

Natürlich kann man einen der dynamischen STL Container wie vector oder list verwenden, aber wie könnte man das Problem auch ohne sie lösen?

Wie könnte man also einen Speicherblock bzw. Array erweitern, ohne ihn umsortieren / umkopieren / umstellen zu müssen?

p.s. wie sieht es denn bei std::list aus, wie wird denn dort der Speicher verwaltet, da dort schließlich Elemente mitten aus der Schlange gelöscht und nur die Adressen der Nachbaren geändert werden?

SeppJ

RussianTux schrieb:

Wie könnte man also einen Speicherblock bzw. Array erweitern, ohne ihn umsortieren / umkopieren / umstellen zu müssen?

Im allgemeinen gar nicht. Falls man malloc aus der C Bibliothek benutzt hat (was nur bei POD sauber funktioniert!), kann man realloc verwenden, welches nur bei Bedarf kopiert (aber eventuell doch).

p.s. wie sieht es denn bei std::list aus, wie wird denn dort der Speicher verwaltet, da dort schließlich Elemente mitten aus der Schlange gelöscht und nur die Adressen der Nachbaren geändert werden?

Die list benutzt keinen aneinanderhängenden Speicherbereich. In der üblichen Implementierung wird jedes Element einzeln angelegt und enthält einen Verweis auf seinen Vorgänger und seinen Nachfolger.

P.S.: Du könntest natürlich alles ganz anders machen und statt new eine Kombination von malloc (oder anderen Methoden, rohen Speicher zu holen) und placement new darauf anwenden.

Dobi

Edit: Und wieder weg damit. Ich will doch nur einmal erster sein.

SeppJ

Dobi schrieb:

Edit: Und wieder weg damit. Ich will doch nur einmal erster sein.

Da musst du später aufstehen .

Aber lass verspätete Antworten ruhig stehen, doppelt hält besser.

Dobi

Joa, wenn's was nützliches gewesen wär, hätt' ich's da gelassen, aber es war eigentlich nur deins in nicht-ganz-so-gut.

otze

wenn du einen größeren Speicherbereich brauchst, musst du umkopieren. Das ist in der Praxis aber nicht mal halb so kostenintensiv, wie es sich anhört. kopieren geht fix.

Oh und bevor du solche Speicherfriemeleien machst, benutze wirklich direkt std::vector. Der macht die Speichererweiterung auch etwas schlauer als +10 Elemente.

RussianTux schrieb:

umkopiert, gelöscht und dann wieder angelegt werden muss

Ich seh zwar nicht ein, wozu du den Buffer brauchst (man kann doch direkt in das Zielarray kopieren). Kopieren tut man in C++ allerdings mit std::copy.

Dein Code ohne Container-Overhead in C++11:

#include <memory>
#include <algorithm>

int main()
{
  constexpr int size_old = 10, size_new = 20;

  std::unique_ptr<int[]> pointer {new int[size_old]};

  pointer[1] = 10;
  pointer[2] = 2;
  pointer[3] = 37;
  //...

  // Am besten in eine eigene Funktion auslagern
  { std::unique_ptr<int[]> buffer {new int[size_new]};
    std::copy(pointer.get(), pointer.get() + size_old, buffer.get());
    std::swap(buffer, pointer);
  }
}

SeppJ

nicht-ganz-so-gut schrieb:

Dein Code ohne Container-Overhead in C++11:

Dein Code ohne Overhead in C++98:

#include <vector>