[boost] Re: Re: Formal Review: Circular Buffer

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2004-03-05 05:22:29

"Jan Gaspar" <jano_gaspar_at_[hidden]> wrote in message
news:20040305092703.88723.qmail_at_web41506.mail.yahoo.com...

> 1. your rationale mentions many characteristics that
> I would expect of
> std::deque. Do you have any idea
>    how big the performance difference is?
The memory is allocated at once, that's the biggest
difference.
------------
What I'm looking for is some more evidence that the data structure is really
faster. I think that
is relevant since that is your reason d'etre (or something, I never took
French in highschool :-) )
for the container.

>
> 2. You mention "Guarantee of basic exception safety"
> as a design criteria. I
> would expect many operations
>     to have a stronger guarantee.
Of cource, some methods provide stronger guarantee,
but in general the container povides just basic
exception safety. For some methods (e.g. insert) it is
impossible to provide stronger guarantees.
-------------
I guess I would like to know the exact guarantee of each function. It will
be important
for eg. when I have to provide a pointer version of circular_buffer for my
smart containers.

> 4. Type Requirements: don't T need to be Assignable
> too?
Just no!
---------
Then how is an element overwritten?

> 5. you could remove one version of push_back and
> push_front by using default
> arguments. Similar for insert()/rinsert()
I don't know if this is good idea or not, but all STL
implementations I've seen have containers with both
methods (one with default param and one without).
----------
ok. I must admit that I have never seen this before. For example, my
dinkumware only has vector::push_back( T& );

>
> 7. when you state contracts like
> Precondition:
> *(this).size() > index
> don't you mean (*this).size() ? I would prefer that
> you omitted this
> entirely.
This is just typo. Anyway I would retain the
precondition.
----------
yes, I'm not talking about removing the precondition. I just don't think
'this->' adds
anything. size() > index would be fine to me.

>
> 8. maybe you should add const_pointer data() const ?
It is not possible. data() is mutating operation. See
the source code.
---------------
ok. then maybe one should get more hints about this mutation (I did not have
a clue), maybe like
c.prepare_array();
foo( &*c.begin() );
And what complexity does it involves (linear, I assume)?

> 9 I assume you provide the basic exception safety
> for set_capacity().
> However, I think you could achieve the strong
> guarantee
>    by (1) allocating the new buffer and (2) start to
> copy elements [might
> throw] (3) swap the two buffers upon completion. The
> same goes for
>    resize(). Why are they both provided? (If you
> made resizes 2nd argument
> to be the bool, then how would they differ?]
Yes, it works exactly like this. But the statement
about provided exception safety covers the whole
container.
--------------
I think that saying that your container gives the basic exception safety
guarantee
is too weak a statement. Afterall, it *must* provide that guarantee. The
standard
specifies which operations that differs and under which cercumstances for T.

>
> 10.  Can't the exception guarantee for the
> copy-constructor be stronger too?
> (and assign(), and push_back(), push_front(),
> insert() )
No for insert()/rinsert(), push_xxx(), data() and
erase(). See the source code.
-------------
Ok, let's try push_back:

  void push_back(param_value_type item) {
        if (full()) {
            if (empty())
                return; (*)
            replace_last(item); // can throw
            increment(m_last); // nothrow
            m_first = m_last;   // nothrow
        } else {
            m_alloc.construct(m_last, item); // can throw
            increment(m_last);                     // nothrow
            ++m_size;                                 // nothrow
        }
    }

AFAICT, you have the strong property unless you cannot roll-back stuff in
replace_last/construct.
(*) it might be good to document that push_back() can choose *not* to insert
something. For example,
     it would be good for me to know when I write a pointer wrapper.

>
> 11. Some operations must be nothrow: swap(), size(),
> capaciity(),
> pop_back(), pop_front().
Yes, they are. It is not written explicitly in the
documentation (there is just no "Exceptions" section
for each method).
-----------
Ok, I can live with that :-). You could consider one line that said that.

br

Thorsten