C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Constructing objects in place in a container Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Sylvain Pion Guest Posted: Fri Oct 17, 2003 3:25 pm    Post subject: Constructing objects in place in a container When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? Has there been any thoughts/discussions on this topic ? I could propose 2 solutions (provided it's agreed it's a problem) : - change the requirements on insert(T) so that it only requires that T is convertible to value_type (and then internally, the new placement operator can be used to construct in place), and insert() would become a template member function (similarly for push_back()...). - or add a bunch of member functions like : template < typename A1, typename A2 > iterator construct_insert(const A1& a1, const A2& a2); this one constructing the element from (a1, a2), and similar functions would be added for N arguments, 0<=N<=10 for example, and passed to the constructor of the object. -- Sylvain [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top WW Guest Posted: Sat Oct 18, 2003 10:46 am    Post subject: Re: Constructing objects in place in a container Sylvain Pion wrote: Quote: When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? Has there been any thoughts/discussions on this topic ? I could propose 2 solutions (provided it's agreed it's a problem) : - change the requirements on insert(T) so that it only requires that T is convertible to value_type (and then internally, the new placement operator can be used to construct in place), and insert() would become a template member function (similarly for push_back()...). I did this same thing in comp.std.c++, IIRC more than a year ago. I have been flamed to death telling that this is a non-issue, noone has any trouble with it etc. So be warned. ;-) IMO it is a good idea, especially for classes which are involved in an Adapter, so their whole game is to convert. Instead of one conversion they will do a conversion and a copy. :-( -- WW aka Attila [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ivan Vecerina Guest Posted: Sat Oct 18, 2003 9:44 pm    Post subject: Re: Constructing objects in place in a container "Sylvain Pion" <spion (AT) sophia (DOT) inria.fr> wrote Quote: When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? Right. Except maybe when all functions involved can be inlined, and the operation can be optimized as a whole... Quote: Has there been any thoughts/discussions on this topic ? Quite a few. First of all, one easy solution that can be used today is the push-empty and swap trick. For example: void fast_destructive_push_back(vector<string>& c, string& s) { c.push_back( string() ); c.back().swap(s); } By first inserting an empty object (wihout any mem allocation) and then swapping it, this avoids unnecessary copies. Next, you could read about Andrei's moving constructors: http://www.moderncppdesign.com/publications/cuj-02-2003.html There is also a proposal to add "takeover references" to the standard, to support "moving constructors". Searching for these keywords (plus authors Howard Hinnant and Andrei Alexandrescu) should provide a bunch of starting points here. Granted, these proposals are about optimizing object moving, not specifically allowing construction within containers. Quote: I could propose 2 solutions (provided it's agreed it's a problem) : - change the requirements on insert(T) so that it only requires that T is convertible to value_type (and then internally, the new placement operator can be used to construct in place), and insert() would become a template member function (similarly for push_back()...). - or add a bunch of member functions like : template < typename A1, typename A2 iterator construct_insert(const A1& a1, const A2& a2); this one constructing the element from (a1, a2), and similar functions would be added for N arguments, 0<=N<=10 for example, and passed to the constructor of the object. I would have yet another solution: use placement-new syntax: new (myVector) std::string("this data"); Additional placement-parameters may allow insertion at a specific location. An std::vector implementation could implement this functionality today, and take advantage of the built-in support that C++ has for exception-safe allocation (by implementing the corresponding placement-delete). And any number of construction parameters are supported using this approach. Regards, Ivan -- http://ivan.vecerina.com http://www.brainbench.com <> Brainbench MVP for C++ [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Sat Oct 18, 2003 10:51 pm    Post subject: Re: Constructing objects in place in a container "WW" <wolof (AT) freemail (DOT) hu> writes: Quote: Sylvain Pion wrote: When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? Has there been any thoughts/discussions on this topic ? I could propose 2 solutions (provided it's agreed it's a problem) : - change the requirements on insert(T) so that it only requires that T is convertible to value_type (and then internally, the new placement operator can be used to construct in place), and insert() would become a template member function (similarly for push_back()...). I did this same thing in comp.std.c++, IIRC more than a year ago. I have been flamed to death telling that this is a non-issue, noone has any trouble with it etc. So be warned. ;-) IMO it is a good idea, especially for classes which are involved in an Adapter, so their whole game is to convert. Instead of one conversion they will do a conversion and a copy. Yeah, I like it. The problem is that I'm not sure there's a way to make a conversion operator do in-place construction without compiler magic. It would be a shame if only the standard containers could take advantage of this idiom. -- Dave Abrahams Boost Consulting www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michiel Salters Guest Posted: Sat Oct 18, 2003 11:17 pm    Post subject: Re: Constructing objects in place in a container [email]spion (AT) sophia (DOT) inria.fr[/email] (Sylvain Pion) wrote in news:bmoqhp$m25$1@news- sop.inria.fr: Quote: When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? It is allowed when you can't detect the optimalization (as always). However, the copy constructor must be called when it has noticable side effects, like output. Quote: Has there been any thoughts/discussions on this topic ? Extensive. There is even a proposal to remedy it, by replacing the copy with a move. Quote: I could propose 2 solutions (provided it's agreed it's a problem) : - change the requirements on insert(T) so that it only requires that T is convertible to value_type (and then internally, the new placement operator can be used to construct in place), and insert() would become a template member function (similarly for push_back()...). That fixes only the case where value_type's ctor takes a single argument. It can't cover two-argument versions, as that would interfere with the range-version of insert() Quote: - or add a bunch of member functions like : template < typename A1, typename A2 iterator construct_insert(const A1& a1, const A2& a2); this one constructing the element from (a1, a2), and similar functions would be added for N arguments, 0<=N<=10 for example, and passed to the constructor of the object. That would obviously work, but it runs into the forwarding problem. In general it isn't possible to create a forwarding function that passes on all its arguments to another function. Again, the move proposal should help. However, the move proposal not only makes your function possible but also makes it unneccesary. Regards, -- Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Siemel Naran Guest Posted: Sun Oct 19, 2003 8:02 am    Post subject: Re: Constructing objects in place in a container "Sylvain Pion" <spion (AT) sophia (DOT) inria.fr> wrote Quote: When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? Has there been any thoughts/discussions on this topic ? Can you use a container of smart pointers, eg. std::vector<boost::shared_pounter. You do end up calling the smart pointer's copy constructor, but it does little (just dereferences a pointer and increments an integer) so is likely to be fast. -- +++++++++++ Siemel Naran [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Gabriel Dos Reis Guest Posted: Sun Oct 19, 2003 8:49 am    Post subject: Re: Constructing objects in place in a container Michiel Salters <Michiel.Salters (AT) cmg (DOT) nl> writes: Quote: spion (AT) sophia (DOT) inria.fr (Sylvain Pion) wrote in news:bmoqhp$m25$1@news- sop.inria.fr: When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? It is allowed when you can't detect the optimalization (as always). However, the copy constructor must be called when it has noticable side effects, like output. Where do you find such requirement? My reading of 12.8/15 is different. -- Gaby [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top WW Guest Posted: Sun Oct 19, 2003 4:05 pm    Post subject: Re: Constructing objects in place in a container David Abrahams wrote: Quote: I did this same thing in comp.std.c++, IIRC more than a year ago. I have been flamed to death telling that this is a non-issue, noone has any trouble with it etc. So be warned. ;-) IMO it is a good idea, especially for classes which are involved in an Adapter, so their whole game is to convert. Instead of one conversion they will do a conversion and a copy. :-( Yeah, I like it. The problem is that I'm not sure there's a way to make a conversion operator do in-place construction without compiler magic. It would be a shame if only the standard containers could take advantage of this idiom. The way we looked at it (ehem, tried) many months ago was member templates. It means that the all those kind of things (push_back etc.) would pass the type through, up to the constructor. Of course this is not necessarily /the/ solution, it was just one way to think about. I just do not get your problem. Why would it need compiler magic? We can construct a type from another one (in-place) without any magic involved. That is why we make some constructor explicit, so that we will not make it by mistake. :-) -- WW aka Attila [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dhruv Guest Posted: Sun Oct 19, 2003 6:43 pm    Post subject: Re: Constructing objects in place in a container On Fri, 17 Oct 2003 11:25:12 -0400, Sylvain Pion wrote: Quote: When an object is inserted in a container, it has to be copied. I would like to optimize away this copy, and construct the object directly in the container. It's my understanding that the C++ standard does not allow the compiler to optimize away this particular copy, right ? Has there been any thoughts/discussions on this topic ? I could propose 2 solutions (provided it's agreed it's a problem) : - change the requirements on insert(T) so that it only requires that T is convertible to value_type (and then internally, the new placement operator can be used to construct in place), and insert() would become a template member function (similarly for push_back()...). Consider the following example. According to your proposal, constructs like this will become valid, while they should be invalid, as they are now: #include <iostream> #include <vector> using std::cout; using std::endl; //Assume this is vector's insert member function. template <class Type, class Param_Type> void insert (Type *tptr, const Param_Type& param) { new (tptr) Type (param); } struct foo { int data; foo () { cout<<"In foo's default ctor."< explicit foo (int x): data(x) { cout<<"In foo's int ctor, x == "< foo (const foo&) { cout<<"In foo's copy ctor"< ~foo () { cout<<"In foo's dtor"< }; int main () { foo *pfoo = (foo*)operator new (sizeof(foo)); insert (pfoo, 2); //Ctor is explicit, still, this compiles. } Quote: - or add a bunch of member functions like : template < typename A1, typename A2 iterator construct_insert(const A1& a1, const A2& a2); this one constructing the element from (a1, a2), and similar functions would be added for N arguments, 0<=N<=10 for example, and passed to the constructor of the object. This is insane!!!, but the idea is a good one. I liked the suggestion given by Ivan Vecerina about the placement new-syntax. It seems pretty practical, and fairly well implementable even given the current scenario. Regards, -Dhruv. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Le Chaud Lapin Guest Posted: Fri Oct 24, 2003 3:23 pm    Post subject: Re: Constructing objects in place in a container [email]spion (AT) sophia (DOT) inria.fr[/email] (Sylvain Pion) wrote in message news:<bmoqhp$m25$1 (AT) news-sop (DOT) inria.fr>... Quote: When an object is inserted in a container, it has to be copied. [snippage] Really? My containers only construct during augmentation: #include <List.hpp> struct Foo {} ; int main () { List<Foo> list; Foo f; list.insert (f); // no copy of f, just construction from f. return 0; } Is this what you mean? Isn't this how STL works? It's hard to believe that STL would do a copy just to insert, so maybe I misunderstand. -Chaud Lapin- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Christoph Schulz Guest Posted: Sat Oct 25, 2003 8:25 am    Post subject: Re: Constructing objects in place in a container Hello! Le Chaud Lapin <unoriginal_username (AT) yahoo (DOT) com> wrote: Quote: spion (AT) sophia (DOT) inria.fr (Sylvain Pion) wrote in message news:<bmoqhp$m25$1 (AT) news-sop (DOT) inria.fr>... When an object is inserted in a container, it has to be copied. [snippage] Really? [code example snipped] It's hard to believe that STL would do a copy just to insert, so maybe I misunderstand. The OP meant (emphasise mine): When an object is inserted in a container, *the object* has to be copied. He did not want to say that the container is copied (as you understood, I suppose). Regards, Christoph [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Le Chaud Lapin Guest Posted: Tue Oct 28, 2003 6:42 pm    Post subject: Re: Constructing objects in place in a container "Christoph Schulz" <kristov (AT) arcor (DOT) de> wrote Quote: Hello! Le Chaud Lapin <unoriginal_username (AT) yahoo (DOT) com> wrote: [email]spion (AT) sophia (DOT) inria.fr[/email] (Sylvain Pion) wrote in message news:<bmoqhp$m25$1 (AT) news-sop (DOT) inria.fr>... When an object is inserted in a container, it has to be copied. [snippage] Really? [code example snipped] It's hard to believe that STL would do a copy just to insert, so maybe I misunderstand. The OP meant (emphasise mine): When an object is inserted in a container, *the object* has to be copied. He did not want to say that the container is copied (as you understood, I suppose). I still do not understand the problem (never seen STL code), but just in case, here is a portion of my List<> template. As you can see, objects in the list are contructed via new taking the augmenting element as an argument. First the part that defines the Node of the List<>:.... template <typename Element> class List { protected : unsigned int capacity_; unsigned int population_; struct Node { Element element; Node *up_link, *down_link; Node (const Element &element) : element(element) {} } *anchor; mutable struct Marker { Node *pointer; unsigned int index; } marker; ... And the part that defines one member function, 'prefix', that puts element at beginning of list: template <typename Element> List<Element> & List<Element>::prefix (const Element &element) { Node *pointer = new Node(element); pointer->up_link = 0; pointer->down_link = anchor; if (anchor) anchor->up_link = pointer; marker.pointer = anchor = pointer; marker.index = 0; population_++; return *this; } -Chaud Lapin- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Sylvain Pion Guest Posted: Wed Oct 29, 2003 9:32 am    Post subject: Re: Constructing objects in place in a container Quote: I still do not understand the problem (never seen STL code), but just Consider the following code : my_big_class x(-4); // a big object which can be constructed from an int. std::vector<my_big_class> V; // an std::vector of such objects V.push_back(x); // you insert it (x gets copied to its final place // in the vector) Now, what I want to do is to avoid the copy of x, and directly construct the object from "-4" inside the vector, something like : std::vector<my_big_class> V; V.push_back(-4); // no temporary my_big_class is created/copied, // but "-4" is passed down internally and a // my_big_class object is constructed from it, inplace. The reference-counting solution looks like a workaround to me, if you consider that useless copies should be avoided in the first place. -- Sylvain [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Wed Oct 29, 2003 4:30 pm    Post subject: Re: Constructing objects in place in a container On 28 Oct 2003 13:42:49 -0500, [email]unoriginal_username (AT) yahoo (DOT) com[/email] (Le Chaud Lapin) wrote: Quote: I still do not understand the problem Node (const Element &element) : element(element) {} This calls the copy ctor to make a copy of the Element which had to be built elsewhere. It takes 17 parameters to make one of those things. Why doesn't your list have a 17 parameter Node contructor which allows constructing in the list? Understood? John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Matthew Collett Guest Posted: Wed Oct 29, 2003 4:35 pm    Post subject: Re: Constructing objects in place in a container In article <fc2e0ade.0310271122.5b2c2a8a (AT) posting (DOT) google.com>, [email]unoriginal_username (AT) yahoo (DOT) com[/email] (Le Chaud Lapin) wrote: Quote: It's hard to believe that STL would do a copy just to insert, so maybe I misunderstand. When an object is inserted in a container, *the object* has to be copied. I still do not understand the problem (never seen STL code), but just in case, here is a portion of my List<> template. As you can see, objects in the list are contructed via new taking the augmenting element as an argument. struct Node { Element element; Node *up_link, *down_link; Node (const Element &element) : element(element) {} } *anchor; The Element member of Node is copy-constructed. That is, you copy the Element being inserted. An STL list would do exactly the same. Best wishes, Matthew Collett -- Those who assert that the mathematical sciences have nothing to say about the good or the beautiful are mistaken. -- Aristotle [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.