std::vector "Thou must always traverse with an iterator" - Ein STL Mythos?

[Gast++]

Es gab einige Beiträge in letzter Zeit in denen es um die Verwendung von std::vector<T> mit Funktionen diverser C-APIs ging, die einen T* als Argument verlangen.

Zur Eingrenzung
- Der vector verwende den Standardallokator (allocator<T>)
- Die betroffene Funktion erlaube es die Zahl der Elemente(size()) mit zu übergeben.
- Die C-Funktion grife nur lesend zu
- Alles passiere innerhalb eines Thread
- Es geht nur um std::vector; nicht um std::list, std::map o.ae.

(Ich weiss dass einige der Einschränkungen redundant sind)

Irgendwie hab den kategorischen Imperativ aus dem Titel im Hinterkopf, nämlich dass man gerade nicht sich einen T* auf vec[0] besogen soll und dann damit arbeitet, sondern immer einen std::vector<T>::iterator (welchen Iteratortyps auch immer) verwenden muss. Und zwar weil man sich auf die Repräsentation der Daten in dem Vector eben nicht verlassen kann; nämlich darauf nicht, dass die Ts ordentlich hintereinander liegen.

Wenn ich einige neuere Forenbeiträge aus dem Themenkreis lese meine ich mit dieser - womöglich falschen Einschätzung - nicht alleine zu sein.

Wenn ich aber Assemblercode anschaue sehe ich dass Compiler daraus einfache Pointerarithmetik macht.
Das ist zwar auch gut so und effizient; aber weniger effizient ist es wenn der Verwnder von std::vector das nicht weiss und in seinem Code mit teuren C-konfomren temporären Kopien des vector-Inhalts arbeitet.

Eigntlich würde ich bei solchen Fragen mir selbst immer raten in den Code zuschauen. Das habe ich getan aber ich versteh ihn nicht!
1001 typedef und #ifdefs und "#include per #include per #include <xyz>".

Was ich suche ist nicht die "Meinung" irgendeines Autors, sondern Info aus einer autoritativen Quelle, also Prof. Stroustrup himself oder oder aus der offiziellen STL Doku.

Am besten wäre natürlich eine Fundstelle mit Zitaten aus dem STL sourec, also eine Lesehilfe für Blöde wie mich.

=> Also Hat jemand autoritative Info zur Hand ob man

// mit
struct aType;
APIFunc(const aType*,size_t n);
std::vector<aType> vec;
//...
aType* p = &(vec[0]);
// einfach
APIFunc(p,vec.size());

aufrufen kann wenn APIFunc die Sequenz traversiert?
Und darüberhinaus - was gilt, wenn APIFunc auch die Elemente modifiziert (die Elemente, nicht die Länge der Sequenz)?

Was ich suche ist nicht die "Meinung" irgendeines Autors, sondern Info aus einer autoritativen Quelle, also Prof. Stroustrup himself oder oder aus der offiziellen STL Doku.

Grüsse

*this

[Helpie]

Die Funktion data() bzw. die Möglichkeit des Zugriffs mit Zeigern
sind im gültigen C++Standard noch nicht vorgesehen - erst im kommenden
Standard.

Auszug aus dem Standardentwurf vom April 2006:

23.2.5.3 vector data

pointer data();
const_pointer data() const;

Returns: A pointer such that [data(),data() + size()) is a valid range. For a
non-empty vector, data() == &front().

pointer ist wie folgt angegeben:
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;

D.h. es wird typischerweise T* sein, was aber letzlich vom Allocator abhängt.

[Phoemuex]

Gast++ schrieb:

Und zwar weil man sich auf die Repräsentation der Daten in dem Vector eben nicht verlassen kann; nämlich darauf nicht, dass die T's ordentlich hintereinander liegen.

Naja, im Standard steht zu den Requirements für eine "sequence":

A sequence is a kind of container that organizes a finite set of objects, all of the same type, into a strictly
linear arrangement. The library provides three basic kinds of sequence containers: vector, list, and
deque.

Und ich meine auch in einem C++-Buch gelesen zu haben, dass das tolle an vector ist, dass er komplett kompatibel zu C-Funktionen ist, die Pointer verwenden. Das Buch war allerdings nicht von Herrn Stroustup persönlich und das konkrete Zitat muss ich erstmal suchen

Felix

[Bashar]

Phoemuex schrieb:

Naja, im Standard steht zu den Requirements für eine "sequence":

A sequence is a kind of container that organizes a finite set of objects, all of the same type, into a strictly
linear arrangement. The library provides three basic kinds of sequence containers: vector, list, and
deque.

Du siehst aber auch selber, dass da noch list und deque mit aufgezählt werden, also kann deine Interpretation nicht stimmen.

@Gast++: Im Standard von 1998 war das wirklich versehentlich nicht geregelt, aber im TR1 von 2005 (?) ist die Definition von vector dahingehend präzisiert worden, dass die Elemente im Speicher direkt hintereinander liegen müssen.

[rüdiger]

Bashar schrieb:

@Gast++: Im Standard von 1998 war das wirklich versehentlich nicht geregelt, aber im TR1 von 2005 (?) ist die Definition von vector dahingehend präzisiert worden, dass die Elemente im Speicher direkt hintereinander liegen müssen.

