|
|
Boost : |
From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2003-07-20 20:30:05
"Jan Gaspar" <jga_at_[hidden]> wrote in message
news:3F17F1B1.47E66E6_at_whitestein.com...
> The implementation can be found at
> http://groups.yahoo.com/group/boost/files/circular_buffer.zip
>
Hello Jan,
I took look on the library and have few comments.
These could be voiced already - I didn't follow older
threads.
1. Namespace boost::detail should be changed
to boost::circular_buffer or something similar.
The "detail" may be used by other libraries
and cause name collisions.
2. "NonconstSelf" type name uses different naming convention than
all other names. Maybe it should be changed to "nonconst_self".
3. cb_iterator: is the m_end value needed?
It can be computed using 'm_it == m_buff->m_last' in
those few (~2) places it is needed and if eliminated,
iterator will get smaller (by 30%) and simpler.
4. Last cb_iterator constuctor: wouldn't it be more efficient
to pass the 'it' by value instead of reference?
5. In cb_iterator::operator-(): result of the expression
' it < *this' can be saved and not computed second time.
6. cb_iterator::operator==(): is the check 'm_end == it.m_end'
really needed?
7. cb_iterator::operator!=(): it may be more efficient to code
it as 'm_it != it.m_it ...' instead of !operator==().
I do not know if compilers are allowed to change logical
expression and if, how good they are in it.
8. cb_iterator::operator<(): the ASSERTS here are useless.
Function compare() doesn't return anything else
than -1/0/1 - I see it.
In addition, e.g. MSVC may pessimize result code if default
switch branch simply exists.
9. OTOH there are places where ASSERT can be inserted:
- ensuring two iterators come from the same buffer
- checking iterators are within valid range
- checking type of iterators is the same (reverse / normal)
STLport has similar facility in debug mode.
I can imagine circular_buffer invalidating iterators
(by setting flag 'invalid').
10. cb_iterator::compare() should be private.
11. circular_buffer<>: is the m_capacity member needed?
It can be calculated in capacity(). (The performance
impact is however rather small.)
12. circular_buffer<>: front(), back(), first(), last()
can be implemented more efficiently without using
rather complex operator[]. Compiler here has
no chance to optimize it away.
13. circular_buffer<>: set_capacity() should check
for ' new_capacity == capacity()'.
14. circular_buffer<>: set_capacity() is not exception safe:
if uninitialized_copy() throws it will leak.
This problem happens IMHO in many functions (e.g.
in constructors).
Scope guard can be used to get basic exception safety.
15: circular_buffer<>: function destroy() shoudl set m_buff to 0
to avoid chance for double delete. I am not sure it can
happen here but it feels more safe.
16. circular_buffer<> constructor taking iterators seems to be
buggy:
if (diff > capacity) {
std::advance(first, diff - capacity);
m_size = capacity;
m_last = m_buff;
} else {
m_size = diff;
m_last = m_buff + size();
}
should be:
if (diff > capacity) {
std::advance(first, diff - capacity);
m_size = capacity;
m_last = m_buff;
} else {
m_size = diff;
if (diff == capacity) { <<<-----
m_last = m_buff; <<<-----
} else {
m_last = m_buff + size();
}
}
17. circular_buffer<>::operator=(): possible executable
size improvement:
if (full()) {
m_last = m_buff;
std::uninitialized_copy(cb.begin(), cb.end(), m_buff);
} else {
m_last = std::uninitialized_copy(cb.begin(), cb.end(), m_buff);
}
can be
m_last = std::uninitialized_copy(cb.begin(), cb.end(), m_buff);
if (full()) {
m_last = m_buff;
}
(I didn't test it.)
18. both circular_buffer<>::assign():
m_buff = m_alloc.allocate(capacity(), 0);
should be
m_buff = allocate(n);
19. circular_buffer<>: both assign() can share common code.
20. circular_buffer<>::swap(): shouldn't m_alloc be swapped
as well? (I do not know what is current opinion about
this.)
If yes, it should be put at the beginning for exception
safety.
21. circular_buffer<>: there are few public sections one
following other. Is there any reason for this?
22. circular_buffer<>::push_back() and other functions
may benefit from passing some types by value rather
than by reference. Boost.call_traits<> can be used here.
When this trick was applied to STLport, these functions
got sped up by ~30%.
The same trick may be likely used for passed iterators.
23. It may be wortwile to check whether A. Alexandrescu's
Mojo technique cannot be used within circular_buffer<>.
(I have no idea about concrete applicaility here.)
24: circular_buffer<>::push_back() and others:
void push_back(const value_type& item) {
if (full()) {
...
return;
}
...
}
should be rather
void push_back(const value_type& item) {
if (full()) {
...
} else
...
}
}
for aestethic reasons.
25. circular_buffer<>::pop_back() and pop_front():
Shouldn't therse functions be protected against
empty buffer?
E.g. push_back/front are protected against zero size
buffer.
The cost of this check is rather small.
26. circular_buffer<>:: first insert(): some code from here
can be shared throughout the library.
27. circular_buffer<>: first insert(): POD types
can be memmove()d instead of object copying one by one.
Dtto for insert_n/rinsert_n.
I am not sure if this solution wouldn't get too complex,
though.
28. circular_buffer<>: insert(pos, n, item): I get compile error.
Test:
-----
circular_buffer<int> a(5);
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
circular_buffer<int>::iterator it1 = a.begin() + 2;
int new_value = 99;
a.insert(it1, 5, new_value);
Output on Intel C++ 7 plugged in MSVC6 IDE:
-------------------------------------------
Compiling...
test.cpp
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\utility(102): error:
no instance of overloaded function "std::_Iter_cat"
matches the argument list
argument types are: (int)
_Distance(_F, _L, _N, _Iter_cat(_F));
^
detected during:
instantiation of "ptrdiff_t={int} __cdecl std::distance(_II,
_II) [with _II=int]" at line 868 of
"C:\Temp\temp\circular_buffer\test\../include/circular_buffer.hpp"
instantiation of "void boost::circular_buffer<T,
Alloc>::insert(boost::circular_buffer<T, Alloc>::iterator,
InputIterator, InputIterator) [with T=int, Alloc=std::vector<int,
std::allocator<int>>::allocator_type, InputIterator=int]"
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\iterator(227): error:
no instance of overloaded function
"std::_Iter_cat" matches the argument list
argument types are: (int)
{_Advance(_I, _N, _Iter_cat(_I)); }
^
detected during:
instantiation of "void std::advance(_II &, _D) [with _II=int,
_D=int]" at line 871 of
"C:\Temp\temp\circular_buffer\test\../include/circular_buffer.hpp"
instantiation of "void boost::circular_buffer<T,
Alloc>::insert(boost::circular_buffer<T, Alloc>::iterator,
InputIterator, InputIterator) [with T=int, Alloc=std::vector<int,
std::allocator<int>>::allocator_type, InputIterator=int]"
C:\Temp\temp\circular_buffer\test\../include/circular_buffer.hpp(782):
error: operand of "*" must be a pointer
operator const value_type& () const { return *m_it++; }
^
detected during:
instantiation of "boost::circular_buffer<T,
Alloc>::Item<InputIterator>::operator const boost::circular_buffer<T,
Alloc>::value_type &() const [with T=int, Alloc=std::vector<int,
std::allocator<int>>::allocator_type, InputIterator=int]"
at line 1051
instantiation of "void boost::circular_buffer<T,
Alloc>::insert_n(boost::circular_buffer<T, Alloc>::iterator,
boost::circular_buffer<T, Alloc>::size_type, const Item &) [with T=int,
Alloc=std::vector<int,
std::allocator<int>>::allocator_
type, Item=boost::circular_buffer<int, std::vector<int,
std::allocator<int>>::allocator_type>::Item<int>]" at line 874
instantiation of "void boost::circular_buffer<T,
Alloc>::insert(boost::circular_buffer<T, Alloc>::iterator,
InputIterator, InputIterator) [with T=int, Alloc=std::vector<int,
std::allocator<int>>::allocator_type, InputIterator=int]"
compilation aborted for C:\Temp\temp\circular_buffer\test\test.cpp (code 2)
Error executing cl.exe.
test.exe - 3 error(s), 0 warning(s)
Output on BC++B 6.4:
--------------------
Build
[C++ Warning] _debug.h(377): W8058 Cannot create pre-compiled header: code
in header
[C++ Error] _iterator_base.h(94): E2406 Dependent type qualifier 'int' is
not a class or struct type
[C++ Error] _iterator_base.h(95): E2406 Dependent type qualifier 'int' is
not a class or struct type
[C++ Error] _iterator_base.h(96): E2406 Dependent type qualifier 'int' is
not a class or struct type
[C++ Error] _iterator_base.h(97): E2406 Dependent type qualifier 'int' is
not a class or struct type
[C++ Error] _iterator_base.h(98): E2406 Dependent type qualifier 'int' is
not a class or struct type
[C++ Error] circular_buffer.hpp(782): E2062 Invalid indirection
[C++ Error] _iterator_base.h(367): E2285 Could not find a match for
'__distance<_RandomAccessIterator,_Distance>(const
int,const int,undefined)'
[C++ Error] _iterator_base.h(367): E2109 Not an allowed type
[C++ Error] _iterator_base.h(447): E2285 Could not find a match for
'__advance<_InputIter,_Distance>(int,int,undefined)'
To cast second parameter to size_t helps but IMHO this should work.
29. circular_buffer<>: all insert(): special case when
n/copy == 0 can be handled just here
(and not in insert_n()).
This would avoid possible long costly advance().
30. circular_buffer<>: insert(Iterator, Iterator):
the last parameters can be safely passed as:
call_traits<InputIterator>::value_type.
31. circular_buffer<>::erase(pos): maybe there should
be protection against erase(buffer.end()) situation.
32. circular_buffer<>::erase(Iter, Iter) may try to use
memcpy() for POD. Again, if it isn't too complex
to implement.
33. circular_buffer<>::insert(Iter, Iter) may contain
STATIC_ASSERT check that Iter iterator value is
convertible to buffer main data type.
Some other functions as well.
Iterator traits may be checked as well.
34. This fragment produces invalid iterator value:
circular_buffer<int> a(0);
circular_buffer<int>::iterator it1 = a.begin();
++it1;
I mention it only because every other capacity
leaves such iterator valid (and equal end()).
35. circular_buffer<>: functions add() and sub()
could return changed pointer instead of using in/out.
It is nicer and with call_traits<> maybe even
faster.
36. circular_buffer<>::allocate() should check
against m_alloc.max_size() and
throw out_of_range if fails.
Now it (on old Dinkumware) likely throws bad_alloc.
37. Documentation: it would be nice to have documented
precondition, postconditions, exceptions
thrown etc. Maybe this info can be embedded into
Doxygened text.
38. Documentation: can standard algorithms be used on
circular buffer?
39. Can ostream<<() or dump() be added into
the library (conditionally by macro)?
40. Can circular_buffer<std::auto_ptr<...> > be made
uncompilable like standard containers are?
41. Documentation: can the documentation describe if
and possibly how hypotetical full featured policy based
circular buffer can be based on this one?
For example if one would like to add MT safety.
S pozdravom,
/Pavel
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk