In article <323C6D6D.DB3@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|> James Kanze US/ESC 60/3/141 #40763 wrote:

    [I've deleted most of the original posting.  We are getting down to
 the "yes, it is, no , it isn't" level, I think we'll just have to
 agree to disagree.]

|> > I'm not implying anything.  I am saying that implementors who want to
|> > sell compilers will do what the customer wants.  If the customer doesn't
|> > want the overhead of comparing allocators in the normal case, the
|> > implementor will provide a specialization of the class which exploits
|> > the knowledge that all instances of the standard allocator compare
|> > equal.
|> >

|> Sorry, but you are implying that only compilers that can do unused
|> code elimination are to be considered candidates for general use.  I
|> can think of environments where any kind of optimization would actually
|> be detrimental.  (Specifically, student batch compile and run systems.
|> Old fashoned and morubund, but still a valid example.)

I do want to answer this point, since it seems that you have not
understood my technical point.  There is no need for any optimization in
the compiler itself.  The implementation of the library should use
partial specialization to provide a distinct implementation of the
container for the case of the default allocator.  If this is done, the
compiler never sees the extra code which you seem to want it to
eliminate.
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone



[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <322DDBE8.40DC@cds.duke.edu> Max TenEyck Woodbury
> <mtew@cds.duke.edu> writes:
>
> |> As a guess, passing an allocator INSTANCE to the string CONSTRUCTOR may be
> |> a serious mistake.  It makes what should be a compact and efficent object
> |> that will be used over and over again into something necessarily larger and
> |> less efficent.  I'd bet that there will be more than one alternate
> |> implementation (abet non-standard) that either ignores allocators or
> |> uses a similar implementation to containers to achieve the same end.
>
> At most, it only adds one pointer.  For a container, this doesn't seem
> like much to me.

If you allow the 'it only adds one pointer' argument, you eventually end
up with something like LISP; fine for what it does, but not for most
practical applications.

> As I have pointed out before, the default allocator guarantees that all
> instances compare equal.  So the implementation can implement a
> partitial specialization on this which simply ignores the allocator
> parameter.

You're implying a standard for the quality of implimentation here, and
not necessarialy the best one.  A good optimizer, while it would trim
the unused code, might very well provide a low level diagnostic, which
could cause untold grief in the wrong techno/political environment.

> If this really becomes an issue in user defined allocators, then the
> compiler could always recognize the special case of operator== on the
> allocator type always returning null, and optimize the pointer out.
> (Implementors: don't put this high on your priority list.  IMHO, it will
> never become an issue.  In the rare cases where performance is an issue,
> I imagine that a user designed class tuned to the application, rather
> than the general library class, will be used.  In this case, whether
> there is a user defined allocator or not is indifferent.)

Argh!!!!!

mtew@cds.duke.edu


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

James Kanze US/ESC 60/3/141 #40763 wrote:
>
> In article <3221F075.60D5@cds.duke.edu> Max TenEyck Woodbury
> <mtew@cds.duke.edu> writes:
>
> |> James Kanze US/ESC 60/3/141 #40763 wrote:
> |> > ...
> |> >
> |> > This problem is not unique to lists, but also affects any objects which
> |> > may want to use a shared representation.  I first encountered it when
> |> > trying to implement a reference counted string class.
> |> >
>
> |> I believe the argument in the original post is incorrect.
>
> |> I've seen your comments on strings before and I am still not sure why
> |> there is a problem, or if there is a problem, why it makes reference
> |> count strings a special problems.
>
> |> To be more specific, I don't see anyplace in the standard where the
> |> deallocator is parameterized except through the base class template.
>
> The deallocator is a member function of the allocator object.  I don't
> know off hand how clear the working papers are, but the intent is
> obvious: all dynamic memory used by a given object must be allocated and
> deallocated by means of an allocator object from the same equivalence
> class as that specified in the constructor.
>
> |> From that it seems all deallocators have to handle whatever is thrown
> |> at them from any allocation source.
>
> In a way, yes.  Since anything that can be thrown at them must have been
> allocated by the same object:-).  The restriction doesn't involve the
> deallocator per se.  The restriction is that all memory in the object be
> allocated by the specified allocator.  At all times.
>
> An example of why this is important: consider a user defined allocator
> for shared memory.  The allocator *class* manages several pools of
> shared memory; each pool is shared with a different set of processes.
> Each equivalence class of the instances of this allocator class manages
> a separate pool.  (The operator== on the allocator class compares pool
> id's.)
>
> If I create a string using an instance which allocates in pool 1, it is
> because this string must be visible in the other processes which have
> access to pool 1.  (Presumably, I will also have taken precautions that
> the string itself is in pool 1 as well.)  If I assign a string to it
> whose memory was allocated from pool 2, I *must* make a deep copy.  The
> necessary processes cannot see the memory from pool 2.
>
> Note that the requirement here *is* that the memory be allocated from a
> specific instance of the allocator.  This is not a problem of
> deallocation, but of user defined specialization.
>
> Presumably, if I need this functionality, *all* of my strings will use
> the same allocator class, with e.g. the pool 0 being the special case of
> unshared memory.  If the implementation is clever, it will only do the
> deep copy when necessary; e.g.: when I assign a string from one pool to
> another.  In this case, the deep copy is necessary by definition, since
> the target processes have no access to the memory in the original string.

Ah, I see.  For strings, you can have several instances of an allocator
and you have to pass the particular instance to the constructor, where a
pointer to it should be saved for future reference.

However, the container classes are just enough different in design that
some of the problems with strings might be avoidable.  Specifically,
the allocator appears to be a template parameter, not a constructor
parameter and the allocators have to match for most container
operations to be compatible.

>
> |> If that is the case, a reference
> |> count implementation presents no more problem than any other.  I could
> |> be missing something though, and your help in pointing out what I missed
> |> would be appreciated.
>
> |> That doesn't mean I like the idea of the allocator being part of the
> |> constructor parameter list for strings, or any other type for that
> |> mater.  It should be a compile time specification, not a run time
> |> specification, UNLESS you can specify a virtual deallocator, and
> |> that has problems that shouldn't even have to be considered!  (Just
> |> to start, how do you know that the object being deallocated has a
> |> virtual deallocator? By the time you need to invoke the deallocator,
> |> you no longer have an object, just raw storage, so either everything
> |> has a virtual deallocator or nothing does.)
>
> I think that the way things are in the current draft actually works
> pretty well, although I will admit that it took me some time to
> understand the logic behind it.  (A good rationale would be a real help.
> It would also require a significant investment of manpower, I fear.)  I
> do wonder if it isn't going too far with regards to flexibility, but now
> that the work has been done, I don't see any reason to remove it.

