Mathias Gaunard ha scritto:
> On May 15, 9:19 am, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
> wrote:
>
>> This looks actually more useful than set_capacity(), because it covers
>> the most common scenario and is not error prone. It replaces the "second
>> form" of the swap trick "std::vector<T>(v).swap(v)", but it's more
>> efficient because it would exploit move constructors, while the swap
>> trick would always make copies.
>
> That trick only makes one copy, which is needed unless standard
> allocators provide in-place shrinking anyway.

Yes, that tricks makes only one copy of the whole container. That means
it has to copy every element inside the container. That why I said
"copies". The point is that if the element type had a move constructor,
an optimized implementation of trim() might use it and avoid the copies.
Of course, we don't have language support for move constructors now, but
we will definitely have them in C++0X.

Ganesh

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

On May 17, 8:59 am, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
wrote:

> Yes, that tricks makes only one copy of the whole container. That means
> it has to copy every element inside the container. That why I said
> "copies". The point is that if the element type had a move constructor,
> an optimized implementation of trim() might use it and avoid the copies.

No. As I said, there is no way to do that unless allocators provide in-
place shrinking.
You need to copy to shrink, that's it. That's what you don't seem to
understand.

And I don't see how it is related to move constructors at all.

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

On May 17, 8:04 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> On May 17, 8:59 am, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
> wrote:

> > Yes, that tricks makes only one copy of the whole container. That means
> > it has to copy every element inside the container. That why I said
> > "copies". The point is that if the element type had a move constructor,
> > an optimized implementation of trim() might use it and avoid the copies.

> No. As I said, there is no way to do that unless allocators provide in-
> place shrinking.
> You need to copy to shrink, that's it. That's what you don't seem to
> understand.

No.  You don't seem to understand the motivations behind move
semantics.  The point is precisely to allow collections like
vector to reallocate without copying.

> And I don't see how it is related to move constructors at all.

Because reallocating without copying is part of their raison
d'   tre.

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ 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.comeaucomputing.com/csc/faq.html                      ]

Mathias Gaunard ha scritto:
> On May 17, 8:59 am, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
> wrote:
>
>> Yes, that tricks makes only one copy of the whole container. That means
>> it has to copy every element inside the container. That why I said
>> "copies". The point is that if the element type had a move constructor,
>> an optimized implementation of trim() might use it and avoid the copies.
>
> No. As I said, there is no way to do that unless allocators provide in-
> place shrinking.
> You need to copy to shrink, that's it. That's what you don't seem to
> understand.
>
> And I don't see how it is related to move constructors at all.
>

With move constructors, you can achieve shrinking by doing this:

1) allocate a new, smaller buffer (the "new" buffer)
2) use move constructors to initialize every element of the new buffer
from every element of the "old" buffer
3) change the internal pointer so that it points to the new buffer
4) destroy the elements of the old buffer
5) deallocate the old buffer

That's essentially the same as doing a copy, except that it uses move
constructors instead of copy constructors. The only concern is what
happens if a move constructor throws, as the contents of the old buffer
are lost during the process and so we cannot "rollback" the operation.
However, if the move constructor does not throw (a requirement that is
usually easy to achieve) then there is no problem at all. The committee
seems to think that this additional requirement is acceptable, as the
latest draft of the standard includes explicit reference to it (see for
example 23.2.5.2/2).

I agree that having in-place shrinking allocators would be optimal, as
it would avoid even the alloc/move/destroy/free cycle, but as you can
see the copy *can* be avoided in C++0x and the latest draft provides
wording to allow such optimization.

Regards,

Ganesh

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

In the current C++ standard the user has little control of how much
memory standard containers use. The swap trick is usuallty the prefered
way today to make a container return unused capacity but it is not the
"natural" way to do it and it is confusing to novices.


Here are some proposals to give the user some more control over the
memory a container uses. They are influenced by the N2271 "EASTL --
Electronic Arts Standard Template Library".


1; Default constructed containers as well as basic_string must not
allocate any memory.

Neither speed nor memory overhead should be forced upon stl users unless
needed. This would result in higer performace without inpact on existing
code.

2; I would like to see the following functionallity available for
containers like vector and dequ.,


- function:  void set_capacity(size_t n);
- postcondition: (capacity() == n)

Works as reserve when n >= size().
When n<size() the conatiner will shrink and the new size will be
min(n,size()).


- function:  void free();
- postcondition: (size() == capacity() == 0)

This would be the same as calling set_capacity(0);

The EASTL version is named reset, but free reflects it's intention better.


3; The following functionality would also be useful, but not as much as
those already discussed.

- function:  void trim();
- postcondition: (capacity() == size())

This is the same as calling container.set_captacity( container.size() );

When a container has been filled and the user decides that he doesn't.
Requriements: the value type is moveconstructible.


Daniel Svensson

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

Daniel Svensson ha scritto:
> 1; Default constructed containers as well as basic_string must not
> allocate any memory.
>
> Neither speed nor memory overhead should be forced upon stl users unless
> needed. This would result in higer performace without inpact on existing
> code.

This is a quality-of-implementation issue, which IMHO need not be
mandated by the standard. I expect any sensible library implementor to
already do that unless there is *very* good reason for doing otherwise
and in that case I say we should trust the implementor. BTW, I assume
with "memory" you mean "heap memory", because otherwise you would
actually forbid techniques like the "small string optimization".

> 2; I would like to see the following functionallity available for
> containers like vector and dequ.,

deque do not have a concept of capacity. Providing these functionalities
may actually hinder the implementation of deque without a significant
gain. I would consider them only for vectors.

> - function:  void set_capacity(size_t n);
> - postcondition: (capacity() == n)
>
> Works as reserve when n >= size().
> When n<size() the conatiner will shrink and the new size will be
> min(n,size()).

Notice that calling reserve(n) actually has the post-condition
capacity() >= n and changing the size won't change the capacity. So if
you want the == in the post-condition you need to be more explicit in
the definition.

Frankly, I don't find this one so useful, because it's too general. I
have never encountered a case where I would need such power (I guess
that 99.9% of the times all you need is trim(), below). Moreover, I find
it error prone, because it has a completely different semantic according
to n being less than greater than size() (it destroys elements in the
former case but does not add elements in the latter!).

Better force the programmer to make a explicit choice, as in:

  if(n < v.size())
    v.resize(n);
  else
    v.reserve(n);

>
> - function:  void free();
> - postcondition: (size() == capacity() == 0)
>
> This would be the same as calling set_capacity(0);
>
> The EASTL version is named reset, but free reflects it's intention better.

I agree that it is useful, as it essentially replaces the hackish
swap-trick. I don't like the name free() as it sounds more like a noun
to me (like empty(), which actually sounds like a verb ;). reset() is
better because it's used with a similar semantic in smart pointers, that
can be seen as degenerate containers.

> 3; The following functionality would also be useful, but not as much as
> those already discussed.
>
> - function:  void trim();
> - postcondition: (capacity() == size())
>
> This is the same as calling container.set_captacity( container.size() );

This looks actually more useful than set_capacity(), because it covers
the most common scenario and is not error prone. It replaces the "second
form" of the swap trick "std::vector<T>(v).swap(v)", but it's more
efficient because it would exploit move constructors, while the swap
trick would always make copies.

Just my two eurocent,

Ganesh

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

> I assume
> with "memory" you mean "heap memory", because otherwise you would
> actually forbid techniques like the "small string optimization".

That is correct.

> > 2; I would like to see the following functionallity available for
> > containers like vector and dequ.,
>
> deque do not have a concept of capacity. Providing these functionalities
> may actually hinder the implementation of deque without a significant
> gain. I would consider them only for vectors.

You are probably right here, only containers that have the concept of
capacity should be affected.
In my opinion that includes basic_string.

> > - function:  void set_capacity(size_t n);
> > - postcondition: (capacity() == n)
>
> > Works as reserve when n >= size().
> > When n<size() the conatiner will shrink and the new size will be
> > min(n,size()).
>
> Notice that calling reserve(n) actually has the post-condition
> capacity() >= n and changing the size won't change the capacity. So if
> you want the == in the post-condition you need to be more explicit in
> the definition.

Ok, the reserve part of the desciption was innacurate. I actually I
intended it to work as the postcondition.

> Better force the programmer to make a explicit choice, as in:
>
>   if(n < v.size())
>     v.resize(n);
>   else
>     v.reserve(n);
>

Resize is not required to deallocate memory, but the following code
reflects how it would work.

if(n < v.size())
 {
    v.resize(n);
    v.trim();
 }
else
  v.reserve(n);

The advantage of a set_capacity function would be that you would be
able to both resize and trim at the same time, but it might be less
error prone to not make it resize the container when n < size().
In addition that after you have set the capacity and filled it you
would not have to trim the container to be sure that it has no excess
capacity.


>> reset() is better because it's used with a similar semantic in smart pointers, that
>> can be seen as degenerate containers.

Reset might be a better name but in the paper it is stated that
beginners tend to confuse it with clear.
When other parts of the standard library uses reset in that way it
would make sens that also vector and strings does so.

Thanks for your feedback Ganesh. What does the rest of you think about
these functions?


/Daniel Svensson

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

On May 15, 9:19 am, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
wrote:

> This looks actually more useful than set_capacity(), because it covers
> the most common scenario and is not error prone. It replaces the "second
> form" of the swap trick "std::vector<T>(v).swap(v)", but it's more
> efficient because it would exploit move constructors, while the swap
> trick would always make copies.

That trick only makes one copy, which is needed unless standard
allocators provide in-place shrinking anyway.


---
[ 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.comeaucomputing.com/csc/faq.html                      ]