Re: Sequence container with fast random access and fast insertion/removal (wherever)
Martin Knoblauch Revuelta ha scritto:
Alberto Ganesh Barbati wrote:
Why do you ask? It's just a container, if it has good iterators and a
reasonable interface, how could it be anti-STL?
Well, it might look like a substitute of vector and list (it's not!),
saving the effort of choosing the correct one in every case. Using it
everywere would be a very bad idea.
Is list a substitute of vector? And let's not forget deque, which is
better than vector in a lot more cases than you might think of. Every
container has its pros and cons and that's why you have more than one.
Your container have even different pros and cons and that's good: one
more tool at your disposal. I wouldn't trust a programmer that thinks
about "saving the effort of choosing" ;-)
Do you think it is useful?
Sure it may be. Maybe you should propose it on the Boost mailing list.
But before posting your code there, you should definitely get rid of the
non-portable macros OFFSET_OF and OWNER. The former is actually not
needed, you can use the standard and portable macro offsetof instead.
I tried offsetof, and I got compiler warnings about playing around NULL
with some compiler... (too old compiler to recognize I'm still using it
;) The thing is that I still need OWNER (see below), so one more macro
is not a big difference.
It *is* a big difference. Because your macro is unportable (in
standardese: it calls for undefined behaviour) and might not work on
conformant compilers.
> There's no problem with OFFSET_OF, since ANY_ADDR is reasonably small,
It doesn't matter how you choose ANY_ADDR. You just can't portably
dereference anything that's not a valid pointer (including NULL).
The latter is just too hack-ish to be even considered for a respectable
library code.
That's because of the char size, isn't it? I thought about this for a
long time. In first place I considered converting the pointers to
integers. Something like:
#define ANY_ADDR 0x100 // Some round number
#define OFFSET_OF(ClassName,MemberName) \
( (long) &(((ClassName*)ANY_ADDR)->MemberName) - \
(long) ANY_ADDR )
#define OWNER(ClassName,MemberName,MemberAddress) \
( (ClassName*) ((long)(MemberAddress) - \
OFFSET_OF(ClassName,MemberName)) )
That's even worse than the previous one, if possible. Using C-style
casts (which in this case resolve to reintepret_casts) makes the whole
macro implementation-defined, therefore non-portable.
but OWNER will truncate MemberAddress if sizeof(void*)>sizeof(long)
(64-bit address spaces are here...).
Yep, that's even another problem.
But yes, the whole thing stinks. Is there a standard way to do it?
Unfortunately not. Now that I see at code more closely, I'm afraid so
say that you have to rethink the whole design. I know that sounds harsh,
but if you strive for conformance and portability, that's the price to pay.
The OWNER trick is very useful. Using it we don't need to store
pointers to the container in the tree nodes. Neither in iterators.
Another benefit is that the dummy node (root, sentinel, end and rend,
all in one) doesn't have a T object nor an ugly never-used equivalent
memory space. All this simplifies the code: the dummy node is treated
as an ordinary node while working with list and tree links.
I don't dispute that the OWNER trick is not useful. Simply it's a fact
that the C++ standard says it has undefined behaviour, so it cannot be
accepted as a portable tool.
What about...
* Supporting allocators
Why not?
- Is it good/bad that many methods are made static?
In fact that sounds very strange to me. A lot of functions looks like
they can be made members of some class. For example:
static avl_array_node<T> * next (avl_array_node<T> * p)
{
assert (p); // NULL pointer dereference
return p->x.next;
}
why don't you just make it a member function of class avl_array_node<T>?
The following:
template<class IT1, class IT2>
static void swap (IT1 it1, IT2 it2);
should instead be a free function and it's a good candidate for a
specialization of std::iter_swap.
HTH,
Ganesh
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]