As a guess, passing an allocator INSTANCE to the string CONSTRUCTOR may be
a serious mistake.  It makes what should be a compact and efficent object
that will be used over and over again into something necessarily larger and
less efficent.  I'd bet that there will be more than one alternate
implementation (abet non-standard) that either ignores allocators or
uses a similar implementation to containers to achieve the same end.

mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze US/ESC 60/3/141 #40763 wrote:

> Alternatively, they could require all allocators of the same type to
> compare equal.  Operations with allocators that don't compare equal
> require a deep copy anyway, and probably aren't that common.  All of
> the containers have a constructor which takes two iterators, so there
> is no problem for the user to copy construct a container using one type
> of allocator with the contents of a container using another type of
> allocator.

I don't like this ... perhaps I have an allocator which, if it is in a
database, allocates data in the same database.  If it is in heap, it
allocates transient data.

The behavior I'd like to see would be as follows:

If the two lists are in the same place ( both in core, both in the same
database ) then shallow copy.

Else deep copy.

This can be implemented ( using objectstore ) like this:

bool operator == ( const Allocator &lhs, const Allocator &rhs )
 {return os_database::of(&lhs) == os_database::of(&rhs);};


--
#include <legalbs/standarddisclaimer>
Rich Paul                |  If you like what I say, tell my
C++, OOD, OOA, OOP,      |  employer, but if you don't,
OOPs, I forgot one ...   |  don't blame them.  ;->
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <322DDBE8.40DC@cds.duke.edu> Max TenEyck Woodbury
<mtew@cds.duke.edu> writes:

|> As a guess, passing an allocator INSTANCE to the string CONSTRUCTOR may be
|> a serious mistake.  It makes what should be a compact and efficent object
|> that will be used over and over again into something necessarily larger and
|> less efficent.  I'd bet that there will be more than one alternate
|> implementation (abet non-standard) that either ignores allocators or
|> uses a similar implementation to containers to achieve the same end.

At most, it only adds one pointer.  For a container, this doesn't seem
like much to me.

As I have pointed out before, the default allocator guarantees that all
instances compare equal.  So the implementation can implement a
partitial specialization on this which simply ignores the allocator
parameter.

If this really becomes an issue in user defined allocators, then the
compiler could always recognize the special case of operator== on the
allocator type always returning null, and optimize the pointer out.
(Implementors: don't put this high on your priority list.  IMHO, it will
never become an issue.  In the rare cases where performance is an issue,
I imagine that a user designed class tuned to the application, rather
than the general library class, will be used.  In this case, whether
there is a user defined allocator or not is indifferent.)
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone



[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <501or5$psf@jake.esu.edu> jpotter@falcon.lhup.edu (John
E. Potter) writes:

|> Arch Robison (robison@kai.com) wrote:
|> : denis (denis.bider@abm.si) writes:

|> : > I only have the April '95 draft, but according to it, only a list with
|> : > identical T and Allocator template arguments can be passed to
|> : > List<T, Allocator>::splice(), because splice() is not a member template.
|> : > (But a member of a template)

|> : The template arguments may be identical, but the constructor for list
|> : has an argument allocator of type Allocator.  Thus two lists with identical
|> : Allocator types could have different allocator objects.

|> And now that we all understand, 23.2.3.7 list operations [lib.list.ops]
|> void splice (iterator position, list<T, Allocator>& x);
|> must have linear complexity not constant as in the public draft.

The upper limit must be linear, but the draft could require constant
time for specific cases, e.g.: the default allocator, or allocators
comparing equal.

Alternatively, they could require all allocators of the same type to
compare equal.  Operations with allocators that don't compare equal
require a deep copy anyway, and probably aren't that common.  All of
the containers have a constructor which takes two iterators, so there
is no problem for the user to copy construct a container using one type
of allocator with the contents of a container using another type of
allocator.

This solution requires the user to make the deep copy explicitly.  This
can be viewed as either an advantage or a disadvantage, according to
your point of view.  It is nice to think that you can assign any string
to any other, and the implementation takes care of making the deap copy
only when needed.  On the other hand, you have an algorithm like
splice, which is almost always constant time.  Once, you accidentally
hit the case where it is linear, and you go crazy trying to figure out
why your program runs so slowly.

I really have no strong opinions one way or the other, but I suspect
requiring all allocators of the same type to compare equal is the
easiest solution for the standards committee.  Otherwise, they have to
verify all of the functions.  On the other hand, it's quite possible
that splice is just an oversight.  I note, for example, that the
complexity of swap is given as "linear in general, constant if
a.get_allocator() == b.get_allocator()".  (Another simple solution
would be to simply introduce a clause somewhere stating that unless
otherwise stated, the complexity guarantees only hold if the allocators
compare equal.)
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone



[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Max TenEyck Woodbury (mtew@cds.duke.edu) wrote:
: James Kanze US/ESC 60/3/141 #40763 wrote:
: > ...
: >
: > This problem is not unique to lists, but also affects any objects which
: > may want to use a shared representation.  I first encountered it when
: > trying to implement a reference counted string class.
: >

: I believe the argument in the original post is incorrect.

: I've seen your comments on strings before and I am still not sure why
: there is a problem, or if there is a problem, why it makes reference
: count strings a special problems.

: To be more specific, I don't see anyplace in the standard where the
: deallocator is parameterized except through the base class template.
[snip]

What deallocator?  The public draft talks about an allocator class.
Objects of any such class must have allocate(X::size_type) and
deallocate(X::pointer) member functions.  Constructors of containers
get a *reference* to an allocator object and produce a *copy* of the
allocator for use by this container.  Thanks to James and the
original poster, many of us have learned more than we wanted to know
about the standard library.  For example, since each container object
has its own allocator object, allocators are not required to support
operator==, the only way to be sure that internals of a container
can be deallocated is to know that they were allocated for this
container.  That makes it impossible to write a constant time swap
function for any container class; however, it is required.

The public draft is known to be full of these kinds of problems.  We will
not have a good idea what is really going on with allocators until we
see the next public draft in December.  I am going to drop discussion
in this area until then.  Best wishes to the committee in their
thankless efforts to get us a language.

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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <504ka3$p0@jake.esu.edu> jpotter@falcon.lhup.edu (John
E. Potter) writes:

|> Thanks to James and the
|> original poster, many of us have learned more than we wanted to know
|> about the standard library.  For example, since each container object
|> has its own allocator object, allocators are not required to support
|> operator==, [...]

I hope you didn't learn this from me.  The draft is quite clear that
allocators are required to support operator==, and the semantics of this
operator are that it returns true if the two objects are functionally
equivalant, i.e.: memory allocated by one can be deallocated by another.

Although the standard requires that all dynamic memory used by an object
be allocated by its allocator object, I presume that the "functionally
equivalent" requirement can be taken to mean that there is no way a
program could tell if the memory was allocated by another object in the
same equivalency class, so the implementation is free to do so under the
"as if" rule.  (I think it would be nice if the standard said this a
little clearer:-).  But as you say, we've yet to see the final draft,
and I'm sure that the committee members are aware of the problem and
working on it.)
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone



[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <4vhsst$f32@engnews1.Eng.Sun.COM> Arch Robison
<robison@kai.com> writes:

|> The original intent of STL was to provide generic algorithms that are
|> as fast as what hand-coded equivalents, but I fear that recent featurism
|> has made this very difficult in the case of class list.

|> According to the April 1995 and January 1996 drafts, the splice
|> operation takes constant time.

|>     void splice(iterator position, list<T,Allocator>& x, iterator i);

|>       Effects:
|>  Inserts an element pointed to by i from list x before position and
|>  removes the element from x. The result is unchanged if position ==
|>  i or position == ++i.
|>       Requires:
|>  i is a valid dereferenceable iterator of x.
|>       Complexity:
|>  Constant time.

|> So consider a call y.splice(j,x,i) for lists x and y, and iterators i and j.
|> The standard would appear to allow x and y to have two different (and
|> incompatible?) allocators!  There seem to be two alternative implementations,
|> both of which have problems:

|>  1.   Create a new list element in x, copy x[i] into y[j-1],
|>              and delete x.  This is constant time with respect to the
|>        size of the list, but very slow if the copy constructor
|>       for class T is very slow.  Hand-coded lists would probably
|>       never do this.

|>  2.   Unlink the element from list y and link it into x.
|>       This is very fast, but now list x has elements not from its
|>       allocator.  This would seem to violate the draft specification,
|>       and certainly complicate memory management.

|> So the standard seems to require the slow implementation (1).
|> Perhaps there should be a requirement on allocators a and b of type X
|> that they allow the expression a==b, which would return true if
|> b.deallocate(p) can handle a pointer generated by a.allocate(...)
|> and vice versa.

This problem is not unique to lists, but also affects any objects which
may want to use a shared representation.  I first encountered it when
trying to implement a reference counted string class.

There are two solutions:

1. Partial specialization on the allocator.  The default allocator
guarantees that all instances of it compare equal.  I suspect that 99%
of all uses will use the default allocator.  So a partial specialization
on the allocator makes sense.  (This supposes, of course, that your
compiler supports partial specialization.)

2. Compare allocators within the function.  If they compare equal, use
the shared data approach, otherwise, fall back on the expensive form.
This requires an additional run-time check when compared to the first
solution, but: a) it works even for user specified allocators, as long
as all of the memory allocated is from the same allocator (or rather,
from allocators from the same equality class), and b) it works with
current compilers.

Long term, I suspect that 1 will be the preferred solution.  It is
optimal for the default case, and I would suspect that most user defined
allocators would compare different offen enough for 2 not to be
worthwhile (but adopting 1 doesn't exclude using 2 in the more general
case).
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils,    tudes et r   alisations en logiciel orient    objet --
                -- A la recherche d'une activit    dans une region francophone



[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

> void splice(iterator position, list<T,Allocator>& x, iterator i);
>
> y.splice(j,x,i) for lists x and y, and iterators i and j.
> The standard would appear to allow x and y to have two different (and
> incompatible?) allocators!

I only have the April '95 draft, but according to it, only a list with
identical T and Allocator template arguments can be passed to
List<T, Allocator>::splice(), because splice() is not a member template.
(But a member of a template)


denis (denis.bider@abm.si)
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

denis (denis.bider@abm.si) writes:

> I only have the April '95 draft, but according to it, only a list with
> identical T and Allocator template arguments can be passed to
> List<T, Allocator>::splice(), because splice() is not a member template.
> (But a member of a template)

The template arguments may be identical, but the constructor for list
has an argument allocator of type Allocator.  Thus two lists with identical
Allocator types could have different allocator objects.

Arch D. Robison    Kuck & Associates Inc.
robison@kai.com    1906 Fox Drive
217-356-2288       Champaign IL 61820
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

biderd@abm.si writes:

> > void splice(iterator position, list<T,Allocator>& x, iterator i);
> >
> > y.splice(j,x,i) for lists x and y, and iterators i and j.
> > The standard would appear to allow x and y to have two different (and
> > incompatible?) allocators!
>
> I only have the April '95 draft, but according to it, only a list with
> identical T and Allocator template arguments can be passed to
> List<T, Allocator>::splice(), because splice() is not a member template.
> (But a member of a template)

True as far as it goes.  This means that you can only splice between
lists which use the same *type* of allocator.  The individual allocator
objects for each list may be different, however.  (Strictly speaking,
they will typically be different, since the default parameter for the
allocator in the constructor is A(), which creates a new allocator
object for each list.)  In the case of Allocator, all instances of the
default allocator type (and probably of a lot of user allocator types)
compare equal.  This was, in fact, the point of my comments concerning
specialization: since the implementor knows that all instances of the
default allocator compare equal, he can forgo the test for equality.

A user allocator may have instances that do not compare equal.  Note
all constructors for STL objects take an allocator parameter.  An
example of a use of an allocator type with instances that do not compare
equal would be a shared memory allocator which manages several pools of
shared memory, different pools shared between different processes.
Comparison of the allocator objects would return true if and only if the
objects used the same pool.  Note that in the above case, if both
allocators use the same pool, it is perfectly acceptable to take the
elements from one list, and put them in another.  If the allocators
don't, then you *MUST* do a deep copy.  Presumable, the processes
accessing the shared memory in the destination list may not be able to
access that in the source list.

--
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle --
                            -- Beratung in industrieller Datenverarbeitung
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze US/ESC 60/3/141 #40763 wrote:
> ...
>
> This problem is not unique to lists, but also affects any objects which
> may want to use a shared representation.  I first encountered it when
> trying to implement a reference counted string class.
>

I believe the argument in the original post is incorrect.

I've seen your comments on strings before and I am still not sure why
there is a problem, or if there is a problem, why it makes reference
count strings a special problems.

To be more specific, I don't see anyplace in the standard where the
deallocator is parameterized except through the base class template.
>From that it seems all deallocators have to handle whatever is thrown
at them from any allocation source.  If that is the case, a reference
count implementation presents no more problem than any other.  I could
be missing something though, and your help in pointing out what I missed
would be appreciated.

That doesn't mean I like the idea of the allocator being part of the
constructor parameter list for strings, or any other type for that
mater.  It should be a compile time specification, not a run time
specification, UNLESS you can specify a virtual deallocator, and
that has problems that shouldn't even have to be considered!  (Just
to start, how do you know that the object being deallocated has a
virtual deallocator? By the time you need to invoke the deallocator,
you no longer have an object, just raw storage, so either everything
has a virtual deallocator or nothing does.)

mtew@cds.duke.edu
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Arch Robison (robison@kai.com) wrote:
: denis (denis.bider@abm.si) writes:

: > I only have the April '95 draft, but according to it, only a list with
: > identical T and Allocator template arguments can be passed to
: > List<T, Allocator>::splice(), because splice() is not a member template.
: > (But a member of a template)

: The template arguments may be identical, but the constructor for list
: has an argument allocator of type Allocator.  Thus two lists with identical
: Allocator types could have different allocator objects.

And now that we all understand, 23.2.3.7 list operations [lib.list.ops]
void splice (iterator position, list<T, Allocator>& x);
must have linear complexity not constant as in the public draft.

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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

The original intent of STL was to provide generic algorithms that are
as fast as what hand-coded equivalents, but I fear that recent featurism
has made this very difficult in the case of class list.

According to the April 1995 and January 1996 drafts, the splice
operation takes constant time.

    void splice(iterator position, list<T,Allocator>& x, iterator i);

      Effects:
 Inserts an element pointed to by i from list x before position and
 removes the element from x. The result is unchanged if position ==
 i or position == ++i.
      Requires:
 i is a valid dereferenceable iterator of x.
      Complexity:
 Constant time.

So consider a call y.splice(j,x,i) for lists x and y, and iterators i and j.
The standard would appear to allow x and y to have two different (and
incompatible?) allocators!  There seem to be two alternative implementations,
both of which have problems:

 1.   Create a new list element in x, copy x[i] into y[j-1],
             and delete x.  This is constant time with respect to the
       size of the list, but very slow if the copy constructor
      for class T is very slow.  Hand-coded lists would probably
      never do this.

 2.   Unlink the element from list y and link it into x.
      This is very fast, but now list x has elements not from its
      allocator.  This would seem to violate the draft specification,
      and certainly complicate memory management.

So the standard seems to require the slow implementation (1).
Perhaps there should be a requirement on allocators a and b of type X
that they allow the expression a==b, which would return true if
b.deallocate(p) can handle a pointer generated by a.allocate(...)
and vice versa.

Otherwise, user's will have to depend on exotic optimization technology,
or simply hand-code their own lists and ignore class list<T,Allocator>
when fast splicing is an issue.

Arch D. Robison    Kuck & Associates Inc.
robison@kai.com    1906 Fox Drive
217-356-2288       Champaign IL 61820


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]