3. Vector "aufrücken" lassen

Vector "aufrücken" lassen

  • U

    Fatal Error appears schrieb:

    Ok danke. Werden wenn ich einen Vector mit vec[10] habe und dan mit erase vec[5] lösche ist dann vec[10] einfach leer oder gibt es dass dann nicht mehr?

    gibt es nicht mehr

    0
  • ?

    Sebastian Pizer schrieb:

    Es kann aber sein, dass die inneren Vektoren, die aufrücken sollen, unnötig kopiert werden. Das hängt von der Implementierung deiner Standardbibliothek ab. [...] Unter Linux hab ich es noch nicht ausprobiert .... Ich mach' das einfach mal jetzt .... 😃

    Die GNU stdlibc++ scheint diese Optimierung auch eingebaut zu haben. Statt die inneren Vektoren umzukopieren, werden einfach ein paar Zeiger umgebogen. Getestet habe ich's mit einem vector<vector<foo> > wobei ich Kopieroperationen von foo mitgezählt habe.

    Gruß,
    SP

    0
  • U

    Sebastian Pizer schrieb:

    Sebastian Pizer schrieb:

    Es kann aber sein, dass die inneren Vektoren, die aufrücken sollen, unnötig kopiert werden. Das hängt von der Implementierung deiner Standardbibliothek ab. [...] Unter Linux hab ich es noch nicht ausprobiert .... Ich mach' das einfach mal jetzt .... 😃

    Die GNU stdlibc++ scheint diese Optimierung auch eingebaut zu haben. Statt die inneren Vektoren umzukopieren, werden einfach ein paar Zeiger umgebogen. Getestet habe ich's mit einem vector<vector<foo> > wobei ich Kopieroperationen von foo mitgezählt habe.

    Gruß,
    SP

    hätte mich auch sehr gewundert, wenn nicht...
    Weil das swap für vectoren entsprechend überladen ist (swapt den pointer und die länge) und im vector an sich ja mit swap gearbeitet wird...

    bb

    0
  • ?

    unskilled schrieb:

    Sebastian Pizer schrieb:

    Die GNU stdlibc++ scheint diese Optimierung auch eingebaut zu haben. Statt die inneren Vektoren umzukopieren, werden einfach ein paar Zeiger umgebogen.

    hätte mich auch sehr gewundert, wenn nicht...
    Weil das swap für vectoren entsprechend überladen ist (swapt den pointer und die länge) und im vector an sich ja mit swap gearbeitet wird...

    Es steht nirgends geschrieben, dass innerhalb von vector<>::erase die Elemente per swap-Funktion vertauscht werden sollen. Für benutzerdefinierte Type (ausgenommen Typen der Standardbibliothek) muss vector<>::erase das Aufrücken der letzten Elemente per Zuweisungsoperator durchführen. Andernfalls wäre die Implementierung nicht standardkonform.

    Es gibt natürlich Element-Typen, die von einer erase -Version profitieren, die stattdessen eine optimierte swap -Funktion für die Elemente aufruft (std::vector<>, std::list<>, ...). Da die STL Kontainer Teil der Standardbibliothek sind und der Nutzer nicht mitbekommen kann, ob wirklich operator= zum Aufrücken benutzt wurde (abgesehen von Performanzunterschieden), ist eine Implementierung von vector<>::erase , die swap für STL Kontainer benutzt nach der "as-if" Regel standardkonform.

    Wenn man jetzt also als Standardbibliotheksentwickler jeweils die beste Variante benutzen will und standardkonform bleiben will, muss man etwas über den Element-Typen T wissen. Ist es eine Klasse der Standardbibliothek? Gehört zu T eine optimierte swap -Funktion? Dafür würde man dann eine Traits Klassen einsetzten:

    /// Gehoert zum Typen T eine EFFIZIENTE swap Funktion?
template<typename T> struct is_swaptimizable : false_type {};
template<typename T> struct is_swaptimizable<std::vector<T> > : true_type {};
template<typename T> struct is_swaptimizable<std::list<T> > : true_type {};
....

    In vector<>::erase könnte dann anhand von is_swaptimizable<T> der "beste" erase -Algorithmus ausgewählt werden.

    Soweit ich weiß, bietet Microsoft einen solchen (aber nicht offiziell dokumentierten) "extension point" an, damit benutzerdefinierte Klassen von einer ähnlichen Optimierung profitieren können. Das trifft ja nicht nur auf erase zu, sondern zB auch auf insert oder die Vergrößerung des Vektors, bei dem normalerweise Elemente umkopiert werden müssen.

    Die GNU libstdc++ Implementierung macht offensichtlich etwas ähnliches -- ich habe die Implementierung von vector<>::erase aber vorhin nicht auf Anhieb gefunden.

    Gruß,
    SP

    0
  • U

    das es nicht im standard steht, ist auch nicht notwendig, weil die alternativen nicht all zu gut sind ^^

    beim msvc hab ich so etwas bisher noch nie gesehen... dacht auch immer, dass swap genutzt wird, weil bei pods der nachteil ggnüber dem op= minimal ist (vll komplett wegoptmiert wird) und bei größeren typen der vorteil nat. rel hoch ist - weil man ein std::swap ja auch immer spezialisiert...

    aber hier mal nen bsp.:
    vector:

    iterator erase(const_iterator _Where_arg)
	{	// erase element at _Where
	iterator _Where = _Make_iter(_Where_arg);
	size_type _Off = _Where - begin();

#if _HAS_ITERATOR_DEBUGGING
	if (end() <= _Where)
		_DEBUG_ERROR("vector<bool> erase iterator outside range");
	std::copy(_Where + 1, end(), _Where);
	_Orphan_range(_Off, _Mysize);

#else /* _HAS_ITERATOR_DEBUGGING */
	std::copy(_Where + 1, end(), _Where);
#endif /* _HAS_ITERATOR_DEBUGGING */

	_Trim(_Mysize - 1);
	return (begin() + _Off);
	}

    also ein wenig entfrickelt:

    iterator erase(const_iterator _Where_arg)
{	// erase element at _Where
	iterator _Where = _Make_iter(_Where_arg);
	size_type _Off = _Where - begin();

	std::copy(_Where + 1, end(), _Where);

	_Trim(_Mysize - 1);
	return (begin() + _Off);
}

    copy verweist auf paar andere copys, aber schlussendlich wird darauf verwiesen:

    template<class _InIt, class _OutIt, class _InOutItCat>
inline
	_OutIt __CLRCALL_OR_CDECL _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
		_InOutItCat, _Scalar_ptr_iterator_tag, _Range_checked_iterator_tag)
	{	// copy [_First, _Last) to [_Dest, ...), pointers to scalars

 #if _HAS_ITERATOR_DEBUGGING
	_DEBUG_RANGE(_First, _Last);
	if (_First != _Last)
		_DEBUG_POINTER(_Dest);
 #endif /* _HAS_ITERATOR_DEBUGGING */

	ptrdiff_t _Off = _Last - _First;	// NB: non-overlapping move
	// if _OutIt is range checked, this will make sure there is enough space for the memmove
	_OutIt _Result = _Dest + _Off;
	if (_Off > 0)
		_CRT_SECURE_MEMMOVE(&*_Dest, _Off * sizeof (*_First), &*_First, _Off * sizeof (*_First));
	return _Result;
	}

    -> entfrickelt:

    template<class _InIt, class _OutIt, class _InOutItCat>
inline _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest, _InOutItCat, _Scalar_ptr_iterator_tag, _Range_checked_iterator_tag)
{
	ptrdiff_t _Off = _Last - _First;
	// if _OutIt is range checked, this will make sure there is enough space for the memmove
	_OutIt _Result = _Dest + _Off;
	if (_Off > 0)
		_CRT_SECURE_MEMMOVE(&*_Dest, _Off * sizeof (*_First), &*_First, _Off * sizeof (*_First));
	return _Result;
}

    wie _CRT_SECURE_MEMMOVE intern arbeitet bekommt man imho nicht raus
    kann dir nur sagen, dass es das hier aufruft:

    _Check_return_wat_ _CRTIMP errno_t __cdecl memmove_s(_Out_opt_bytecap_post_bytecount_(_DstSize,_MaxCount) void * _Dst, _In_ rsize_t _DstSize, _In_opt_bytecount_(_MaxCount) const void * _Src, _In_ rsize_t _MaxCount);

    aber die implementation ist eben in der CRT ^^

    bb

    PS: Ich würde jedenfalls ne Implementierung, die immer einfach nur swap aufruft vollkommen in Ordnung finden - wenn ich nen Objekt nehm, für das kein swap existiert, bin ich selbst schuld - und abgesehen davon, denke ich, dass der compiler da ne ganze menge optimieren kann (also aus dem "normalen" swap eh nen op= wird - aber ich muss jz erst mal weg, bevor ich das testen kann - doofes rl ^^)

    0
  • F

    Boah wieder einiges dazugelernt...:) Hab aber dennoch noch eine Frage:
    Ist es auch möglich etwas in einen Vector nachträglich einzuschieben?
    also: neues Multi_vec[5]: alte multi_vec[5] wird zu multi_vec[6]?

    0
  • P

    schau mal in der Doku deiner Wahl nach vector<>::insert()

    0
  • F

    Perfekt. Danke.

    0
  • F

    Mmhm ich krieg es einfach nicht hin. Ich versteh nicht was in den 2. Pareameter bei vector.insert(vector.begin,?????); kommt.
    Ich habe einen mehrdimensionalen Vector:
    std::vector <std::vector std::wstring > multi_vec;//[20][5]
    und will bei multi_vec[0] 5 neue Werte einfügen wobei der alte [0] nach 1 rutschen soll usw.

    0
  • ?

    read the f***ing manual

    0
  • X

    blupp schrieb:

    read the f***ing manual

    englisch

    0
  • P

    xBlackKnightx schrieb:

    englisch

    Da kommt man auf Dauer nicht drumherum.

    0
  • J

    Überleg Dir doch einfach mal, was multi_vec[0] für ein Objekt ist. Dann kommst Du zwangsläufig auf sowas hier:

    http://codepad.org/7do9rNHW

    /e: für multi_vec[0] sollte man natürlich eine Referenz anlegen, damit wird die ganze Sache dann ein wenig übersichtlicher...

    0

  • pumuckl schrieb:

    xBlackKnightx schrieb:

    englisch

    Da kommt man auf Dauer nicht drumherum.

    Jopp. Aber sie wehren sich behaarlich. *g*
    Und natürlich kann man ja auch immer im Forum fragen, und andere Leute quälen, anstatt mal ne halbe Seite englische Doku zu lesen.

    0
Anmelden zum Antworten