writing an external function in std c++

[James Kanze]

On 19 Feb., 11:41, Richard Herring <junk@[127.0.0.1]> wrote:

[...]

You really think it will help? The very first push_back will do
something internally equivalent to reserve(N) for some N which quite
likely exceeds 4.
Perhaps. I have not examined my implementation but would expect it to
have reserves of 1, 2 and four.

Why? (That's certainly not what my implementation would do, if
I were writing it.)

Because I would expect std::vector to grow exponentially. Now,
I know that this does not mean doubling, but for very small
numbers I would expect an effective doubling.

Even for 0. 0 has to be special cases, since 2*0 isn't going
to grow the vector at all. Given that, I would expect the
special case to use something more than 4.

I see behind the lines a suggestion that there might be a
faster growth for small values and this could well be so.
Intuitively I understood this not to be according to the
standard, but this was pure intuition.

What happens for small values is irrelevant with regards to the
*amortised* complexity requirements specified in the standard.

Now looking at it, it looks as my implementation allocates four times
- namely as 1,2,3 and 4 elements. It tries to grow to
max(new_size,current_capacity + current_capacity/2).

I'd also use a multiplier of 1.5. On the other hand, I'd
definitely special case 0, rather than funnel everything into
the same function (with new_size, in this case, probably equal
to current_capacity + 1 -- but maybe your implementation does
the special casing upstream, ensuring that new_size is at least
16, or something like that).

And while the idea didn't occur to me until your posting, I
think I think that using a larger multiplier for very small
vectors might be a good idea. (You don't want anything bigger
than around 1.6 for larger vectors, of course.) So my
expression would be more like:

max( max( new_size, minSize ),
current_capacity + ( current_capacity > pageSize
? current_capacity / 2
? current_capacity ) )

(On the other hand, I wonder if it isn't worth special casing
current_capacity == 0 completely. Given that in this case, you
don't have to worry about copying and deallocating the old
vector.)

 

[peter koch]

    [...]
You really think it will help? The very first push_back will do
something internally equivalent to reserve(N) for some N which quite
likely exceeds 4.
Perhaps. I have not examined my implementation but would expect it to
have reserves of 1, 2 and four.
Why?  (That's certainly not what my implementation would do, if
I were writing it.)

Because I would expect std::vector to grow exponentially. Now,
I know that this does not mean doubling, but for very small
numbers I would expect an effective doubling.

Even for 0.  0 has to be special cases, since 2*0 isn't going
to grow the vector at all.  Given that, I would expect the
special case to use something more than 4.

I see behind the lines a suggestion that there might be a
faster growth for small values and this could well be so.
Intuitively I understood this not to be according to the
standard, but this was pure intuition.

What happens for small values is irrelevant with regards to the
*amortised* complexity requirements specified in the standard.

Now looking at it, it looks as my implementation allocates four times
- namely as 1,2,3 and 4 elements. It tries to grow to
max(new_size,current_capacity + current_capacity/2).

I'd also use a multiplier of 1.5.  On the other hand, I'd
definitely special case 0, rather than funnel everything into
the same function (with new_size, in this case, probably equal
to current_capacity + 1 -- but maybe your implementation does
the special casing upstream, ensuring that new_size is at least
16, or something like that).

Many reallocations end in one function in my implementation, where the
number of total elements is given.

And while the idea didn't occur to me until your posting, I
think I think that using a larger multiplier for very small
vectors might be a good idea.  (You don't want anything bigger
than around 1.6 for larger vectors, of course.)  So my
expression would be more like:

    max( max( new_size, minSize ),
         current_capacity + ( current_capacity > pageSize
                              ? current_capacity / 2
                              ? current_capacity ) )

(On the other hand, I wonder if it isn't worth special casing
current_capacity == 0 completely.  Given that in this case, you
don't have to worry about copying and deallocating the old
vector.)

What does pageSize have to do with this? Also your solution is quite
inefficient when many small sized vectors are allocated. I never wrote
a C++ vector, but once did something similar and i used the formula
new_capacity = old_capacity + old_capacity/2 + c, where c was
initially 1 but later changed to 8. But my container was not a general
purpose one and 8 might be a very bad number for some uses.

/Peter

 

[James Kanze]

Many reallocations end in one function in my implementation,
where the number of total elements is given.

That's to be expected. That doesn't prevent special casing
(although in a lot of cases, it might be interesting to special
case even earlier).

What does pageSize have to do with this?

It's just a convenient name for some magic number. The optimal
cut-off point would probably depend on the allocation strategy
used in operator new().

Also your solution is quite inefficient when many small sized
vectors are allocated.

In terms of memory, maybe. Or maybe not. In my experience,
most small vectors are allocated with the size in the
constructor, and are never grown. Any choice you make here
represents a trade off, and you can find cases where it isn't
optimal for something.

I never wrote a C++ vector, but once did something similar and
i used the formula new_capacity = old_capacity +
old_capacity/2 + c, where c was initially 1 but later changed
to 8. But my container was not a general purpose one and 8
might be a very bad number for some uses.

Yes. The real problem with the formula above is finding the
right values for minSize and pageSize.