War glaube ich in C++03.

[Phoemuex]

Bashar schrieb:

Phoemuex schrieb:

Naja, im Standard steht zu den Requirements für eine "sequence":

A sequence is a kind of container that organizes a finite set of objects, all of the same type, into a strictly
linear arrangement. The library provides three basic kinds of sequence containers: vector, list, and
deque.

Du siehst aber auch selber, dass da noch list und deque mit aufgezählt werden, also kann deine Interpretation nicht stimmen.

Stimmt, hab ich mich vertan

[camper]

Gast++ schrieb:

Und zwar weil man sich auf die Repräsentation der Daten in dem Vector eben nicht verlassen kann; nämlich darauf nicht, dass die T's ordentlich hintereinander liegen.

Entscheidend ist hier 23.2.4/1 Satz 4:

ISO/IEC 14882:2003 schrieb:

The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

[Gast++]

@Helpie:

Vielen Dank; das lässt zumindest eine Implikation zu.

@Phoemuex:

Phoemuex schrieb:

A sequence is a kind of container that organizes a finite set of objects, all of the same type, into a strictly linear arrangement. The library provides three basic kinds of sequence containers: vector, list, anddeque.

Gut dass Du drauf hinweist!
Das hatt eich vergessen zu erwähnen:
"strictly linear" ist mir da einfach nicht genug; abgesehen davon dass "linear" afaik nur bedeutet

f(L*n) == L * f(n) mit L elem R, also hier wohl L elem N+

spricht der ganze "Zirkus" um allocator::pointer, _Myptr ... und auch das Zitat von Helpie imo dagegen dass dies so gemeint ist.

Wegen des Zitates das Du suchen wolltest: Danke, aber das bringt nichts. Wenn ich ein Buch über die STL geschrieben hätte häte da sicherlich das Gegenteil dringestanden...

Grüsse

*this

[Thou shalt]

Thou shalt not commit adultery

[Gast++]

camper schrieb:

Gast++ schrieb:

Und zwar weil man sich auf die Repräsentation der Daten in dem Vector eben nicht verlassen kann; nämlich darauf nicht, dass die T's ordentlich hintereinander liegen.

Entscheidend ist hier 23.2.4/1 Satz 4:

ISO/IEC 14882:2003 schrieb:

The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

@Camper

Vielen Dank! Genau das hab ch gesucht!

@Bashar, rüdiger

Hab gerade mal
ISO/IEC 14882:2003 (S. 489/pdf S.517)

ISO/IEC 14882:1998 (S. 482/pdf S.508)

miteinander verglichen; die Fundstelle die Camper gab ist 2003 hinzugekommen!

Damit ist auch klar, warum ich (und vielleicht einige andere auch) von der These ausgingen, genau diese Art von Pointerarithmetik sei dubios; das war einfach überaltertes "Wissen".

Bleiben noch 2 offene Fragen:

- Helpie hatte ja dieses Proposal für den neuen Standard aufgezeigt; was soll dann data() eigentlich?

- Welche "Compiler"-pakete wurden auf den neuen Standard updated?
Zu den Compilern die vor 2003 released wurden, aber noch im Einsatz sind (MSVC 6!) müsste das ja ggf. in Servicepacks seitdem enthalten sein.

Bei MS recherchier ich das mal; kennt jemand gcc release interna?

Grüsse

*this

P.S.: @moderators: Wäre dies vielleicht was für die FAQ?

[Bashar]

Gast++ schrieb:

- Welche "Compiler"-pakete wurden auf den neuen Standard updated?
Zu den Compilern die vor 2003 released wurden, aber noch im Einsatz sind (MSVC 6!) müsste das ja ggf. in Servicepacks seitdem enthalten sein.

Was das Hintereinanderliegen der Elemente im Speicher angeht, muss da nichts geupdatet werden. Diese Sache wurde ja genau deshalb vergessen, weil alle beteiligten stillschweigend davon ausgegangen sind, dass es eh so implementiert wird.

[-------]

Gast++ bitte entferne die Links auf die Standards. Das ist illegal.

[Helpie]

Bleiben noch 2 offene Fragen:

- Helpie hatte ja dieses Proposal für den neuen Standard aufgezeigt; was soll dann data() eigentlich?

- Welche "Compiler"-pakete wurden auf den neuen Standard updated?
Zu den Compilern die vor 2003 released wurden, aber noch im Einsatz sind (MSVC 6!) müsste das ja ggf. in Servicepacks seitdem enthalten sein.

Bei MS recherchier ich das mal; kennt jemand gcc release interna?

data() soll ähnlich wie c_str() den Zugriff auf die internen Daten erlauben.
GCC 4.2 hat es bereits implementiert. Damit ist der Zugriff über Zeiger möglich.
Z.B.

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

#define PRINT(X) cout << (#X) << " = " << (X) << endl
int main() {
     vector<int> v;
     v.push_back(1);
     v.push_back(2);
     v.push_back(3);
     v.push_back(99);
     int* p = v.data();          // data()
     while(p != v.data() +v.size()) {
        PRINT(p);
        PRINT(*p);
        ++p;
     }        
}