Constant Time std::vector Item Removal
in [C++]
|
Prev: Distinguish between pointers created with 'new' and created with references.
Next: Distinguish between pointers created with 'new' and created with references.
From: Falk Tannhäuser on 1 Aug 2010 14:51 Am 01.08.2010 16:30, schrieb Mathias Gaunard: > On Jul 31, 3:25 am, Jeffrey Schwab<j...(a)schwabcenter.com> wrote: >> On 7/20/10 10:00 AM, Seungbeom Kim wrote: >> >>> vec[pos] = std::move(vec.back()); >> >> What's in vec.back() after that statement? (I'm still coming to terms >> with move semantics.) > > It's not clearly stated by the standard what operations must be valid > on a moved-from object. > It seems that destruction and all forms of copy construction and > assignment must remain valid, which means move semantics are not > really overhead-free, since all these primitives will need to check > for the moved-from state. I don't think there will be a special "moved-from" state in real-world implementations. I would rather expect one of the following: (1) the moved-from object retains its old value, (2) the moved-from object obtains the old value of the moved-to object (i.e. move is implemented as swap), or (3) the moved-from object becomes empty (i.e. as if it was default-constructed). Depending on implementation details of the type in question, what actually happens may depend on the current object value. For example, in case of std::string with short-string optimization in effect, I wouldn't be too surprised to see (1) for short strings, (2) for long strings in case of move assignment and (3) for long strings in case of move construction. Of course, as long as you only do things you are supposed to with the moved-from object (as destruct or re-assign it), all this doesn't really matter. Falk -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Mathias Gaunard on 2 Aug 2010 03:36 On Aug 2, 1:10 am, "Bo Persson" <b...(a)gmb.dk> wrote: > No, they will not have to check for any other states than they already > have. My point is that you will need to introduce an extra "empty" state in order to make use of move semantics, and that state may require additional branches in each of the object primitives. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: nmm1 on 2 Aug 2010 03:49 In article <4c55b7de$0$22015$426a74cc(a)news.free.fr>, =?ISO-8859-1?Q?Falk_Tannh=E4user?= <clcppm-poster(a)this.is.invalid> wrote: > >I don't think there will be a special "moved-from" state in real-world >implementations. I would rather expect one of the following: >(1) the moved-from object retains its old value, >(2) the moved-from object obtains the old value of the moved-to object (i.e. move is implemented as swap), or >(3) the moved-from object becomes empty (i.e. as if it was default- >constructed) Such objects certainly exist, and are unavoidable for a few requirements. Any that contain context- or location-dependent data are likely to have such properties - e.g. the context gets nullified on a move. My understanding of C++ is that it implicitly assumes that objects do NOT have such properties, but that is based primarily on reading the actual wording and not being able to make it self-consistent if they do. However, I can see no explicit wording one way or the other. Regards, Nick Maclaren. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Seungbeom Kim on 2 Aug 2010 21:48 On 2010-08-01 22:51, Falk Tannh�user wrote: > > I don't think there will be a special "moved-from" state in real-world implementations. I would rather expect one of the following: > (1) the moved-from object retains its old value, > (2) the moved-from object obtains the old value of the moved-to object (i.e. move is implemented as swap), or > (3) the moved-from object becomes empty (i.e. as if it was default-constructed). > > Depending on implementation details of the type in question, what actually happens may depend on the current object value. For > example, in case of std::string with short-string optimization in effect, I wouldn't be too surprised to see (1) for short > strings, (2) for long strings in case of move assignment and (3) for long strings in case of move construction. > Of course, as long as you only do things you are supposed to with the moved-from object (as destruct or re-assign it), all this > doesn't really matter. I'm not sure if it doesn't violate anything when (2) is used, i.e. when y = std::move(x); doesn't (immediately) release any resource that y previously held. I don't really know, though it looks somewhat suspicious. (Of course, in the original context where it is used with std::remove(), it won't make much difference eventually.) -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Felipe Magno de Almeida on 2 Aug 2010 22:18
On Aug 2, 3:36 pm, Mathias Gaunard <loufo...(a)gmail.com> wrote: > On Aug 2, 1:10 am, "Bo Persson" <b...(a)gmb.dk> wrote: > >> No, they will not have to check for any other states than they already >> have. > > My point is that you will need to introduce an extra "empty" state in > order to make use of move semantics, and that state may require > additional branches in each of the object primitives. IIUC, You don't if you implement move as swap. > -- Regards, -- Felipe Magno de Almeida -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |