Topic: When and where must containers use allocators?


Author: markus.mauhart@nospamm.chello.at ("Markus Mauhart")
Date: Thu, 26 Jun 2003 02:19:29 +0000 (UTC)
Raw View
//this msg seems to have vanished during its 1st transport

"Dhruv" <dhruvbird@gmx.net> wrote ...
>
> > What i did was
> > alloc<node> an = ..
> > alloc<value> av = ..
> >
> > alloc<node>::pointer pn = an.allocate(1);
> > alloc<value>::construct(&pn->value);
>
> Is construct a static member?

this is not required, but I think the above was only a scetch

---
[ 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                       ]





Author: markus.mauhart@nospamm.chello.at ("Markus Mauhart")
Date: Fri, 27 Jun 2003 17:53:41 +0000 (UTC)
Raw View
Sorry for the delayed answer, Hans !

""Hans Bos"" <hans.bos@xelion.nl> wrote ...
>
> What i did was
> alloc<node> an = ..
> alloc<value> av = ..
>
> alloc<node>::pointer pn = an.allocate(1);
> alloc<value>::construct(&pn->value);
>
> I think the undefined behaviour is taking the address of pn->value.
> Although, according to 20.1.4 you can take the address of a
> CopyConstructable object, I don't think that is true if the operator& is
> overloaded for value and the value is not yet constructed.
>
> This has nothing to do with using construct or new.
> Visual C++ 6.0 uses
>     construct(&(*pn).value, v)
>
> And C++ builder 6.0 (stlport) uses:
>     new (&pn->value)(v)
>
> So both implementation have the same undefined behaviour if operator& is
> overloaded, since the object is not yet constructed.

IMO taking the address is not the problem, but using this address as
argument for construct ... the 2 tables of the allocator requirements
say IMO undoubtly that [(value-construct's argument must have type
value-pointer) && (it must be the result of a previous value-allocate()
using an 'equivalent' value-allocator object)]. I think only magic
or a significant change in the standard could yield this conversion.

> I don't know if using alloc<value>::address helps here, since it still
> operates on nonconstructed types.
>
> The solution to this is simple:
> struct node
> {
>         value_type value;
>
>         node *next;
>         ..
>
>         node(const value_type &v): value(v) { ... }
> };
>
> Now you can call the constructor with:
>     allocator<node>::construct(pn, node(value));
>
> I am not sure if all the extra constructors can be optimized away.

I think you are right, this IS a method to use node-construct()
for a logically uncopyable node-class.
But were is now value-construct .. is a c++-impl allowed to omit it ?-)

> But there is a difference in wat we want and wat the standard says.
> If we don't want containers to use the construct member, we should
> say so in the standard.
>
> And then there is no need to require the construct and destroy members
> in allocators.

IMO it's a very uncomfortable situation. 99% of all c++lib users dont
know and care about their container's allocators, about construct/destroy
and the not-global 'new' inside construct. The next 0.9% find this three
magic & apparently obvious hooks into containers (construct/destroy) and
maybe into allocators (not-global 'new') and say wow, how sophisticated!,
and forget it (allthough not-global 'new' IMHO is most likely detected
via an unexpected compiler error msg). The rest 0.1% who then really wants
to support this 'obvious features' in their containers and allocators,
design & implementation, then either fights a lost battle again missing
specifications, unknown intentions, undefined behaviour of lots of
conversions inside c++-lib implementations, or one decides to make use
of the one really usefull and concrete information we have about
construct/destroy ... namely that no container-implementation nor any
other allocator client is required to enter this Potemkin interface ;-)


Regards,
Markus

---
[ 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                       ]





Author: markus.mauhart@nospamm.chello.at ("Markus Mauhart")
Date: Fri, 27 Jun 2003 17:53:52 +0000 (UTC)
Raw View
"Dhruv" <dhruvbird@gmx.net> wrote ...
>
> > What i did was
> > alloc<node> an = ..
> > alloc<value> av = ..
> >
> > alloc<node>::pointer pn = an.allocate(1);
> > alloc<value>::construct(&pn->value);
>
> Is construct a static member?

this is not required, but I think the above was only a scetch

---
[ 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                       ]





Author: hans.bos@xelion.nl ("Hans Bos")
Date: Sat, 14 Jun 2003 19:43:35 +0000 (UTC)
Raw View
""Markus Mauhart"" <markus.mauhart@nospamm.chello.at> wrote in message
news:62kFa.130813$lL2.1213483@news.chello.at...
> ""Hans Bos"" <hans.bos@xelion.nl> wrote in ...
> > [...]
...
> Taking only your arguments, IMHO your conclusion is valid, and adding
> a bit explanation to C++0x seems enough to make this intent clear.
> But IMO you forgot to consider some vital parts, especially
> your list sample IMO results in undefined behaviour:
>
> > I implemented some containers  and following the standard I used
construct
> > an destroy for construction/destruction.
> > For list you have a node type like:
> > struct node
> > {
> >         value_type value;
> >
> >         node *next;
> >         ...
> > };
> >
> > No you can construct the value with allocator construct by using
&n.value.
>
> (why have you put 'value' on top ? has this to do with 20.1.5 ?)
>
> IMO you violated 20.1.5. Let me try a sketch of your list-code:

What i did was
alloc<node> an = ..
alloc<value> av = ..

alloc<node>::pointer pn = an.allocate(1);
alloc<value>::construct(&pn->value);

I think the undefined behaviour is taking the address of pn->value.
Although, according to 20.1.4 you can take the address of a
CopyConstructable object, I don't think that is true if the operator& is
overloaded for value and the value is not yet constructed.

This has nothing to do with using construct or new.
Visual C++ 6.0 uses
    construct(&(*pn).value, v)

And C++ builder 6.0 (stlport) uses:
    new (&pn->value)(v)

So both implementation have the same undefined behaviour if operator& is
overloaded, since the object is not yet constructed.
I don't know if using alloc<value>::address helps here, since it still
operates on nonconstructed types.

The solution to this is simple:
struct node
{
        value_type value;

        node *next;
        ..

        node(const value_type &v): value(v) { ... }
};

Now you can call the constructor with:
    allocator<node>::construct(pn, node(value));

I am not sure if all the extra constructors can be optimized away.

>
> Cause of this additional arguments AFAICS your interpretation
> and conclusion costs much more troubles than the c++ committee
> and the users probably want to pay for this conclusion's little
> gain: any_alloc::construct/destroy may have additional side
> effects specific to each any_alloc-type/object.

I totally agree with you. But there is a difference in wat we want and wat
the standard says.
If we don't want containers to use the construct member, we should say so in
the standard.

And then there is no need to require the construct and destroy members in
allocators.

Greetings,
Hans.

---
[ 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                       ]





Author: dhruvbird@gmx.net (Dhruv)
Date: Mon, 16 Jun 2003 19:37:17 +0000 (UTC)
Raw View
hans.bos@xelion.nl ("Hans Bos") wrote in message news:<3eeb0a9b$0$49107$e4fe514c@news.xs4all.nl>...
> ""Markus Mauhart"" <markus.mauhart@nospamm.chello.at> wrote in message
> news:62kFa.130813$lL2.1213483@news.chello.at...
> > ""Hans Bos"" <hans.bos@xelion.nl> wrote in ...
> > > [...]
>  ...

> What i did was
> alloc<node> an = ..
> alloc<value> av = ..
>
> alloc<node>::pointer pn = an.allocate(1);
> alloc<value>::construct(&pn->value);

Is construct a static member?

>
> I think the undefined behaviour is taking the address of pn->value.
> Although, according to 20.1.4 you can take the address of a
> CopyConstructable object, I don't think that is true if the operator& is
> overloaded for value and the value is not yet constructed.
>
> This has nothing to do with using construct or new.
> Visual C++ 6.0 uses
>     construct(&(*pn).value, v)
>
> And C++ builder 6.0 (stlport) uses:
>     new (&pn->value)(v)
>
> So both implementation have the same undefined behaviour if operator& is
> overloaded, since the object is not yet constructed.
> I don't know if using alloc<value>::address helps here, since it still
> operates on nonconstructed types.
>
> The solution to this is simple:
> struct node
> {
>         value_type value;
>
>         node *next;
>         ..
>
>         node(const value_type &v): value(v) { ... }
> };
>
> Now you can call the constructor with:
>     allocator<node>::construct(pn, node(value));
>
> I am not sure if all the extra constructors can be optimized away.
>
> >
> > Cause of this additional arguments AFAICS your interpretation
> > and conclusion costs much more troubles than the c++ committee
> > and the users probably want to pay for this conclusion's little
> > gain: any_alloc::construct/destroy may have additional side
> > effects specific to each any_alloc-type/object.
>
> I totally agree with you. But there is a difference in wat we want and wat
> the standard says.
> If we don't want containers to use the construct member, we should say so in
> the standard.
>
> And then there is no need to require the construct and destroy members in
> allocators.
>
> Greetings,
> Hans.
>
> ---
> [ 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                       ]

---
[ 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                       ]





Author: bop2@telia.com ("Bo Persson")
Date: Mon, 16 Jun 2003 19:39:10 +0000 (UTC)
Raw View
""Hans Bos"" <hans.bos@xelion.nl> skrev i meddelandet
news:3eeb0a9b$0$49107$e4fe514c@news.xs4all.nl...
> ""Markus Mauhart"" <markus.mauhart@nospamm.chello.at> wrote in
message
> news:62kFa.130813$lL2.1213483@news.chello.at...
> > ""Hans Bos"" <hans.bos@xelion.nl> wrote in ...
> > > [...]
> ...
> > Taking only your arguments, IMHO your conclusion is valid, and
adding
> > a bit explanation to C++0x seems enough to make this intent clear.
> > But IMO you forgot to consider some vital parts, especially
> > your list sample IMO results in undefined behaviour:
> >
> > > I implemented some containers  and following the standard I used
> construct
> > > an destroy for construction/destruction.
> > > For list you have a node type like:
> > > struct node
> > > {
> > >         value_type value;
> > >
> > >         node *next;
> > >         ...
> > > };
> > >
> > > No you can construct the value with allocator construct by using
> &n.value.
> >
> > (why have you put 'value' on top ? has this to do with 20.1.5 ?)
> >
> > IMO you violated 20.1.5. Let me try a sketch of your list-code:
>
> What i did was
> alloc<node> an = ..
> alloc<value> av = ..
>
> alloc<node>::pointer pn = an.allocate(1);
> alloc<value>::construct(&pn->value);
>
> I think the undefined behaviour is taking the address of pn->value.
> Although, according to 20.1.4 you can take the address of a
> CopyConstructable object, I don't think that is true if the
operator& is
> overloaded for value and the value is not yet constructed.
>
> This has nothing to do with using construct or new.
> Visual C++ 6.0 uses
>     construct(&(*pn).value, v)
>
> And C++ builder 6.0 (stlport) uses:
>     new (&pn->value)(v)
>
> So both implementation have the same undefined behaviour if
operator& is
> overloaded, since the object is not yet constructed.

I believe the implementors are under the impression that 20.1.3 (Table
30) says that you *cannot* overload operator&() for CopyConstructible
types. The operator is required to return a T* that "denotes the
address of t". Doesn't leave much room, does it?


Bo Persson
bop2@telia.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                       ]





Author: markus.mauhart@nospamm.chello.at ("Markus Mauhart")
Date: Mon, 9 Jun 2003 01:37:28 +0000 (UTC)
Raw View
""Hans Bos"" <hans.bos@xelion.nl> wrote in message news:3ee05719$0$49103$e4fe514c@news.xs4all.nl...
>
> ""Markus Mauhart"" <markus.mauhart@nospamm.chello.at> wrote in message
> news:heIDa.32314$lL2.326963@news.chello.at...
> > "John Madsen" <johnmadsen_usenet@hotmail.com> wrote ...
> > >
> > > I'm wondering about what the standard says about when std containers
> > > must use the facilities provided by the allocators associated with
> > > them.  As far as I can tell, the only place in the standard where it
> > > actually says that a container must call member functions of the
> > > supplied allocator is in 23.1/8:
> > >
> > > "A copy of this argument [the allocator passed to a ctor] is used for
> > > any memory allocation performed, by these constructors and by all
> > > member functions, during the lifetime of each container object."
> > >
> > > In particular this does not seem to require that the container use the
> > > construct() and destroy() members to create and destroy instances of
> > > the contained type.  Is this correct?
> >
> > Yes, this is correct for the container requirements (23.1).
> > And also the general allocator requirements (20.1.5, 20.4.1) neither
> > require the usage of construct(p,t)/destroy(p) nor do they explain the
> > benefits of using construct()/destroy() (e.g. when compared with the
> > more WYSIWYG "(*&p).~T::T() and ::new((void*)&*p) T(args)").
> > But not only is construct() redundant, it is also not sufficient, cause
> > it doesnt (and cant) support types without copy-constructor.
> >
>
> But wat does "performing memory allocation" mean?

In the c++ language this is what typically happens in the 1st phase of a
new-expression, allthough malloc() does it too, but we can call any "allocation
function" (3.7.3.1) manually whenever we like.
W.r.t. the library, 20.1.5 & 20.4.1, table 32 is quite clear:
"a.allocate(n) a.allocate(n,u) ... Memory is allocated for n objects of type T
 but objects are not constructed."
Especially: memory allocation != object construction


> Following your reasoning, a container is not required to deallocate memory
> using the allocator (perhaps this is a defect).

No. a.deallocate() & a.allocate() are not portably redundant, especially nobody
claimes that the empty expression "" is equivalent to "a.deallocate(p)".
If you want to take&release memory from a conforming allocator in a portable
way, then a.deallocate() & a.allocate() is the only known way to achieve this
desired erffect.
OTOH in c++ there are traditionally many ways to use available memory,
including construct(p), ::new((void*)&*p) and memcopy(&*p,...).

> Since it is required to define a construct and destroy member in an
> allocator,

Not only "a construct and destroy member", but IMO exactly with
the specified effect -> a certain new expression.

> I expect that containers use them  to construct and destruct objects.

I understand that you originally got this impression (as it happened to
me and the other few % of c++ users that ever mentioned the existence of
contruct/destroy), because normaly the c++-library describes either
necessary or very usefull interfaces.
But nobody is perfect, and construct()/destroy() as specified now are
neither necessary nor very usefull.
And currently the standard doesnt require the standard library nor any
other allocator-client-code to use construct/destroy to create objects
inside memory provided by the allocator.

> All elements in a container are created by copy construction anyway,

Obviously you mean the value_type of a container defined in the
stdc++-library.

> so you lose nothing by using the allocator construct member.

Surely we all would loose:

1) Every implementation of std::list<T> and std::set<T> probably consists
of nodes that are logically uncopyable, despite T being copyable.
Even when no c++-lib-implementation makes efforts to technically make this
nodes un-copyable and un-cpy-assignable (to express this design inherent
logic), neither do they define copy-ctor/op= nor do they use them
- e.g. Dinkumware/VC7's std::set<> compiles & builds cleanly when its
"struct _Node" gets added private and not implemented copy-ctor/op=.
So we can learn that most c++-lib-implementations (have to) use
"p = alloc<NODE>::[de]allocate()" without using a single
"alloc<NODE>::construct(p,othernode)".
IMO you have never used a c++-implementation which creates list/set/map-
nodes by calling alloc<node>::construct().

2) std::string<char,any_alloc<>> is allowed to contruct & use T-values
not allocated (nor construct()ed) via its internal get_allocator().
The same is probably true for other stdc++-lib-containers.

3) stdc++-allocators are very usefull to implement any kind of
userdefined container-class/type C<T>, where the restriction of T being
CopyConstructible is not necessary; this then is a feature of this
userdefined container design.

4) stdc++-conforming allocators may be used outside the scope of any
[stdc++-]container. E.g. a straightforeward usage pattern of statfull
c++-allocators is to use them for storing all kind of client state:
stdc++-containers, other containers, objects of other type.

The 1st paragraph of [lib.allocator.requirements] 20.1.5 IMHO gives a
valid description of the range & intent of c++-allocators:

 "The library describes a standard set of requirements for allocators, which
  are objects that encapsulate the information about an allocation model.
  This information includes the knowledge of pointer types, the type of their
  difference, the type of the size of objects in this allocation model,
  as well as the memory allocation and deallocation primitives for it.
  All of the containers (clause 23) are parameterized in terms of allocators."

Note "allocation model", not "construction model", nor any kind of
"object factory" mentioned. And not bound to the containers defined
in the stdc++-library.

> Perhaps this is a quality of implementation feature (where high quality
> implementations use the construct and destroy members provided by the
> allocator).

Have you ever observed unexpected behaviour or symptoms of low QOI when
your c++-library allocate()ed but didnt construct() container-nodes ?


But back to the OP's question:

Do you think that Dinkumware's STL or other libraries have a defect when
their list/set/map doesnt use "alloc<node>::construct(ptr_node,other_node)"
or "alloc<value>::contruct(ptr_t,other_t)" ? What would be the observable
behaviour of this defect ?

Or is the standard defect in this context ?

IMO the answers are no & no, and I've tried to explain my opinion.

Your answers are ... ?
For any "yes", maybe an explanation and a constructive suggestion
how to fix it ?


Regards,
Markus.


---
[ 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                       ]





Author: hans.bos@xelion.nl ("Hans Bos")
Date: Mon, 9 Jun 2003 19:41:44 +0000 (UTC)
Raw View
""Markus Mauhart"" <markus.mauhart@nospamm.chello.at> wrote in message
news:RxHEa.90359$lL2.870323@news.chello.at...
> ""Hans Bos"" <hans.bos@xelion.nl> wrote in message news:3ee05719$0$49103>
> But wat does "performing memory allocation" mean?
>
> In the c++ language this is what typically happens in the 1st phase of a
> new-expression, allthough malloc() does it too, but we can call any
"allocation
> function" (3.7.3.1) manually whenever we like.
> W.r.t. the library, 20.1.5 & 20.4.1, table 32 is quite clear:
> "a.allocate(n) a.allocate(n,u) ... Memory is allocated for n objects of
type T
>  but objects are not constructed."
> Especially: memory allocation != object construction
>
>
> > Following your reasoning, a container is not required to deallocate
memory
> > using the allocator (perhaps this is a defect).
>

What I meant was, how is "memory allocation" defined in the C++ standard.
In 3.2.3:
    "... allocation function for placement new (5.3.4)"

So here placement new is considered allocation.

In 3.7.3:
    "... via the global allocation functions operator new and operator new[]
and the
global deallocation functions operator delete and operator delete[]."

Here allocation and deallaction are two different concepts (see also 3.7.3.1
"allocation functions" and 3.7.3.2 "deallocation functions").

In 17.4.3.4/2:
"...of eight dynamic memory allocation function signatures ...
This includes operator delete, which is considered a memory allocation
function here."

In 20.1.5/1 Allocator requirements:

"The library describes a standard set of requirements for allocators, which
are objects that encapsulate the information about an allocation model. This
information includes the knowledge of pointer types, the type of their
difference, the type of the size of objects in this allocation model, as
well as the memory allocation and deallocation primitives for it."

Here construction and destruction are not mentioned explicitly. So they must
fall under the memory and dealloction primitives.

So what I meant is that the standard is not very clear on the meaning of
memory allocation.
And with respect to containers ("containers are required to use the
allocator for memory allocation") you can take a narrow view (deallocation
is not allocation) or a wider view (as in 3.2.3 and 20.1.5/1). In the latter
view constuction and destruction are also taken as memory allocation
functions.

In any way, it is not very clear how a container should behave with respect
to allocators.

> No. a.deallocate() & a.allocate() are not portably redundant, especially
nobody
> claimes that the empty expression "" is equivalent to "a.deallocate(p)".
> If you want to take&release memory from a conforming allocator in a
portable
> way, then a.deallocate() & a.allocate() is the only known way to achieve
this
> desired erffect.
> OTOH in c++ there are traditionally many ways to use available memory,
> including construct(p), ::new((void*)&*p) and memcopy(&*p,...).
>
> > Since it is required to define a construct and destroy member in an
> > allocator,
>
> Not only "a construct and destroy member", but IMO exactly with
> the specified effect -> a certain new expression.

It is clear that the construct function must have the same effect as using
the placement new expression, but that does not mean it has to call
placement new. Calling construct may also have other side effects (e.g.
counting the number of calls).

>
> > I expect that containers use them  to construct and destruct objects.
>
> I understand that you originally got this impression (as it happened to
> me and the other few % of c++ users that ever mentioned the existence of
> contruct/destroy), because normaly the c++-library describes either
> necessary or very usefull interfaces.
> But nobody is perfect, and construct()/destroy() as specified now are
> neither necessary nor very usefull.
> And currently the standard doesnt require the standard library nor any
> other allocator-client-code to use construct/destroy to create objects
> inside memory provided by the allocator.
>
> > All elements in a container are created by copy construction anyway,
>
> Obviously you mean the value_type of a container defined in the
> stdc++-library.
>
> > so you lose nothing by using the allocator construct member.
>
> Surely we all would loose:
>
> 1) Every implementation of std::list<T> and std::set<T> probably consists
> of nodes that are logically uncopyable, despite T being copyable.
> Even when no c++-lib-implementation makes efforts to technically make this
> nodes un-copyable and un-cpy-assignable (to express this design inherent
> logic), neither do they define copy-ctor/op= nor do they use them
> - e.g. Dinkumware/VC7's std::set<> compiles & builds cleanly when its
> "struct _Node" gets added private and not implemented copy-ctor/op=.

For containers, the value type is required to be CopyConstructable (and it
is not required to be DefaultConstructable).
So it is a non standard extension to allow types that cannot be copied.

However, if an implementation can deduce that a type cannot be copied and
doesn't use alloctors for the construction, it is fine by me.

Note that the list::size function (the only way the initialize list element
without providing an initializer) has a second argument that is copied into
the newly created nodes. (although it is allowed to have to separate
overloads for size, I think the default constructor can only be called once
when several nodes are created).

> So we can learn that most c++-lib-implementations (have to) use
> "p = alloc<NODE>::[de]allocate()" without using a single
> "alloc<NODE>::construct(p,othernode)".
> IMO you have never used a c++-implementation which creates list/set/map-
> nodes by calling alloc<node>::construct().

I implemented some containers  and following the standard I used construct
an destroy for construction/destruction.
For list you have a node type like:
struct node
{
        value_type value;

        node *next;
        ...
};

No you can construct the value with allocator construct by using &n.value.
The other members can be constructed in some other way (e.g. explicitly
initializing).
So it is possible to implement a list that is using allocator.construct to
construct the values.

And yes, I have used them as well :-)


> 2) std::string<char,any_alloc<>> is allowed to contruct & use T-values
> not allocated (nor construct()ed) via its internal get_allocator().
> The same is probably true for other stdc++-lib-containers.

std::string is not a container. The value type must be a POD so contruction
is not an issue.
If you look closely to std::string, you will see that every element in the
string is explicitly inititialized by the char_traits::assign or
char_traits::move function.

>
> 3) stdc++-allocators are very usefull to implement any kind of
> userdefined container-class/type C<T>, where the restriction of T being
> CopyConstructible is not necessary; this then is a feature of this
> userdefined container design.

Of course I can do whatever I want in my own containers, but standard
containers should follow the standard.
I can also require that the alloctors to my container have an extra
construct function to default construct values.

...

> The 1st paragraph of [lib.allocator.requirements] 20.1.5 IMHO gives a
> valid description of the range & intent of c++-allocators:
>
>  "The library describes a standard set of requirements for allocators,
which
>   are objects that encapsulate the information about an allocation model.
>   This information includes the knowledge of pointer types, the type of
their
>   difference, the type of the size of objects in this allocation model,
>   as well as the memory allocation and deallocation primitives for it.
>   All of the containers (clause 23) are parameterized in terms of
allocators."
>
> Note "allocation model", not "construction model", nor any kind of
> "object factory" mentioned. And not bound to the containers defined
> in the stdc++-library.

But what are the categories for the construct and destroy member (knowledge
of pointer types?).
Since here the purpose of allocators are described and the construct and
destroy members are not explicitly mentioned here, I take it that memory
allocation and deallocation primitives include construct and destruct.

>
> > Perhaps this is a quality of implementation feature (where high quality
> > implementations use the construct and destroy members provided by the
> > allocator).
>
> Have you ever observed unexpected behaviour or symptoms of low QOI when
> your c++-library allocate()ed but didnt construct() container-nodes ?
>

If the construct and destroy function have some other side effects (as
counting the number of calls) then there is a difference in calling constuct
or construction the value with placement new.

Greetings,
Hans.

---
[ 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                       ]





Author: markus.mauhart@nospamm.chello.at ("Markus Mauhart")
Date: Wed, 11 Jun 2003 19:10:13 +0000 (UTC)
Raw View
""Hans Bos"" <hans.bos@xelion.nl> wrote in ...
> [...]

this explanation helped a lot.
If necessary correct my summary of it:

  W.r.t. construct/destroy the standard is not clear enough.
  But considering many valid aspects you came to the conclusion that
  containers of std-library implementations ("std-containers") have
  to construct all their contained values using "alloc<value_type>
  ::construct(..)" if value_type is not a POD and if the underlying
  memory came from any 'allocation', and that this is possible
  (-> your list sample).
  You did not need nor want to decide in what situations other
  T-allocate()ed 'T-typed memory' must be initialized with
  T-construct(..) before using it, especially you know that only
  one of "construct(&node.value)" and "construct(&node)" is possible.
  Completly open is the question what allocator clients that are
  not std-containers are expected to do w.r.t. construct().

