"James Russell Kuyper Jr." <kuyper@wizard.net> writes:

> Stephen Howe wrote:
> >
> > "James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
> > news:3BD4B660.F3C7606@wizard.net...
> ...
> > > There's no reallocate() member in the Table 32 requirements for
> > > Allocators. How would you go about writing the code for
> > > std::vector<T,Allocator>::pack() without it?
> >
> > Right. But I was treating the OP's suggestion as a request and therefore the
> > allocator would have to support such functionality. As far as I can see,
> > with the Allocators interface at the moment, it can't be done efficiently.
>
> As far as I can see, it can't be done at all.
>
> In order to maintain backward compatibility, reallocate() or a function
> with comparable abilties would have to be made an optional Allocator
> member; we can't go breaking all of the code that depends upon
> allocators that don't have that member. Therefore, it would have to be
> undefined behavior to use std::vector<T,Allocator>::pack() unless
> Allocator defines that member. This approach to the problem is
> technically feasible, but IMO extremely unlikely to be approved.

It would not have to be undefined behaviour, if the (non-)existance of
the function is detectable by code, say through an allocator_traits.
Then one possibility (the iterator-biased choice) would be to make
pack() a no-op for allocators witout resize-capability, another
possibility (the memory-biased choice) would be to invalidate the
iterators in that case.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

Christopher Eltschka wrote:
...
> It would not have to be undefined behaviour, if the (non-)existance of
> the function is detectable by code, say through an allocator_traits.

As a general rule, I distrust solutions which depend upon traits
classes. A traits template will give you the correct information only if
someone remembers to specialize the template for each new class it might
be applied to. You can usually choose a "safe" default when it isn't
specialized, but that means that in general the traits template can't be
counted on to correctly the question it's designed to answer.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3C228128.B4CC8CE3@wizard.net...
> Christopher Eltschka wrote:
> ...
> > It would not have to be undefined behaviour, if the (non-)existance of
> > the function is detectable by code, say through an allocator_traits.
>
> As a general rule, I distrust solutions which depend upon traits
> classes. A traits template will give you the correct information only if
> someone remembers to specialize the template for each new class it might
> be applied to. You can usually choose a "safe" default when it isn't
> specialized, but that means that in general the traits template can't be
> counted on to correctly the question it's designed to answer.

It is possible to write a traits class that automagically detects whether a
member function of a known signature exists.  I think this code is legal and
does that, unfortunately I've yet to find a compiler that can actually cope
with it!  Even Comeau segfaults with it ;-(.

    namespace details
    {
      template <class T, class Type, Type>
      struct type_fwd
      {
        typedef T type;
      };

      template <class T, class = T>
      struct has_reallocate
      {
        enum { value = false };
      };

      template <class T>
      struct has_reallocate
      <
        T,
        typename type_fwd
        <
          T,
          void *(T::*)(void *, size_t, size_t),
          &T::reallocate
        >::type
      >
      {
        enum { value = true };
      };
    }

    template <class T>
    struct allocator_traits
    {
      enum { has_reallocate = details::has_reallocate<T>::value };
    };

I admit the code isn't pleasant, but it does avoid having to remember to
specialise allocator_traits for every new allocator.

--
Richard Smith


---
[ 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.research.att.com/~austern/csc/faq.html                ]

kuyper@wizard.net (James Russell Kuyper Jr.) wrote (abridged):
> For most of the other standard containers, there's considerable less
> reason to bother with such a function. std::vector<T> and std::deque<T>
> are the only ones that routinely have a reason to significantly
> overallocate.

It could be useful to add such a function to the Allocators themselves.
For example, a list allocator might keep a pool of free blocks which could
grow large.

    std::list<int> l;
    // ...
    l.get_allocator().pack();

would be a hint for the allocator to return free blocks to the heap it got
them from. It should just be a hint, in my view, which the allocator (or
collection) could ignore.

  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.research.att.com/~austern/csc/faq.html                ]

Stephen Howe wrote:
>
> "James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3BD4B660.F3C7606@wizard.net...
...
> > There's no reallocate() member in the Table 32 requirements for
> > Allocators. How would you go about writing the code for
> > std::vector<T,Allocator>::pack() without it?
>
> Right. But I was treating the OP's suggestion as a request and therefore the
> allocator would have to support such functionality. As far as I can see,
> with the Allocators interface at the moment, it can't be done efficiently.

As far as I can see, it can't be done at all.

In order to maintain backward compatibility, reallocate() or a function
with comparable abilties would have to be made an optional Allocator
member; we can't go breaking all of the code that depends upon
allocators that don't have that member. Therefore, it would have to be
undefined behavior to use std::vector<T,Allocator>::pack() unless
Allocator defines that member. This approach to the problem is
technically feasible, but IMO extremely unlikely to be approved.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

Hallo,
the lack of any explicit means for *reducing* the memory used by a
vector has lead to the invention of idioms to obtain the same effect,
which appear to rely more on specific implementation characteristics
than on explicit support in the standard, as discussed in a recent
thread under the subject: "Defect Report: Vector reallocation and swap".

As this functionality appears to be required by many programmers,
wouldn't it be reasonable to add a "pack()" (or any better name) member
function whose effect would be to reduce a vector capacity to its size?

The "pack()" function would obviously reallocate the internal array,
thus invalidating all iterators.

Cheers,
Nicola Musatti

---
[ 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.research.att.com/~austern/csc/faq.html                ]

> The "pack()" function would obviously reallocate the internal array,
> thus invalidating all iterators.

Why should it do that? I would far rather it returned any excess memory back
to the allocator and shrink the internal array insitu.
That way, no interators would be invalid, no constructors, copy constructors
or destructors would be called.

But generalising this, I would prefer that pack(), shrink() existed for all
types of containers and would minimise any excess memory under the
containers control. Further, all other types of container member functions
should not minimise excess memory.

Stephen Howe





---
[ 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.research.att.com/~austern/csc/faq.html                ]

Stephen Howe wrote:
>
> > The "pack()" function would obviously reallocate the internal array,
> > thus invalidating all iterators.
>
> Why should it do that? I would far rather it returned any excess memory back
> to the allocator and shrink the internal array insitu.

There's no reallocate() member in the Table 32 requirements for
Allocators. How would you go about writing the code for
std::vector<T,Allocator>::pack() without it?

> But generalising this, I would prefer that pack(), shrink() existed for all
> types of containers and would minimise any excess memory under the
> containers control. Further, all other types of container member functions
> should not minimise excess memory.

For most of the other standard containers, there's considerable less
reason to bother with such a function. std::vector<T> and std::deque<T>
are the only ones that routinely have a reason to significantly
overallocate.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3BD4B660.F3C7606@wizard.net...
> Stephen Howe wrote:
> >
> > > The "pack()" function would obviously reallocate the internal
array,
> > > thus invalidating all iterators.
> >
> > Why should it do that? I would far rather it returned any excess
memory back
> > to the allocator and shrink the internal array insitu.
>
> There's no reallocate() member in the Table 32 requirements for
> Allocators. How would you go about writing the code for
> std::vector<T,Allocator>::pack() without it?

Hehe, quite so. See www.cuj.com/experts/1912/alexandr.htm.


Andrei


---
[ 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.research.att.com/~austern/csc/faq.html                ]

"James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3BD4B660.F3C7606@wizard.net...
> Stephen Howe wrote:
> >
> > > The "pack()" function would obviously reallocate the internal array,
> > > thus invalidating all iterators.
> >
> > Why should it do that? I would far rather it returned any excess memory
back
> > to the allocator and shrink the internal array insitu.
>
> There's no reallocate() member in the Table 32 requirements for
> Allocators. How would you go about writing the code for
> std::vector<T,Allocator>::pack() without it?

Right. But I was treating the OP's suggestion as a request and therefore the
allocator would have to support such functionality. As far as I can see,
with the Allocators interface at the moment, it can't be done efficiently.

> For most of the other standard containers, there's considerable less
> reason to bother with such a function. std::vector<T> and std::deque<T>
> are the only ones that routinely have a reason to significantly
> overallocate.

Ok

Stephen Howe


---
[ 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.research.att.com/~austern/csc/faq.html                ]