Was von der STL nehm ich hierfür...

[Helium]

Ich brauche einfach nur ein sozusagenes Array von einem meiner Objekte.

"sozusagenes", toller Neologismus, dessen Sinn sich mir aber nicht erschließt.

Die Reihenfolge ist dabei trivial und ich greife auch wenn überhaupt nur via ID zu, also wäre [] ganz gut.

trivial? Meintest du vielleicht egal? Order erklärt sich die Reihenfolge hier von selbst, ist die Reheinvolge von jedem sofort erschließbar, selbstverständlich?

Warum sollen die Elemente linear (für HumeSikkins: er mein vektoriel, nehme ich an) angeordnet sein? Welchen Vorteil bzw. Nutzen ziehst du daraus?

Wennst ständig wächst und/oder schrumft nimm deque, ansonsten vector. Ansosnten könnten möglicherweise Hashs das sein, was du suchst. Guck dir daru mal die SGi implementation der STL an.

[Ingo aka Desert Hawk]

Original erstellt von <dua>:
lineare zugriffzeit kannste eigentlich nur sinnvoll mit ner verketteten liste garantieren. nimm auf keinen fall std::map mitO(log(n)) oder gar std::vector mit O(1). sie sind zu weit vom linearen zugriff entfernt.

Hmm.. mal ganz blöde gefragt, warum sollte jemand eine Datenstruktur nutzen, die O(n) ist, wenn es auch mit O(1) geht?

[Helium]

weil einfügen in ne Liste o(1) hat und in nem Vektor o(n). Man muss also Prioritäten setzen: Schneller zugriff oder schnelles einfügen.

[Daniel E.]

Original erstellt von Ingo aka Desert Hawk:
Hmm.. mal ganz blöde gefragt, warum sollte jemand eine Datenstruktur nutzen, die O(n) ist, wenn es auch mit O(1) geht?

Es sagt nichts über die Laufzeiten/ Speicherverbrauch/ whatever aus.
O(1) heißt, Laufzeit ist konstant.
O(n) heißt, Laufzeit ist direkt proportional zu der Anzahl der Elemente.

Man könnte nun einfach immer(!) von einem größtmöglichen n ausgehen. Damit hat der Algorithmus ein konstentes Laufzeitverhalten, O(1), und ist trotzdem langsamer/ speicherfressender/ whatever als der O(n)-Algorithmus. Die O-Notation ist in der Praxis eher nicht so wirklich ernstzunehmen, wegen der unberücksichtigten Fixkosten.

[cLE]

Hi!

zurück zur eigentlichen Frage:
Wenn du auf deine Daten per ID zugreifen willst, kommt ja eigentlich nur noch ne map in Frage, außer wenn du mit ID nen Array Index meinst.
Im letzteren Fall kannst du vector vergessen, da du ja Elemente aus der Mitte löschen möchtest, was unter Umständen ewig dauern kann. Für diesen Fall ist eine Liste sehr gut geeignet. Testweise kannst du aber auch deque ausprobieren, das deutlich schneller sein kann. Von der queue kann ich dir für deinen Anwendungsfall nur abraten, da diese dafür gedacht ist nach dem FIFO Prinzip zu arbeiten und kein Container im eignetlichen Sinn ist.
Am Besten erzeugst du dir in deinem Programm ein typedef, womit du die Instanzen deiner list / deque / sonstwas erzeugst. Dann kannst du nacheinander mehrere Testläufe mit den verschiedenen Container machen.

mfg cLE

[HumeSikkins]

Von der queue kann ich dir für deinen Anwendungsfall nur abraten, da diese dafür gedacht ist nach dem FIFO Prinzip zu arbeiten und kein Container im eignetlichen Sinn ist.

Ach nein? Und seit wann ist deque kein Container im eigentlichen Sinne? Und wie definierst du "im eigentlichen Sinne". Im Sinne des C++ Standards ist std::deque nämlich ein Container.

[cLE]

Original erstellt von HumeSikkins:
[quote] Von der queue kann ich dir für deinen Anwendungsfall nur abraten, da diese dafür gedacht ist nach dem FIFO Prinzip zu arbeiten und kein Container im eignetlichen Sinn ist.

**
Ach nein? Und seit wann ist deque kein Container im eigentlichen Sinne? Und wie definierst du "im eigentlichen Sinne". Im Sinne des C++ Standards ist std::deque nämlich ein Container.**[/QUOTE]
1. bezieht sich meine Aussage auf queue und nicht auf deque
2. ist queue ein Adaptor (genau wie stack), womit man einen Container wie deque kapseln kann um eine FIFO Warteschlange zu erzeugen
3. "im eigentlichen Sinne" - hier ganz genau:

template<class T, class A = allocator<T> >
    class Cont {
public:
    typedef A allocator_type;
    typedef T0 size_type;
    typedef T1 difference_type;
    typedef T2 reference;
    typedef T3 const_reference;
    typedef T4 value_type;
    typedef T5 iterator;
    typedef T6 const_iterator;
    typedef T7 reverse_iterator;
    typedef T8 const_reverse_iterator;
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;
    size_type size() const;
    size_type max_size() const;
    bool empty() const;
    A get_allocator() const;
    iterator erase(iterator it);
    iterator erase(iterator first, iterator last);
    void clear();
    void swap(Cont x);
protected:
    A allocator;
    };

Dieses Interface muss von einem Container mindestens bereitgestellt werden. Zum Vergleich queue:

template<class T,
    class Cont = deque<T> >
    class queue {
public:
    typedef Cont::allocator_type allocator_type;
    typedef Cont::value_type value_type;
    typedef Cont::size_type size_type;
    explicit queue(const allocator_type& al = allocator_type()) const;
    bool empty() const;
    size_type size() const;
    allocator_type get_allocator() const;
    value_type& top();
    const value_type& top() const;
    void push(const value_type& x);
    void pop();
protected:
    Cont c;
    };

Das was sofort auffallen sollte, ist dass queue überhaupt keine Iteratoren zur Verfügung stellt, seltsam oder???

mfg cLE

[HumeSikkins]

@<cLE>
Sorry. Ich habe mich schlicht und einfach verlesen.
Für queue ist deine Aussage natürlich korrekt.

/me geht schuldbewusst in den Keller lesen üben.

[Ingo aka Desert Hawk]

Original erstellt von Daniel E.:
**Es sagt nichts über die Laufzeiten/ Speicherverbrauch/ whatever aus.
O(1) heißt, Laufzeit ist konstant.
O(n) heißt, Laufzeit ist direkt proportional zu der Anzahl der Elemente.

Man könnte nun einfach immer(!) von einem größtmöglichen n ausgehen. Damit hat der Algorithmus ein konstentes Laufzeitverhalten, O(1), und ist trotzdem langsamer/ speicherfressender/ whatever als der O(n)-Algorithmus. Die O-Notation ist in der Praxis eher nicht so wirklich ernstzunehmen, wegen der unberücksichtigten Fixkosten.**

Naja indirekt sagt es schon was über die Laufzeiten aus...
1. Container - Laufzeit zum Einfügen O(n)
2. Container - Laufzeit zum Einfügen O(1)

mess mal die Laufzeit des 1. Containers, in dem gegen unendlich viele Elemente eingefügt werden.
Und das gleiche machst du nochmal für den 2. Container.

Wenn der O(1)Container länger braucht, dann würd ich sagen, muss das von seinem Programmierer gewollt sein.

Ich mein sicher kann ich auch einen Container bauen, der O(1) Laufzeiten hat aber wesentlich länger braucht, als ein Container mit O(n).
Aber wer macht sowas?

[Mis2com]

Ups...

Also nochmal klar formuliert (hoffe ich ;)):

Ich möchte es so handhaben, dass ich später einen zeiger, den ich von dem z.B. Vector bekomme, einfach an eine Funktion übergeben kann.
Das hat den Zweck, dass die Funktion einfach schnell alles durchliest und dabei einfach über [] zugreifen kann, wenn ich also vorher im Vector hatte:

100
200
300
400
500

und dass dann mit dem zeiger übergebe, soll die funktion so arbeiten können:

array[0]
array[1]
array[2]
array[3]
array[4]

Die Reihenfolge ist egal, das heißt es ist gleich, ob ein Objekt ganz vorne oder hinten liegt, dieObjekte können auch mehrere EIgenschaften gleich haben.

Da es keinen primärschlüssel gibt, nutzt mir eine Map nicht sonderlich viel, weil ich da auch selber suchen müsst, also ohne die .find Methode, die ja nur mit dem Primärschlüssel arbeitet, den ich sowieso nicht habe.

@dua:
Damit habe ich C++ nicht abgeschlossen, was redest du fürn Mist?
Durch das Buch habe ich mir die theoretischen Grundlagen verschafft, sodass ich diese nun praktiosch ausleben kann und erweitern!
Man lernt nie aus

MfG MAV