Taking only your arguments, IMHO your conclusion is valid, and adding
a bit explanation to C++0x seems enough to make this intent clear.
But IMO you forgot to consider some vital parts, especially
your list sample IMO results in undefined behaviour:

> I implemented some containers  and following the standard I used construct
> an destroy for construction/destruction.
> For list you have a node type like:
> struct node
> {
>         value_type value;
>
>         node *next;
>         ...
> };
>
> No you can construct the value with allocator construct by using &n.value.

(why have you put 'value' on top ? has this to do with 20.1.5 ?)

IMO you violated 20.1.5. Let me try a sketch of your list-code:

alloc<node>  an = ...
alloc<value> av = ...

alloc<node> ::pointer pn = an.allocate(1);

alloc<value>::pointer pv = ???

av.construct (pv);//<-- some people think that this call is mandatory
                  //for each element in any stdc++-library container.

But how got you pv from pn ? Table31 tells us that pv must be
obtained by some call to "av.allocate(...)".
Let me interpret/relax this requirenment: PV is a ra-iterator,
hence 'obtained' shall also include iterator-arithmetic, like ...
    pv = av.allocate(20);
    for (PV p=pv ;p!=pv+20 ;++p) av.construct(p,t);

My guess is that you did one of ...

pv = (PV) pn;
  //an undefined cast between ra-iterators of different type.
pv = av.address (&(pn->value));
  //1) the argument "(&(pn->value)" is invalid for av.address(..)
  //2) the result is invalid for av.construct(..)

So at this point we know that, according to 20.1.5 as it is, we never
may use the memory just allocated for the *node* to construct() the
single *value* inside it.
Otherwise, if the standard really intended mandatory calls to
alloc<V>.construct(pv,t) for each element of every std-container<V>,
then there is a lot to correct & add in 20.1.5, especially AFAICS
this would involve some non-trivial additional requirements for
the type of alloc::pointer.
Is there somebody having a concrete suggestion how to fix the wording
to make this work, at least for the simple case with pointer == T* ?
How long will it take until libraries conform to this "must-construct()"
rule ?

Btw, it's not only your list-sample; last time I looked also widely
used library implementations contained a lot of such conversions and/or
function calls not backed up by the standard. I came on this not cause
of searching for it, but cause of compiler error messages for non-trivial
'pointer'-types.


Cause of this additional arguments AFAICS your interpretation
and conclusion costs much more troubles than the c++ committee
and the users probably want to pay for this conclusion's little
gain: any_alloc::construct/destroy may have additional side
effects specific to each any_alloc-type/object.


So to repeate the open questions:

1) For memory allocated with a c++-allocator, may construct() have
   other (-> allocator-specific) effects (-> side effects) than the
   effect explicitely described in c++98 (== table 32) ?

2) For memory allocated with a c++-allocator, who must when call
   construct() ? (table32: "a.construct(p,t) (not used)" ;-)

3) Must every element of a std-container live in memory allocated
   with its c++-allocator ? Should we even require that it is
   accessible with an alloc<value>::pointer ? Was this the reason
   for the invention of container::pointer ? And what about elements
   in strings, and string::pointer (== allocator_type::pointer) ?

If (1) is no, then (2)'s answer is irrelevant, and we would have
spared lots of time.
If (1) is yes, then the necessarily detailed answer for (2)
not only must tell who shall call construct() when, but also
make this possible for list- and tree-nodes.


Regards,
Markus.

---
[ 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                       ]





Author: markus.mauhart@nospamm.chello.at ("Markus Mauhart")
Date: Thu, 5 Jun 2003 18:01:42 +0000 (UTC)
Raw View
"John Madsen" <johnmadsen_usenet@hotmail.com> wrote ...
>
> I'm wondering about what the standard says about when std containers
> must use the facilities provided by the allocators associated with
> them.  As far as I can tell, the only place in the standard where it
> actually says that a container must call member functions of the
> supplied allocator is in 23.1/8:
>
> "A copy of this argument [the allocator passed to a ctor] is used for
> any memory allocation performed, by these constructors and by all
> member functions, during the lifetime of each container object."
>
> In particular this does not seem to require that the container use the
> construct() and destroy() members to create and destroy instances of
> the contained type.  Is this correct?

