Dave Harris wrote:
>
> jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> > Note that this ctor fails to construct the node.  I don't like partially
> > constructed objects.  Setting the two pointers to 0 is only a little
> > better.  That's why I was thinking of a hack to get it constructed right
> > the first time.
>
> OK. Fair point.
>
> I also like the point you made in another article about what happens if we
> have U::operator T() rather than T::T(const U&). In this case we can
> eliminate the copy only if the compiler provides the NRVO. Since the NRVO
> is itself QoI, it seems at least some important insert() cases have to be
> QoI regardless.

However for that "thing" you may have a workaround by providing a
conversion constructor.  However there is no workaround for the extra
copy without changing the library.

Attila

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Tue, 11 Jun 2002 16:13:58 GMT, Attila Feher
<Attila.Feher@lmf.ericsson.se> wrote:

> However for that "thing" you may have a workaround by providing a
> conversion constructor.  However there is no workaround for the extra
> copy without changing the library.

I don't understand.  Create an allocator (copy from your implementation)
with a templated construct member.  Instantiate vector with it.  Use
insert(range).  The copy is gone.  No change to the language or the
library.

Dave wondered (you sniped it) whether this solution would satisfy you.
If not, what do you want?  Be specific.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> What's to customize?  The interface is a pointer and a reference to
> const.  The job is placement new.  Neither the container writer nor
> the allocator writer has any freedom.  What am I missing?

Firstly, the allocator can do things on the side - for example, count the
number of objects it has allocated, or keep a list of where they all are.
This might be useful for profiling memory use, debugging reads/writes to
uninitialised memory, perhaps even some kind of garbage collection. It has
a lot of freedom to do stuff unrelated to its main job.

Secondly, it gives the allocator a chance to "bless" the memory before it
is actually used. As an analogy, modern operating systems can reserve a
range of memory addresses without actually allocating the physical RAM to
back it. The physical RAM doesn't need to be allocated until the bytes in
the address range are actually read or written. Thus with allocators.

I am actually suggesting here a stronger condition than previously: that
memory allocated by an allocator not be read or written before construct()
has been called on it, and not read or written after destroy(). I don't
think this requirement is any more onerous than a requirement to use
construct()/destroy() in the first place. It does, however, provide the
allocator with a software hook for doing any final initialisation it might
want to do.

Is this enough?

I've never written an allocator, and in fact I'm not convinced the
standard needs them. Since they are there, and have construct() and
destroy() methods, it seems to me that they will be more valuable if they
are used consistently. What is to be gained by having some objects
allocated with construct() and some by other mechanisms? Why should an
object allocated by construct() be destroyable via an unrelated call like
p->~T()? Why should the allocator author have to provide the functions if
they are not going to be used?

Note that Howard had suggested the desire for a point of customisation as
an argument /against/ the optimisation.


> Let's see if I understand the proposal.
>
> 1.  Replace the allocator construct member with a template.
> 2.  Require all insert/construct(range) members of all containers to use
>     the construct function directly.
>
> Is that it?

Not really. Here we were discussing what a quality implementation might
actually choose to do, if it were left as QoI. So I suppose the proposal
is to leave it as QoI. Mostly we are still exploring options and
implications.


> As an implementer, I get little freedom in implementing these functions.
> For node-based containers, it seems that some struct hackery must be
> used to pass the pointers and value to the construct function.

The aim here is to allow implementations to combine the conversion with
the copy. How it does that is up to it.

One approach would be to give the Node a single-argument constructor which
takes a T. Thus:

    struct Node {
        T t;
        Node<T> *pNext;
        Node<T> *pPrev;

        template <typename U>
        Node( const U &u ) : t(u) {}
    };

    typedef typename Allocator::rebind<Node>::other NodeAllocator;
    NodeAllocator a;

    NodeAllocator::Pointer p = a.allocate(1);
    a.construct( p, u );

