vector = wie kann man prüfen ob der platz belegt ist

ConfusedGuy

hi,

hab mal wieder ne frage zu vectoren.
wenn ich einen vector habe, von dem ich weiß wie groß er sein muss und nach und nach an unterschiedlichen stellen elemente einfügen will, wie kann ich dabei überprüfen ob ein platz bereits belegt ist?

gibt es da eine einfache art das zu machen oder muss man sich da was ausdenken? kann ich zb. den vector mit NULL oder so initialisieren und dann einfach die gewisse stelle gegen NULL prüfen?

danke euch schon mal,

grüße

bluecode

hi,

normalerweise nimmt man für sowas eine list und keinen vector ;), da das einfügen an irgendeiner Stelle des vectors langsam im Vgl. zur list ist.

ConfusedGuy

da mein vector bereits eine bestimmte größe hat, sollte das nach und nach einfügen von elementen kein problem sein und auch keine performance einbuße verursachen. außerdem brauche ich einen vector

also in der reihenfolge:
1. vector erstellen
2. größe festlegen
3. werte aus datei holen
4. werte in array ablegen

beim schritt 4 ist es für mich wichtig an welcher stelle sie im vector sind und ob sich an der stelle bereits ein elemten befindet.

hoffe wird nun klarer was ich vorhab

LordJaxom

Kommt auf die Elemente des vectors an. Wenn Du Zeiger speicherst leg einen Nullzeiger an die unbenutzten Stellen. Wenn Du Objekte speicherst definiere ein leeres Objekt, z.B. durch ein Flag oder indem Du die Belegung eines Pflichtfeldes prüfst.

Bei einem std::string könnte man z.B. empty() als Kriterium nehmen, wenn man voraussetzt dass bei einem gültigen Element der String nicht "" sein darf.

ConfusedGuy

mmhhh, habe gehofft es gebe etwas wie .is_empty_at( index) oder so. oder halt eine einfachere art.

handelt sich um objekte...dann werde ich das wohl mit einem "standart"-objekt machen müssen.

oder hat noch wer ne idee?

Ponto

ConfusedGuy schrieb:

mmhhh, habe gehofft es gebe etwas wie .is_empty_at( index) oder so. oder halt eine einfachere art.

handelt sich um objekte...dann werde ich das wohl mit einem "stan****"-objekt machen müssen.

oder hat noch wer ne idee?

Irgendwo würde müsste aber dann die Information mit gespeichert werden und das kostet Speicherplatz, den man normalerweise nicht verschwenden möchte. Wenn du das aber haben möchtest, kannst du ja ein paralleles Array mitführen:

std::vector<Object> obj(5000);
std::vector<bool> belegt(5000, false);

Dieser Vektor benötigt dann ungefähr n/8 Bytes an Speicherplatz.

KingOfTheBlueMouse

bool *is_empty = new bool[vektor.size()];

Edit:
ich war zu langsam

Ist es nicht möglich den Vector mit Standardwerten zu füllen. Bei bedarf kannst du dann abfragen ob dieser Standardwert noch erhalten ist. Hier ein kleines Beispiel:

/**
 * Erzeugt einen Vector mit 50000 Zahlen. Diese werden
 * mit dem Wert 0 initialisiert
*/
vector<int> v(50000, 0)

Eine Alternative zu der oben bereits vorgestellten Lösung wäre die Verwendung von Strukturen...

#include <iostream> 
#include <vector>
using namespace std;

template <class T>
struct Entry {
  T value;
  bool valid;

  Entry(T v, bool ok)
    : value(v), valid(ok)
  {}

};

int main()
{
  typedef vector<Entry<int> > vec_type;
  vec_type v(50, Entry<int>(0, true));

  for (int i=0; i<=25; ++i) {
    v[i].value = i;
    v[i].valid = false;
  }

  if (v[5].valid) v[5].value=10;
}

Dies bringt zwar _kein_ Performance-Vorteil, aber die Information ob der Wert verändert wurde ist "verknüpft" mit der eigentlichen Variablen.

ConfusedGuy

mmhhh, dann werde ich es wohl einfach über eine objekt realisieren, wie weiter oben aufgeführt.

danke euch aber für eure hilfe

Ponto

Bei der Speicherung eines bool in der Struktur und der Verwendung von new bool[vector.size()] sollte man immer bedenken, dass ein bool mindestens sizeof(1) hat und damit wohl mindestens ein Byte belegt.

Ponto

Wenn die Indizes viel größer werden können als die Menge der zu initialisierenden Objekte, oder wenn du Objekte nur beim ersten Zugriff initialisieren möchtest, gibt es eine Methode, die nur sizeof(Index) * N zusätzlichen Speicher benötigt, wobei N die Anzahl der tatsächlich benötigten Indizes ist und nicht der größte Index.

Die Methode gibt es aber nur bei Bedarf, falls sie dir nicht eh schon bekannt ist.

CStoll

Ein Vector speichert seine Elemente ohne Zwischenräume, da gibt es kein "nicht belegt" (du kannst höchstens ein "undefinierter Wert" festlegen - Möglichkeiten dazu wurden dir ja schon genannt). Wenn du nur einen kleinen Anteil der möglichen Indizes tatsächlich verwendest, ist wohl eine map<int,data> besser geeignet (besonders da du für die "leeren" Felder auch Speicherplatz benötigst).

Ponto

CStoll schrieb:

Ein Vector speichert seine Elemente ohne Zwischenräume, da gibt es kein "nicht belegt" (du kannst höchstens ein "undefinierter Wert" festlegen - Möglichkeiten dazu wurden dir ja schon genannt). Wenn du nur einen kleinen Anteil der möglichen Indizes tatsächlich verwendest, ist wohl eine map<int,data> besser geeignet (besonders da du für die "leeren" Felder auch Speicherplatz benötigst).

Mit einem std::vector geht das nicht. Da muss man schon operator new oder malloc benutzen. Ich habe auch den Overhead falsch angegeben. Er ist sizeof(Index) * (M + N) wobei M der maximale Index ist.

Wann macht man sowas:

Man benötigt bei dünn besetzten Indizes wirklich O(1) Zugriff und kann sich erlauben viel Speicher zu verwenden.
Man darf keine Laufzeit in die Initialisierung eines voll besetzten Arrays stecken. Auch die Initialisierung des Hilfsarrays von bool Werten ist nicht drin.