Yes, this is correct for the container requirements (23.1).
And also the general allocator requirements (20.1.5, 20.4.1) neither
require the usage of construct(p,t)/destroy(p) nor do they explain the
benefits of using construct()/destroy() (e.g. when compared with the
more WYSIWYG "(*&p).~T::T() and ::new((void*)&*p) T(args)").
But not only is construct() redundant, it is also not sufficient, cause
it doesnt (and cant) support types without copy-constructor.

My guess is that either some c++draft author once had more (or less:-)
clear ideas about what additional functionality contruct()/destroy()
could provide but then that ideas never found their way into c++98.
Or that construct()/destroy() originally were implementation details
of early container/allocator library implementers (e.g. take a look
at Dinkumware's library which IIRC internally contains a lot of
"construct"/"CONSTRUCT" mini-functions/macros) which then by chance
or via copy&paste found their way into c++98 as official public
interface.

IMO the cleanest solution would be to deprecate usage of construct/destroy
immediatly, and probably then to remove them from both the general allocator
requirements (20.1.5) and from std::allocator's description (20.4.1).

> Dinkumware's STL (as
> distributed in VC++ 7.1), for example, does not use construct() to
> create copies of the elements contained in their std::list (and
> possibly other containers -- I haven't checked).  Rather, they use
> placement new with memory returned by the allocator's allocate().  Is
> this conforming behavior?  If it is, ought it to be?

IMO it is conforming as long as placement new's argument points to
suitably aligned and sized and otherwise unused memory.
This is as cristal clear as anything else we know about c++ "objects",
values and memory.


Regards,
Markus.

---
[ 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                       ]





Author: hans.bos@xelion.nl ("Hans Bos")
Date: Fri, 6 Jun 2003 21:05:49 +0000 (UTC)
Raw View
""Markus Mauhart"" <markus.mauhart@nospamm.chello.at> wrote in message
news:heIDa.32314$lL2.326963@news.chello.at...
> "John Madsen" <johnmadsen_usenet@hotmail.com> wrote ...
> >
> > I'm wondering about what the standard says about when std containers
> > must use the facilities provided by the allocators associated with
> > them.  As far as I can tell, the only place in the standard where it
> > actually says that a container must call member functions of the
> > supplied allocator is in 23.1/8:
> >
> > "A copy of this argument [the allocator passed to a ctor] is used for
> > any memory allocation performed, by these constructors and by all
> > member functions, during the lifetime of each container object."
> >
> > In particular this does not seem to require that the container use the
> > construct() and destroy() members to create and destroy instances of
> > the contained type.  Is this correct?
>
> Yes, this is correct for the container requirements (23.1).
> And also the general allocator requirements (20.1.5, 20.4.1) neither
> require the usage of construct(p,t)/destroy(p) nor do they explain the
> benefits of using construct()/destroy() (e.g. when compared with the
> more WYSIWYG "(*&p).~T::T() and ::new((void*)&*p) T(args)").
> But not only is construct() redundant, it is also not sufficient, cause
> it doesnt (and cant) support types without copy-constructor.
>

But wat does "performing memory allocation" mean?
Following your reasoning, a container is not required to deallocate memory
using the allocator (perhaps this is a defect).

Since it is required to define a construct and destroy member in an
allocator, I expect that containers use them  to construct and destruct
objects.
All elements in a container are created by copy construction anyway, so you
lose nothing by using the allocator construct member.

Perhaps this is a quality of implementation feature (where high quality
implementations use the construct and destroy members provided by the
allocator).

Greetings,
Hans.

---
[ 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                       ]





Author: johnmadsen_usenet@hotmail.com (John Madsen)
Date: Sun, 25 May 2003 14:18:39 +0000 (UTC)
Raw View
I'm wondering about what the standard says about when std containers
must use the facilities provided by the allocators associated with
them.  As far as I can tell, the only place in the standard where it
actually says that a container must call member functions of the
supplied allocator is in 23.1/8:

"A copy of this argument [the allocator passed to a ctor] is used for
any memory allocation performed, by these constructors and by all
member functions, during the lifetime of each container object."

In particular this does not seem to require that the container use the
construct() and destroy() members to create and destroy instances of
the contained type.  Is this correct?  Dinkumware's STL (as
distributed in VC++ 7.1), for example, does not use construct() to
create copies of the elements contained in their std::list (and
possibly other containers -- I haven't checked).  Rather, they use
placement new with memory returned by the allocator's allocate().  Is
this conforming behavior?  If it is, ought it to be?

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                       ]