I suppose this is what you mean by "hackery". It doesn't seem like a hack
to me. It just seems to be using the provided functions in a
straight-forward way to achieve the aims. (Rebind itself may be a hack,
but that's another matter.)

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri,  7 Jun 2002 16:28:31 GMT, brangdon@cix.co.uk (Dave Harris)
wrote:

> jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> > What's to customize?  The interface is a pointer and a reference to
> > const.  The job is placement new.  Neither the container writer nor
> > the allocator writer has any freedom.  What am I missing?

> Firstly, the allocator can do things on the side - for example, count the
> number of objects it has allocated, or keep a list of where they all are.
> This might be useful for profiling memory use, debugging reads/writes to
> uninitialised memory, perhaps even some kind of garbage collection. It has
> a lot of freedom to do stuff unrelated to its main job.

That can all be done without the construct/destroy members.

> Secondly, it gives the allocator a chance to "bless" the memory before it
> is actually used. As an analogy, modern operating systems can reserve a
> range of memory addresses without actually allocating the physical RAM to
> back it. The physical RAM doesn't need to be allocated until the bytes in
> the address range are actually read or written. Thus with allocators.

Ok.  That is a gain for the allocator writer and a restriction on the
container writer.

> I am actually suggesting here a stronger condition than previously: that
> memory allocated by an allocator not be read or written before construct()
> has been called on it, and not read or written after destroy(). I don't
> think this requirement is any more onerous than a requirement to use
> construct()/destroy() in the first place. It does, however, provide the
> allocator with a software hook for doing any final initialisation it might
> want to do.

Accepted.

> Is this enough?

Yes, thanks.

> I've never written an allocator, and in fact I'm not convinced the
> standard needs them. Since they are there, and have construct() and
> destroy() methods, it seems to me that they will be more valuable if they
> are used consistently. What is to be gained by having some objects
> allocated with construct() and some by other mechanisms? Why should an
> object allocated by construct() be destroyable via an unrelated call like
> p->~T()? Why should the allocator author have to provide the functions if
> they are not going to be used?

Beats me, but I think that is what the standard requires.  Allocators
*shall* provide the functions and containers *may* use them.  Howard has
no objections to changing the may to shall.  I don't know about others.

> Note that Howard had suggested the desire for a point of customisation as
> an argument /against/ the optimisation.

Is that against the optimization or against the original proposal which
uses another customization object?

> > Let's see if I understand the proposal.

> > 1.  Replace the allocator construct member with a template.
> > 2.  Require all insert/construct(range) members of all containers to use
> >     the construct function directly.

> > Is that it?

> Not really. Here we were discussing what a quality implementation might
> actually choose to do, if it were left as QoI. So I suppose the proposal
> is to leave it as QoI. Mostly we are still exploring options and
> implications.

Ok.  If I provide an allocator with templated construct member, is it
conforming?  If it is, I think we have a portable method to make insert
range efficient for vector with no change to the standard.  I don't
think that it will work for other containers.

It also puts the work on the user who really wanted a templated
push_back and others.

> > As an implementer, I get little freedom in implementing these functions.
> > For node-based containers, it seems that some struct hackery must be
> > used to pass the pointers and value to the construct function.

> The aim here is to allow implementations to combine the conversion with
> the copy. How it does that is up to it.

> One approach would be to give the Node a single-argument constructor which
> takes a T. Thus:

>     struct Node {
>         T t;
>         Node<T> *pNext;
>         Node<T> *pPrev;
>
>         template <typename U>
>         Node( const U &u ) : t(u) {}

Note that this ctor fails to construct the node.  I don't like partially
constructed objects.  Setting the two pointers to 0 is only a little
better.  That's why I was thinking of a hack to get it constructed right
the first time.

>     };

>     typedef typename Allocator::rebind<Node>::other NodeAllocator;
>     NodeAllocator a;

>     NodeAllocator::Pointer p = a.allocate(1);
>     a.construct( p, u );

Now finish the construction.

   p->pNext = pos;
   p->pPrev = pos->pPrev;

> I suppose this is what you mean by "hackery". It doesn't seem like a hack
> to me. It just seems to be using the provided functions in a
> straight-forward way to achieve the aims. (Rebind itself may be a hack,
> but that's another matter.)

No, I was thinking about the hackery needed to convert

   new(p)Node(u, pos, pos->pPrev);

to use the construct member.  I used construction functions which did
the new, filled in the fields and returned the pointer in other
languages before I ever saw a constructor.  I guess that I just see the
allocator as an alternative operator new.  It handles raw memory only.

It has been interesting.  Not sure that we have given anyone much to
think about, but who knows.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> Note that this ctor fails to construct the node.  I don't like partially
> constructed objects.  Setting the two pointers to 0 is only a little
> better.  That's why I was thinking of a hack to get it constructed right
> the first time.

OK. Fair point.

I also like the point you made in another article about what happens if we
have U::operator T() rather than T::T(const U&). In this case we can
eliminate the copy only if the compiler provides the NRVO. Since the NRVO
is itself QoI, it seems at least some important insert() cases have to be
QoI regardless.


> Ok.  If I provide an allocator with templated construct member, is it
> conforming?

As far as I can tell.


> If it is, I think we have a portable method to make insert
> range efficient for vector with no change to the standard.  I don't
> think that it will work for other containers.

Agreed. It looks like QoI is the only way to fly.


> It has been interesting.  Not sure that we have given anyone much to
> think about, but who knows.

I wonder if it satisfies the original posters, Maciej Sobczak and Attila
Feher.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon,  3 Jun 2002 04:12:40 GMT, brangdon@cix.co.uk (Dave Harris)
wrote:

> Also, I don't like exposing the container's uninitialised memory. This is
> a very low-level approach. For example, if my Function is a no-op that
> doesn't actually construct an object, then I can inject uninitialised
> memory into the middle of a vector. I think what we actually want here is
> more like:

>    template <class U>
>    void push_back( const U &u );

> where the T(U) conversion is required to happen exactly once and T(T) not
> to happen at all. This function avoids exposing uninitialised memory.

Interestingly, the original question was why that function does not
exist.  Amazing how far we can go with a simple question.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

maciej@maciejsobczak.com (Maciej Sobczak) wrote (abridged):
> > If i points to uninitialised memory, doesn't the expression &*i yield
> > undefined behaviour?
> [explanation of why it is UB skipped]
>
> Aren't uninitialized_fill and uninitialized_fill_n defined exactly this
> way (20.4.4.2 and 20.4.4.3)?

You're right. There's no reason why the extra requirements of 20.4.4/1
shouldn't be applied to your new functions. I'm still not entirely
comfortable with it, but it isn't anything new.


> > Allocators have a construct() method. Should allocators also have an
> > uninitialized_fill_function() ?
>
> I didn't think about this. Who would use it?

Implementers of containers, or other users of allocators. The idea is for
all construction and destruction to go through the allocator. After all,
allocate::construct() exists and it seems wrong to have some constructions
go one route and others go another.


> > For example, if my Function is a no-op that doesn't actually
> > construct an object, then I can inject uninitialised memory into
> > the middle of a vector.
>
> Yes, exactly.
> But - the same issue applies everywhere, where the client code is
> expected to do something and does not do it. Even in constructors:
> if somebody writes a no-op constructor that doesn't actually
> construct an object, then... Does it mean that the idea of
> constructor is broken?

The difference for me is one of encapsulation. I like all of the
operations which affect the integrity of an object to be part of its
class's definition. So yes, we have to study the constructor carefully,
but as the constructor is part of the class that's reasonable. Once we've
studied the entire class (including friends) we're done.

What bothers me here is that the vector is no longer able to maintain its
own integrity. It's not enough to get the elements right and to get the
vector right. Other code, separate from both vector and element classes,
can always inject unconstructed elements into the middle of the vector.
And this is without using casts, undefined behaviour, or anything at all
tricky. It seems like a loop-hole.


> My proposal is a bit more generic, because:
> - it does not require it (although the Function *can* use "new (p)
> T(u);")
> - it supports more flexible strategy, like calling arbitrary methods
> (like "initObject") on the newly added objects.

It seems as though this separates the job of construction into two parts,
with the second part being done by initObject(), and then having a
builder-function put them together. Why not have the constructor construct
the object completely? In C++, the constructor /is/ the builder-function.
It is exactly the job of the constructor to turn uninitialised memory into
complete objects.

... having said that, I can see it might be useful for containers of
pointers. The build-function could look like:

    void builder( Object **p ) {
        *p = new Object;
    }

The idea here is to bridge the gap between constructing a pointer and
constructing the thing it points to. However, even this can be
accommodated with templated insert members:

    struct ObjectBuilder {
        operator Object *() { return new Object; }
    };

    std::vector<Object *> v;
    ObjectBuilder builder;
    v.insert( v.end(), 100, builder ); // Not current std.
    v.insert( v.end(), &builder, &builder+1 ); // Might work today.

The trick being to use a conversion operator. If we must have
initObject(), the same trick works:

    struct ObjectBuilder {
        operator Object () {
            Object obj;
            obj.initObject();
            return obj;
        }
    };

This relies on the Named Return Value Optimisation to avoid unnecessary
copies.

So I don't think your approach is more generic. It may be more
straight-forward - it's more obvious what a plain function is doing than a
class with a conversion operator. Against this we have the loss of
encapsulation of vector, and the dilution of the concept of construction.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

hinnant@antispam.metrowerks.com (Howard Hinnant) wrote (abridged):
> You can't leave this as a QoI issue and expect it to self correct
> unless there is unambiguous evidence for which path is quality.  I see
> arguments for both paths being quality.  For example if the container
> consistently uses allocator.construct(), this becomes a point of
> customization since client code can supply a custom allocator.

Since allocator.construct() exists, it seems to me it should be used for
constructing all objects in the memory it owns. If it is allowed to be a
template member, it can do the right thing when passed a U instead of a
T. It also provides the single point of customisation. So it seems to me
that this is the "quality" approach.

However, I might be wrong; I've not heard your arguments for the other
routes. If there are strong arguments for both routes, then surely that is
even more reason to grant freedom to implementors? They should know what
their customers want.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <memo.20020604121446.47415B@brangdon.madasafish.com>, Dave
Harris <brangdon@cix.co.uk> wrote:

| If it is allowed to be a
| template member, it can do the right thing when passed a U instead of a
| T. It also provides the single point of customisation. So it seems to me
| that this is the "quality" approach.

I agree, this proposal sounds most interesting.

--
Howard Hinnant
Metrowerks

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> You must have missed my article and Howard's response.

Yes; sorry. I've found it now. It reached my server but didn't get linked
into the right thread. I needed to use Google to track it down.


> Sorry, A does not have that ctor.

Then give Wrapper an operator A() conversion, and rely on the Named Return
Value Optimisation.


> >         Wrapper w(a,b,c,d);
> >         v.insert( v.end(), &w, &w+1 );
>
> I really need to stretch my imagination to see that as an iterator.

The arguments here are (Wrapper *), which is a plain pointer. All pointers
are iterators.


> Yes, a bunch more code to write.

True. And it addresses a case which the original proposal didn't bother
with. On the other hand, the "range of constants" iterator isn't tied to
std::vector. It could be made into a template and reused. In some
situations it may be more appropriate than fill_n().


> Since the standard does not specify, it is QoI now.
>
> The bottom line question is whether this optimization is worth the
> effort to add something to the standard.

I am not personally concerned about the optimisation. However, I would
currently rather see something like this than the original proposal. More
generally, it's been pointed out before that the design of allocators
could do with review, and some more template member functions added to
them (eg to simplify cases which currently need rebind()). Perhaps these
issues could be born in mind if/when that happens.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Tue,  4 Jun 2002 17:48:31 GMT, Howard Hinnant
<hinnant@antispam.metrowerks.com> wrote:

> In article <memo.20020604121446.47415B@brangdon.madasafish.com>, Dave
> Harris <brangdon@cix.co.uk> wrote:
>
> | If it is allowed to be a
> | template member, it can do the right thing when passed a U instead of a
> | T. It also provides the single point of customisation. So it seems to me
> | that this is the "quality" approach.

What's to customize?  The interface is a pointer and a reference to
const.  The job is placement new.  Neither the container writer nor
the allocator writer has any freedom.  What am I missing?

> I agree, this proposal sounds most interesting.

Let's see if I understand the proposal.

1.  Replace the allocator construct member with a template.
2.  Require all insert/construct(range) members of all containers to use
    the construct function directly.

Is that it?

As a user, I get to hack any other insert/construct into the range form
to gain performance.

As an implementer, I get little freedom in implementing these functions.
For node-based containers, it seems that some struct hackery must be
used to pass the pointers and value to the construct function.

I don't see much gain for anyone, but maybe I am missing the point.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello,

"Christopher Eltschka" <celtschk@web.de> wrote in message
news:ad36ap$oaa$1@news.tuwien.ac.at...
> jpotter@falcon.lhup.edu (John Potter) writes:
> What about:
>
> template<typename F>
>  void construct_insert(iterator pos, F f, size_type count);
>
> Adds space for count objects at position pos, then executes f(p) for
> each position in order, where p is a void pointer to the memory
> location of the object to create. f(p) then must construct an object
> of type value_type at that address.

Yes, it can be generalized this way. However, as I've pointed out in my
other post, insert does not necessarily leave the uninitialized room for new
objects.

Let's suppose:

vector<A> v;
v.reserve(10);

v.push_back(a0);
// ...
v.push_back(a5);

Then:

v.insert(v.begin() + 2, ax, 3);

will probably (common implementation) move a2, a3, a4, a5 three places
towards bigger indexes, using partially uninitialized_copy and partially
normal assignment and leave you with something like:

a0 a1 a2 a3 a4 a2 a3 a4 a5

and then will perform normal assignment, so that the sequence will look
like:

a0 a1 ax ax ax a2 a3 a4 a5

The problem with insert_function (or construct_insert) is that it would need
to destroy first all the objects that occupy the range where the new objects
will be constructed.
In other words, construct_insert would need to do:

start:
a0 a1 a2 a3 a4 a5
shift:
a0 a1 a2 a3 a4 a2 a3 a4 a5
destroy:
a0 a1 __ __ __ a2 a3 a4 a5
construct using f:
a0 a1 ax ax ax a2 a3 a4 a5

Of course, such a function can be implemented and someone will probably find
some use for it.
Anyway, it would be a good support for push_back_function (or
construct_push_back), because there you have uninitialized memory for free,
as a natural intermediary step in growing the sequence.

On my page I propose the minimal implementation for push_back_function,
which is, well, just a hack over copy'n'paste body of insert method. But
this was done only for presentation purposes and I can easily imagine that
common code can be refactored out.

> template<typename F>
>  void contruct_push_back(F f)
[...]
> template<typename F>
>  void construct_push_front(F f)

Good names!

The problem is still the range of problems that this extension can solve.
Avoidance of unneeded temporary is one of them and it has triggered the
concept. Another one can be some intelligent construction of the new objects
(with your construct_insert), if we take into account the fact that the
functor can carry some variable state inside. This state can influence the
construction of consecutive objects. Just brainstorming.

Best regards,

--
Maciej Sobczak
http://www.maciejsobczak.com/



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> Ok, that does make it look like what it is, a generator.

Part of the job here is to transfer arbitrary constructor parameters from
the caller to the actual construction point. An iterator could also do
that.


> It still does not cover an unitialized_insert (pos, first, last, trans)
> which is a transform insertion not a generator.

std::vector already has:

    template <typename ForwardIterator>
    void insert( iterator pos,
          ForwardIterator first, ForwardIterator last );

which does the first part of the job. The templated Allocator function
mentioned earlier:

    template <typename U>
    void construct( pointer p, const U &value );

does the second part of the job, the actual in-place construction. Putting
them together involving some code like:

    allocator.construct( p, *first );

handles the range-insert directly. We can treat push_back() as:

    vec.insert( vec.end(), &value, (&value)+1 );

Here is the iterator is just a plain pointer, a (U*). We need value to be
convertable to a T. If we control T, we can give it a suitable constructor
T(U) directly (as the original poster had done). Alternatively, we can
give the U type an operator T() conversion - this can still avoid
unnecessary temporaries if the compiler implements the Return Value
Optimisations. U can even wrap multiple arguments, as described for
keyword arguments in D&E 6.5.1.1.

So we need the new templated method in Allocator but we don't actually
need to change the interface to vector. The existing templated insert() is
sufficient. Using iterators avoids the need to expose the vector's raw
memory, which I see as an advantage. The construction happens much the
same as it happens today. In particular, there are no new issues for
exception safety.

I suspect that if we make our own allocator class, instead of using
std::allocator, and we give it a templated construct(), std::vector will
start to use it immediately. In other words, we can do this today with no
library or languages changes at all. I've not tested it though. My local
std::vector implementation doesn't provide member templates :-(

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 31 May 2002 23:25:49 GMT, brangdon@cix.co.uk (Dave Harris)
wrote:

> jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> > Ok, that does make it look like what it is, a generator.

> Part of the job here is to transfer arbitrary constructor parameters from
> the caller to the actual construction point. An iterator could also do
> that.

I don't think that you followed the original thread on clc++m.  It is a
bit cluttered with word games.  The original problem was a simple
vector<A>::push_back(B) where A had a ctor taking a B.  The desire was
to optimize A(A(B)) to A(B).  There was also speculation about an
arbitrary set of parameters which led to this proposal.  The original
poster has stated that the original problem was the real desire and that
the expansion was just speculation.

I don't seem to be able to follow your assertion that an iterator could
do the expanded problem.  How do you translate v.push_back(a, b, c, d)
where A has the appropriate ctor to iterators without extra copies?

> > It still does not cover an unitialized_insert (pos, first, last, trans)
> > which is a transform insertion not a generator.

> std::vector already has:

>     template <typename ForwardIterator>
>     void insert( iterator pos,
>           ForwardIterator first, ForwardIterator last );

> which does the first part of the job. The templated Allocator function
> mentioned earlier:

>     template <typename U>
>     void construct( pointer p, const U &value );

> does the second part of the job, the actual in-place construction. Putting
> them together involving some code like:

>     allocator.construct( p, *first );

> handles the range-insert directly. We can treat push_back() as:

>     vec.insert( vec.end(), &value, (&value)+1 );

> Here is the iterator is just a plain pointer, a (U*). We need value to be
> convertable to a T. If we control T, we can give it a suitable constructor
> T(U) directly (as the original poster had done).

Yes, that was my hack in clc++m.  It works fine with gcc since it does
not use allocator.construct.  It failed on the CW implementation because
it uses allocator.construct.  AFAICT, both are valid.

> So we need the new templated method in Allocator but we don't actually
> need to change the interface to vector. The existing templated insert() is
> sufficient. Using iterators avoids the need to expose the vector's raw
> memory, which I see as an advantage. The construction happens much the
> same as it happens today. In particular, there are no new issues for
> exception safety.

Agreed.

> I suspect that if we make our own allocator class, instead of using
> std::allocator, and we give it a templated construct(), std::vector will
> start to use it immediately. In other words, we can do this today with no
> library or languages changes at all. I've not tested it though. My local
> std::vector implementation doesn't provide member templates :-(

That should solve the CW implementation.  All you need to do is write an
allocator. ;-)  Gcc works now without it.  It also covers the like
ctors.

I will assume that anyone interested in this efficiency will also have
an A::operator=(B const&).  That covers insert(pos, B) via the same hack
and any actual range insertion.

It does not cover insert(pos, n, B) for n != 1.  I think that we can
accept one temporary A to copy construct or assign n items.  Same for
the ctor.

Now that we agree that there is no need for this proposal because it can
be done anyway, let's look at the other containers.

List::insert(range) is logically implemented in terms of insert(pos,
val).  There is nothing to be gained by writing anything other than a
simple loop which uses insert(pos, val).  Gcc does this.  Our hack fails
and an allocator will not help.

So, we can't do it today.  Is there any justification for changing the
standard to force an optimization on implementers?  Is there a
precident?  Is QoI good enough since there is a hack which could work?

Does anyone have any feedback for Maciej on whether this idea is worth
expansion to a formal proposal?

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

maciej@maciejsobczak.com (Maciej Sobczak) wrote (abridged):
> The Function object is supposed to be called this way:
>
> f(&*i);
>
> where i is the iterator value in the appropriate range. The f function
> object's responsibility is to either create new object pointed by the
> iterator or throw an exception.

If i points to uninitialised memory, doesn't the expression &*i yield
undefined behaviour? I know that some people think it should be
well-defined when i is a plain pointer, but I think the issue is still
controversial.

In any case, you are defining it for iterators in general. Indeed, the
only times you need &*i instead of plain i is when these evaluate to
different results - so the pair of operations cannot be optimised away. *i
may be non-trivial, user-defined code. The potential for bad undefined
behaviour seems real.

Basically, I am uncomfortable with these functions because their arguments
don't seem like proper iterators.

Allocators have a construct() method. Should allocators also have an
uninitialized_fill_function() ?


> template <class Function>
> void push_back_function(Function f);

I'm not sure the efficiency saving is worth the extra complexity.

Also, I don't like exposing the container's uninitialised memory. This is
a very low-level approach. For example, if my Function is a no-op that
doesn't actually construct an object, then I can inject uninitialised
memory into the middle of a vector. I think what we actually want here is
more like:

   template <class U>
   void push_back( const U &u );

where the T(U) conversion is required to happen exactly once and T(T) not
to happen at all. This function avoids exposing uninitialised memory.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> I don't think that you followed the original thread on clc++m.

Actually I did. I even posted 2 articles to it, although they were in
favour of library changes. I just re-read the thread again, and I don't
think anyone has suggested using the 3-iterator version of insert() to do
push_back()'s job.

If I've been lax, it was in not closely following the thread here. I
treated it as a continuation of clc++m thread and I'm really trying to
solve the original poster's problem, which was to avoid copying certain
large objects. Copying references to these objects seems to be OK.


> I don't seem to be able to follow your assertion that an iterator could
> do the expanded problem.  How do you translate v.push_back(a, b, c, d)
> where A has the appropriate ctor to iterators without extra copies?

Like:

    struct Wrapper {
        A &a; B &b; C &c; D &d;
        Wrapper( A &a_, B &b_, C &c_, D &d_ ) :
             a(a_), b(b_), c(c_), d(d_) {}
    };

    struct A {
        A( const Wrapper &w ) {
            // ...
        }
    };

    inline void push_back( vector<A> &v, A &a, B &b, C &c, D &d ) {
        Wrapper w(a,b,c,d);
        v.insert( v.end(), &w, &w+1 );
    }

    push_back( v, a, b, c, d );

With a good compiler this ought to produce good code. We avoid copying the
a,b,c,d objects, which are the objects which might be arbitrarily large. I
suspect we won't even have to copy the references after everything is
inlined.

I had to change the syntax from v.push_back(a,b,c,d) to push_back(v,
a,b,c,d). This doesn't bother me much. This is an optimisation which most
people probably won't need at all, and I think it's acceptable to
sometimes have to write slightly obscure code to maximise performance.


> It does not cover insert(pos, n, B) for n != 1.

We can handle that with a smarter iterator. Treat it as:

    struct WrapperIterator {
        int i;
        B *pb;
        WrapperIterator() : i(0), pb(0) {}
        WrapperIterator( int i_, B &b_ ) : i(i_), pb(&b_) {}
        B &operator *() { return *pb; }
        WrapperIterator &operator++() { --i; return *this; }
        bool operator!=( const WrapperIterator &wi ) const {
            return i != wi.i;
        }
        // ...
    };

    inline void insert( vector<A> &v, vector<A>::iterator pos,
            int n, B &b ) {
        v.insert( pos, WrapperIterator(n,b), WrapperIterator() );
    }

This iterator always returns the same object for *i, so a pair of them
behave like a range of n copies of that object. We don't have to actually
copy the B object.

(Incidently, this is an example of an idiom that would be simpler if STL
algorithms represented sequences explicitly as a single object, rather
than implicitly as a pair of iterators. But that's another debate.)


> List::insert(range) is logically implemented in terms of insert(pos,
> val).  There is nothing to be gained by writing anything other than a
> simple loop which uses insert(pos, val).  Gcc does this.  Our hack fails
> and an allocator will not help.

Agreed. By the same token, the vector::insert(pos,first,last) approach
won't work if that function is implemented in terms of
insert(pos,1,value).

I think the standard is unclear here. It specifies the number of copies of
A but does not say anything about copies of B, or conversions from B to A.
Since these are observable behaviour they ought to be documented. I think
the intent is that *first be an A, not just something convertable to A,
but I don't see that restriction stated explicitly.


> So, we can't do it today.  Is there any justification for changing the
> standard to force an optimization on implementers?  Is there a
> precident?  Is QoI good enough since there is a hack which could work?

I think we need a standard change regardless, to tighten up what it says
about the templated insert functions. We can either make these hacks
illegal (ie require *first to be an A), or make them legal but with no
efficiency advantage over the non-templated functions, or mandate the
efficiency advantage, or make it QoI.

We need feedback from compiler vendors. My guess is that if we make it
QoI, most of them will eventually adopt the efficient implementations. Is
there any reason not to, now that the advantage has been pointed out?
However, also I think the fact that the standard already specifies the
number of times items are copied for these insert operators, is precedent
for specifying what happens with conversions.


> Does anyone have any feedback for Maciej on whether this idea is worth
> expansion to a formal proposal?

I don't like it. I'll say more in another article.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <memo.20020602042401.51291A@brangdon.madasafish.com>, Dave
Harris <brangdon@cix.co.uk> wrote:

| We need feedback from compiler vendors. My guess is that if we make it
| QoI, most of them will eventually adopt the efficient implementations. Is
| there any reason not to, now that the advantage has been pointed out?

Your post does not seem to address the basis for the varying behavior:

One implementation uses placement new via allocator.construct() to
construct new elements.  Another implementation uses placement new via
uninitialized_fill().  The path dictates which type placement new is
instantiated with (the container type or the external element type).

You can't leave this as a QoI issue and expect it to self correct
unless there is unambiguous evidence for which path is quality.  I see
arguments for both paths being quality.  For example if the container
consistently uses allocator.construct(), this becomes a point of
customization since client code can supply a custom allocator.

--
Howard Hinnant
Metrowerks

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello,

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20020602042405.51291B@brangdon.madasafish.com...
> maciej@maciejsobczak.com (Maciej Sobczak) wrote (abridged):
> > The Function object is supposed to be called this way:
> >
> > f(&*i);
> >
> > where i is the iterator value in the appropriate range. The f function
> > object's responsibility is to either create new object pointed by the
> > iterator or throw an exception.
>
> If i points to uninitialised memory, doesn't the expression &*i yield
> undefined behaviour?
[explanation of why it is UB skipped]

Aren't uninitialized_fill and uninitialized_fill_n defined exactly this way
(20.4.4.2 and 20.4.4.3)?
I have not found any defect report on this.
I'm not proficient enough with the standardese to come up with the proper
syntax by myself. ;-)
I have written it based on what I saw elsewhere in the Standard.
In this context, your post surprises me.

To be honest, I was surprised to see the "&*first" expression in the
Standard, but I think that implementing these operators in "unexpected ways"
is asking for troubles anyway, so I've given up. However, I'll be grateful
for further explanations, not in terms of possible dangers (which I
understand) but in terms of what is already there.

> Basically, I am uncomfortable with these functions because their arguments
> don't seem like proper iterators.

Same. Are 20.4.4.2 and 20.4.4.3 broken?

> Allocators have a construct() method. Should allocators also have an
> uninitialized_fill_function() ?

I didn't think about this. Who would use it? I mean - how to call it?
My intent was to provide a way to pull the construction process outside of
the container so that the client code can have more control over it. It
seems quite reasonable to me to call push_xxx_function on the container, but
I do not expect myself calling such a "thing" on the allocator. Maybe just
because I do not use allocatos daily.

> > template <class Function>
> > void push_back_function(Function f);
>
> I'm not sure the efficiency saving is worth the extra complexity.
>
> Also, I don't like exposing the container's uninitialised memory.

This bothers me, too.

> This is
> a very low-level approach.

As low as it can take and still deserve the STL name, I think.

> For example, if my Function is a no-op that
> doesn't actually construct an object, then I can inject uninitialised
> memory into the middle of a vector.

Yes, exactly.
But - the same issue applies everywhere, where the client code is expected
to do something and does not do it. Even in constructors: if somebody writes
a no-op constructor that doesn't actually construct an object, then...
Does it mean that the idea of constructor is broken? push_xxx_function is
supposed to be just a call-back constructor.

> I think what we actually want here is
> more like:
>
>    template <class U>
>    void push_back( const U &u );
>
> where the T(U) conversion is required to happen exactly once and T(T) not
> to happen at all. This function avoids exposing uninitialised memory.

Yes, that would solve the case, where T(U) is well-defined.
My proposal is a bit more generic, because:
- it does not require it (although the Function *can* use "new (p) T(u);")
- it supports more flexible strategy, like calling arbitrary methods (like
"initObject") on the newly added objects.

Best regards,

--
Maciej Sobczak
http://www.maciejsobczak.com/



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Maciej Sobczak" <maciej@maciejsobczak.com> writes:

> Hello,
>
> "Christopher Eltschka" <celtschk@web.de> wrote in message
> news:ad36ap$oaa$1@news.tuwien.ac.at...
> > jpotter@falcon.lhup.edu (John Potter) writes:
> > What about:
> >
> > template<typename F>
> >  void construct_insert(iterator pos, F f, size_type count);
> >
> > Adds space for count objects at position pos, then executes f(p) for
> > each position in order, where p is a void pointer to the memory
> > location of the object to create. f(p) then must construct an object
> > of type value_type at that address.
>
> Yes, it can be generalized this way. However, as I've pointed out in my
> other post, insert does not necessarily leave the uninitialized room for new
> objects.

This depends on the container.

>
> Let's suppose:
>
> vector<A> v;
> v.reserve(10);
>
> v.push_back(a0);
> // ...
> v.push_back(a5);

Let's also suppose:

list<A> l;

l.push_back(a0);
...
l.push_back(a5);

>
> Then:
>
> v.insert(v.begin() + 2, ax, 3);
>
> will probably (common implementation) move a2, a3, a4, a5 three places
> towards bigger indexes, using partially uninitialized_copy and partially
> normal assignment and leave you with something like:
>
> a0 a1 a2 a3 a4 a2 a3 a4 a5
>
> and then will perform normal assignment, so that the sequence will look
> like:
>
> a0 a1 ax ax ax a2 a3 a4 a5

Then with iter being 2 away from l.begin(),

v.insert(iter, ax, 3);

will probably (common implamantation) insert thee new elements,
copying ax three times:

a0 a1 ax ax ax a2 a3 a4 a5

>
> The problem with insert_function (or construct_insert) is that it would need
> to destroy first all the objects that occupy the range where the new objects
> will be constructed.

The advantage with insert_function (or construct_insert) is that the
ax can be generated just in place (and in addition, they need not even
be identical), instead of copying them.

> In other words, construct_insert would need to do:
>
> start:
> a0 a1 a2 a3 a4 a5
> shift:
> a0 a1 a2 a3 a4 a2 a3 a4 a5
> destroy:
> a0 a1 __ __ __ a2 a3 a4 a5
> construct using f:
> a0 a1 ax ax ax a2 a3 a4 a5

In other words, for the list construct_insert would be able to do:

start:
a0 a1 a2 a3 a4 a5
insert (not moving a? in memory):
a0 a1 __ __ __ a2 a3 a4 a5
constructing using f:
a0 a1 ax ax ax a2 a3 a4 a5


BTW, the vector could also move the objects one-by-one (which might be
an advantage for objects with large "out-of-object" parts,
i.e. dynamic allocated memory, or if assignment is more expensive than
destruct/construct):

a0 a1 a2 a3 a4 a5 __ __ __
a0 a1 a2 a3 a4 a5 __ __ a5
a0 a1 a2 a3 a4 __ __ __ a5
...
a0 a1 a2 __ __ a2 a3 a4 a5
a0 a1 __ __ __ a2 a3 a4 a5
a0 a1 ax ax ax a2 a3 a4 a5

Note that there are never more than 6 objects during move.

Indeed, I'm on the opinion that there should be a standard-supported
move operation, and this move operation should be used whenever
objects are relocated. Such a move operation can generally be
implemented much cheaper than copy or assignment (f.ex, for reference
counting, there's no need to access the reference counter at all; for
classes using dynamic memory without RC, it's just copying the pointer
instead of allocating the memory, copying the content and then
deallocating the old memory during the following destruction or
assignment).

Now, using such a standard-supported move operation, the vector
behaviour you showed for construct_insert would be the standard one.

>
> Of course, such a function can be implemented and someone will probably find
> some use for it.
> Anyway, it would be a good support for push_back_function (or
> construct_push_back), because there you have uninitialized memory for free,
> as a natural intermediary step in growing the sequence.

And for certain containers, you also have uninitialized memory for
free in the middle. Also in C++-as-I-would-like-it-to-be(tm), you
would have uninitialized memory for free in vector as well (while
being more efficient for almost all objects with nontrivial
copy/assignment).

>
> On my page I propose the minimal implementation for push_back_function,
> which is, well, just a hack over copy'n'paste body of insert method. But
> this was done only for presentation purposes and I can easily imagine that
> common code can be refactored out.
>
> > template<typename F>
> >  void contruct_push_back(F f)
> [...]
> > template<typename F>
> >  void construct_push_front(F f)
>
> Good names!
>
> The problem is still the range of problems that this extension can solve.
> Avoidance of unneeded temporary is one of them and it has triggered the
> concept. Another one can be some intelligent construction of the new objects
> (with your construct_insert), if we take into account the fact that the
> functor can carry some variable state inside. This state can influence the
> construction of consecutive objects. Just brainstorming.

That's one of the points of construct_insert. You cannot use input
iterator ranges, since they don't construct into given memory, but
produce a temporary value to be copied. construct_insert now also
allows to inplace-construct a range of values.

Indeed, it's a workaround to another C++-intrinsic inefficiency. By
their nature, value-returning functions construct objects (of course
only indirectly through "real" object constructors). However, while
"real" object destructors can not only be used to create temporaries
through Classname(arguments), but can be used to directly create
objects in variables (normal variable definition) and on newly
allocated (new) or even arbitrary (placement new) memory, functions
are restricted to create their return values as temporaries (which
_might_ be optimized away by the compiler, but that's not guaranteed).

Quite a while ago I made a suggestion (which did not get a very
positive echo), to change this, by allowing thing like

  Myclass foo(int);

  foo myvar(5); // defined myvar of type Myclass,
                // constructed by foo(5)

  new foo(5); // allocates an object of type Myclass and initializes
              // through foo(5)

  new(ptr) foo(5); // placement new of foo(5)

This would resolve the direct-construction with input iterators:

  new(ptr) iter.operator*();

It would also automatically include the often wanted declare feature:

Instead of

  declare iter = v.begin();

one could simply write

  v.begin iter;

Now, as I said, the echo wasn't too positive, so I don't think this
would have any chance to get into C++, but I still consider it the
right way (the syntax of course might be improveable).

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Maciej Sobczak wrote:
> Aren't uninitialized_fill and uninitialized_fill_n defined exactly this way
> (20.4.4.2 and 20.4.4.3)?

You missed the requirements in 20.4.4/1.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon,  3 Jun 2002 04:12:55 GMT, brangdon@cix.co.uk (Dave Harris)
wrote:

> jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> > I don't think that you followed the original thread on clc++m.
>
> Actually I did. I even posted 2 articles to it, although they were in
> favour of library changes. I just re-read the thread again, and I don't
> think anyone has suggested using the 3-iterator version of insert() to do
> push_back()'s job.

You must have missed my article and Howard's response.

> > I don't seem to be able to follow your assertion that an iterator could
> > do the expanded problem.  How do you translate v.push_back(a, b, c, d)
> > where A has the appropriate ctor to iterators without extra copies?

> Like:

>     struct Wrapper {
>         A &a; B &b; C &c; D &d;
>         Wrapper( A &a_, B &b_, C &c_, D &d_ ) :
>              a(a_), b(b_), c(c_), d(d_) {}
>     };

>     struct A {
>         A( const Wrapper &w ) {
>             // ...
>         }
>     };

Sorry, A does not have that ctor.

>     inline void push_back( vector<A> &v, A &a, B &b, C &c, D &d ) {
>         Wrapper w(a,b,c,d);
>         v.insert( v.end(), &w, &w+1 );
>     }
>
>     push_back( v, a, b, c, d );

> With a good compiler this ought to produce good code. We avoid copying the
> a,b,c,d objects, which are the objects which might be arbitrarily large. I
> suspect we won't even have to copy the references after everything is
> inlined.

> I had to change the syntax from v.push_back(a,b,c,d) to push_back(v,
> a,b,c,d). This doesn't bother me much. This is an optimisation which most
> people probably won't need at all, and I think it's acceptable to
> sometimes have to write slightly obscure code to maximise performance.

I really need to stretch my imagination to see that as an iterator.  I
do agree with your statement about optimization.

> > It does not cover insert(pos, n, B) for n != 1.

> We can handle that with a smarter iterator. Treat it as:

>     struct WrapperIterator {
>         int i;
>         B *pb;
>         WrapperIterator() : i(0), pb(0) {}
>         WrapperIterator( int i_, B &b_ ) : i(i_), pb(&b_) {}
>         B &operator *() { return *pb; }
>         WrapperIterator &operator++() { --i; return *this; }
>         bool operator!=( const WrapperIterator &wi ) const {
>             return i != wi.i;
>         }
>         // ...
>     };

>     inline void insert( vector<A> &v, vector<A>::iterator pos,
>             int n, B &b ) {
>         v.insert( pos, WrapperIterator(n,b), WrapperIterator() );
>     }

> This iterator always returns the same object for *i, so a pair of them
> behave like a range of n copies of that object. We don't have to actually
> copy the B object.

Yes, a bunch more code to write.

> > List::insert(range) is logically implemented in terms of insert(pos,
> > val).  There is nothing to be gained by writing anything other than a
> > simple loop which uses insert(pos, val).  Gcc does this.  Our hack fails
> > and an allocator will not help.

> Agreed. By the same token, the vector::insert(pos,first,last) approach
> won't work if that function is implemented in terms of
> insert(pos,1,value).

That is not allowed except for input iterators.  The standard specifies
that it will be linear and that would be quadratic.

> I think the standard is unclear here. It specifies the number of copies of
> A but does not say anything about copies of B, or conversions from B to A.
> Since these are observable behaviour they ought to be documented. I think
> the intent is that *first be an A, not just something convertable to A,
> but I don't see that restriction stated explicitly.

Maybe the standard says only what was intended.

> > So, we can't do it today.  Is there any justification for changing the
> > standard to force an optimization on implementers?  Is there a
> > precident?  Is QoI good enough since there is a hack which could work?

> I think we need a standard change regardless, to tighten up what it says
> about the templated insert functions. We can either make these hacks
> illegal (ie require *first to be an A), or make them legal but with no
> efficiency advantage over the non-templated functions, or mandate the
> efficiency advantage, or make it QoI.

Since the standard does not specify, it is QoI now.

The bottom line question is whether this optimization is worth the
effort to add something to the standard.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) writes:

> On Mon, 27 May 2002 17:44:40 GMT, "Maciej Sobczak"
> <maciej@maciejsobczak.com> wrote:
>
> > Following the thread on comp.lang.c++.moderated titled "Do not pay for...
> > xxx.push_back()", I have noticed an opportunity for library extension.
> > The extension is targeted at the Standard Sequence classes (vector, deque,
> > list), where push_back and push_front methods are defined, but it can be
> > also viable for Associative containers.
>
> Considering that c.push_back(x) and c.push_front(x) are just sugar for
> c.insert(c.end(), x) and c.insert(c.begin(), x), what are you doing for
> the real function?
>
> Even these could be considered sugar for c.insert(pos, &x, &x + 1).
> What about this function in the general form c.insert(pos, ib, ie)?

What about:

template<typename F>
 void construct_insert(iterator pos, F f, size_type count);

Adds space for count objects at position pos, then executes f(p) for
each position in order, where p is a void pointer to the memory
location of the object to create. f(p) then must construct an object
of type value_type at that address.

template<typename F>
 void construct_insert(iterator pos, F f)

Has the same effect as construct_insert(pos, f, 1)

template<typename F>
 void contruct_push_back(F f)

Has the same effect as construct_insert(end(), f)

template<typename F>
 void construct_push_front(F f)

Has the same effect as construct_insert(begin(), f)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Wed, 29 May 2002 19:35:14 GMT, Christopher Eltschka <celtschk@web.de>
wrote:

> jpotter@falcon.lhup.edu (John Potter) writes:

> > Even these could be considered sugar for c.insert(pos, &x, &x + 1).
> > What about this function in the general form c.insert(pos, ib, ie)?

> What about:

> template<typename F>
>  void construct_insert(iterator pos, F f, size_type count);

> Adds space for count objects at position pos, then executes f(p) for
> each position in order, where p is a void pointer to the memory
> location of the object to create. f(p) then must construct an object
> of type value_type at that address.

Ok, that does make it look like what it is, a generator.  Then the two
algorithms should be uninitialized_generate and
uninitialized_generate_n.  The unitialized_insert and push_xxx can be
written in terms of that.

It still does not cover an unitialized_insert (pos, first, last, trans)
which is a transform insertion not a generator.

I guess that you could use a generator which gets the range as
constructor arguements and hope that n matches the distance.  It just
does not seem right.

It would also be possible to use a countdown iterator to get insert n
from insert range without the matching problem.

Anyway, both insert n and insert range seem to be the basic operations.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Wed, 29 May 2002 15:10:54 GMT, "Maciej Sobczak"
<maciej@maciejsobczak.com> wrote:

Devil's advocate.

> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:3cf422df.43235955@news.earthlink.net...
> > On Mon, 27 May 2002 17:44:40 GMT, "Maciej Sobczak"
> > Considering that c.push_back(x) and c.push_front(x) are just sugar for
> > c.insert(c.end(), x) and c.insert(c.begin(), x), what are you doing for
> > the real function?

> I propose to implement the push_xxx_function without using existing interts.

You propose to require all implementations to do it your way.

> > Even these could be considered sugar for c.insert(pos, &x, &x + 1).
> > What about this function in the general form c.insert(pos, ib, ie)?

> Well, with containers that use contiguous (either required or not) memory
> blocks (vector and deque apply), this method will not buy you anything. The
> reason is that inserting in the middle of the sequence usually involves
> copying (shifting) the required number of elements to make a room for new
> objects. This "room", however, is not (in general) entirely uninitialized.

Yes, but it may be partially uninitialized.  Consider inserting 10
elements in the middle of a vector containing 10 elements.  It should
copy initialize the new last five from the old last five.  Wonderful
initialize the first five new items using the function and assign the
last five original items not using the function.  How does this work?

Of course, it is also possible to back_insert the ten elements and then
rotate into place.  This should be much better.  Why not require all
implementations to do it this way?

> Using my functor there would be asking for undefined behavior.

Not if implementations are required to do it the right way.

> One would
> wipe out the underlying block, but calling destructors just to pretend that
> there is again uninitialized memory would be an overkill whereas my proposal
> is about performance. Or, maybe not - that depends on the particular
> application.

It is all about performance.  It does nothing which can not be done with

the existing library.  It does nothing but save a copy.

It does not generalize.  What about back(front)_insert_iterator?  How
does it fit with algorithms?  What about container ctors?  If I can
write a for loop to back insert a container of B into a container of A
using this push_back_function, why can't I use copy or the ctor which
takes a range to do the same thing as efficiently?

> Please look into the code here:

That can only show what you have done.  It can say nothing about
what should be done or how it should be standardized.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 27 May 2002 17:44:40 GMT, "Maciej Sobczak"
<maciej@maciejsobczak.com> wrote:

> Following the thread on comp.lang.c++.moderated titled "Do not pay for...
> xxx.push_back()", I have noticed an opportunity for library extension.
> The extension is targeted at the Standard Sequence classes (vector, deque,
> list), where push_back and push_front methods are defined, but it can be
> also viable for Associative containers.

Considering that c.push_back(x) and c.push_front(x) are just sugar for
c.insert(c.end(), x) and c.insert(c.begin(), x), what are you doing for
the real function?

Even these could be considered sugar for c.insert(pos, &x, &x + 1).
What about this function in the general form c.insert(pos, ib, ie)?

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello,

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:3cf422df.43235955@news.earthlink.net...
> On Mon, 27 May 2002 17:44:40 GMT, "Maciej Sobczak"
> Considering that c.push_back(x) and c.push_front(x) are just sugar for
> c.insert(c.end(), x) and c.insert(c.begin(), x), what are you doing for
> the real function?

I propose to implement the push_xxx_function without using existing interts.

> Even these could be considered sugar for c.insert(pos, &x, &x + 1).
> What about this function in the general form c.insert(pos, ib, ie)?

Well, with containers that use contiguous (either required or not) memory
blocks (vector and deque apply), this method will not buy you anything. The
reason is that inserting in the middle of the sequence usually involves
copying (shifting) the required number of elements to make a room for new
objects. This "room", however, is not (in general) entirely uninitialized.
Using my functor there would be asking for undefined behavior. One would
wipe out the underlying block, but calling destructors just to pretend that
there is again uninitialized memory would be an overkill whereas my proposal
is about performance. Or, maybe not - that depends on the particular
application.

With lists it is not that hard: all new elements, whenever inserted, can be
created with assumption that the uninitialized memory is an arena. But I'm
far from proposing a special case here.

I propose only push_xxx_function for containers, where analogous push_xxx
are defined.

Please look into the code here:

http://www.maciejsobczak.com/_temp/cpp/

for examples how I see one reasonable (I hope) implementation of
vector::push_back_function.

Best regards,

--
Maciej Sobczak
http://www.maciejsobczak.com/



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello,

This is my first attempt to propose a library extension, so please be
forgiving if I'm outside of the etiquette...

Following the thread on comp.lang.c++.moderated titled "Do not pay for...
xxx.push_back()", I have noticed an opportunity for library extension.
The extension is targeted at the Standard Sequence classes (vector, deque,
list), where push_back and push_front methods are defined, but it can be
also viable for Associative containers.

The objective of this proposal is to provide a generic and easy way to add
elements to the container without the need to create a temporary object,
when the target object (inside the container) is created from some other
object of different type. The options discussed on clc++m covered
variable-length argument templates. My proposal does not need any changes in
the language.

What to add:
1. I propose to add the two algorithms to the <memory> header:

template <class ForwardIterator, class Function>
void uninitialized_fill_function(ForwardIterator first, ForwardIterator
last, Function f);

template <class ForwardIterator, class Size, class Function>
void uninitialized_fill_function_n(ForwardIterator first, Size n, Function
f);

The above functions call the function object f for each iterator value in
the given range.
The Function object is supposed to be called this way:

f(&*i);

where i is the iterator value in the appropriate range. The f function
object's responsibility is to either create new object pointed by the
iterator or throw an exception.

2. I propose to add the methods:

template <class Function>
void push_front_function(Function f);

template <class Function>
void push_back_function(Function f);

to the sequence classes, analogously to already existing push_front and
push_back methods.
The responsibility of these methods is to allocate memory for new object and
construct it using the function provided.

The first addition is just a generic support for the push_xxx_function
methods and can be used on their own for other purposes.

Having the push_xxx_functions in Standard sequences, it is easy to avoid
unneeded temporary when new object is created from another one of different
type, no matter what constructor is involved (the biggest problem discussed
on clc++m was the variety of constructors that can be used - here, the
construction is encapsulated in the callback function, where the programmer
has complete control over the construction process).

Impact on the existing code:
None. This extension does not use any old name in the Standard library.

As a feasibility proof, please find here:

http://www.maciejsobczak.com/_temp/cpp/

the already changed files for MSVC++ 6.0 and MSVC++ 7.0 compilers (only
push_back_function for vector is provided as an example - this case was
discussed on clc++m). I have tried to keep the changes as minimal as
possible and they are carefuly documented. The test program showing that the
temporary is really avoided is also provided.

I would like to know your opinions.

Best regards,

--
Maciej Sobczak
http://www.maciejsobczak.com/



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]