Leigh Johnston said:
That implementation you talk about is not ideal as it is not an STL
compliant container: it does not use an allocator and it default
constructs NODE_SIZE T elements whenever a new node is created which
is not correct from an STL point of view. segmented_array is STL
compliant.
I have been able to spend a little more time looking through the code
for your segmented_array. I am not a library implementer by any stretch
of the imagination but there does appear to be an amount of interest in
your implementation alongside the idea of whether a chuncklist could be
proposed for inclusion in Boost. I am certainly interested in this as
an idea and, for my own learning, the requirements of STL compliance and
how you attain that in a library container have led me to want to look
more closely at your segmented_array. (I explain this merely to ensure
that any comments that I make will be understood as positively critical
at most and merely questioning at least.)
I was looking, in particular, at the implementation of the comparison
operators for your iterators, and I was noticing what seems to be a
problem or two and was wanting to raise a query also.
If we take your implementation of op== on your iterator_base class, for
example:
template <
typename Pointer2,
typename Reference2,
typename SegmentListIterator2,
typename SegmentIterator2,
typename Segment2
bool operator==(const iterator_base<
Pointer2,
Reference2,
SegmentListIterator2,
SegmentIterator2,
Segment2
{ return iPosition == rhs.iPosition; }
it seems that there is an issue here over this definition since it
permits the following:
09:12:32 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/Emacs/segmented_array $cat src/debug.cpp
#include <cassert>
#include "segmented_array.h"
int main()
{
lib::segmented_array<int> sa_int1;
lib::segmented_array<int> sa_int2;
sa_int1.push_back(1);
sa_int2.push_back(1);
assert(sa_int1.begin() == sa_int2.begin());
}
09:12:48 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/Emacs/segmented_array $make
Building file: src/debug.cpp
Invoking: gcc as compiler
gcc -O0 -gdwarf-2 -g3 -Wall -Wno-unused -fmessage-length=0
-MMD -MP -o bin/debug.o -c src/debug.cpp
Finished building: src/debug.cpp
Building target: bin/debug
Invoking: g++ as linker
g++ -Wl,--enable-auto-import -static -o bin/debug bin/debug.o
Finished building: bin/debug
09:13:39 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/Emacs/segmented_array $make run_debug
09:13:46 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/Emacs/segmented_array $
That is, since it compares only on position, it evaluates as equal two
iterators pointing to the same position in difference containers.
Obviously, if you replaced the use of segmented_array in this test with,
say, std::vector, this test would fail.
Further, I'm trying to understand what the purpose is of having your
operators (as op== here) as function templates parametertized
differently from the type instance itself. I am only beginning
to think this through and so this is just a query, but I notice that in
the specification for std::iterator [lib.iterator.synopsis] the
comparison operators are declared as free functions of the form:
template <class Iterator>
bool operator==(const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
Having experimented with your implementation I have not yet been able to
find a scenario in which I can discover the utility of your
parameterization. As illustrated above, op== returns true for two
iterators of the same type but on different arrays. Yet, if you try to
compare two iterators of different types (i.e., on containers of
different types) then it doesn't even compile.
09:32:11 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/Emacs/segmented_array $cat src/debug.cpp
// file: debug.cpp
#include <cassert>
#include "segmented_array.h"
int main()
{
lib::segmented_array<int> sa_int1;
lib::segmented_array<double> sa_double1;
sa_int1.push_back(1);
sa_double1.push_back(1);
assert(sa_int1.begin() == sa_double1.begin());
}
09:32:14 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/Emacs/segmented_array $make
Building file: src/debug.cpp
Invoking: gcc as compiler
gcc -O0 -gdwarf-2 -g3 -Wall -Wno-unused -fmessage-length=0 -MMD -MP
-o bin/debug.o -c src/debug.cpp
src/debug.cpp: In function ¡®int main()¡¯:
src/debug.cpp:18: error: no match for ¡®operator==¡¯ in
¡®lib::segmented_array<T, N, A>::begin() [with T = int, unsigned
int N = 64u, A = std::allocator<int>]() == lib::segmented_array<T,
N,A>::begin() [with T = double, unsigned int N = 64u, A =
std::allocator<double>]()¡¯
make: *** [bin/debug.o] Error 1
So, I'm not sure what there is in between comparing iterators of the
same type (which compiles, but succeeds too broadly) and comparing
iterators of different types (which fails to compile) that necessitates
the parameterization of your comparison operators as function templates
in this way.
Perhaps you could provide an example that illustrates this
implementation choice. I'm sure I have not yet considered all
possibilities.
Regards
Paul Bibbings
I note there's a C++ implementation here: