[boost] Proxy indirect container adaptor: 4 claims

From: Christian Engström (christian.engstrom_at_[hidden])
Date: 2004-02-26 08:39:31

>> Christian Engström <christian.engstrom_at_[hidden]> writes:
>>
>>The classic example is the expression  a == b, which becomes ambiguous
>>[...]
> 
> 
> David Abrahams wrote:
> 
> A classic example of a problem that can bve solved more elegantly by
> the iterator adaptors library, *without* the problematic two-way
> implicit conversion -- and it *is* problematic, even if one direction
> is derived-to-base.  You asked for feedback; I say look at the work
> that those came before you already did in this area.  I don't know why
> you won't, but I've stopped trying now.

Excellent, if there is a more elegant way that can even handle raw 
pointer iterators, that could very well be how the proxy package should 
be implemented --- *if* it should be implemented.  But there's the rub, 
as I see it.

I get the distinct feeling that we are talking a little bit at 
cross-purposes, which is making this discussion much more frustrating 
for both of us than it ought to be.  Before we've managed to give each 
other a heart attack :-), I'd like to try and see if I can explain what 
I mean.

If I read you correctly, you are getting more and more annoyed at the 
idio^h^h^h^h list member who persists in defending some crappy home-made 
indirect container implementation, while [seemingly] refusing to even 
look at the components that already exist in the form of professionally 
crafted state-of-the-art implementations in the Boost library.  Even if 
one has never been in such a situation (which I have, in other areas), 
it's easy to imagine how frustrating it must be.

For me, what's so frustrating is that although the discussion is both 
useful and interesting for me, and that I'm learning a lot, I feel that 
it is always drifting away from the aspect that I'm really the most 
interested in right now, which is to find an answer to the question:

--Is there a way to define a package for indirect containers, so that 
one can take a program that uses a direct container, and convert it to 
using an indirect container just by changing the definition of the 
container type?

I have a first proposal for a design and a demo implementation (that's a 
better word, isn't it?) that seem to suggest, to me at least, that the 
answer is "yes", but before doing anything else I'd like to hear some 
further opinions on the matter.  Is the apparent "yes" of the demo 
implementation false, and if so, what is the problem that makes it 
impossible to construct a solution along these general lines?

When you ask me why I don't just use indirect_iterator, the answer is 
that it's because I can't see how I could achieve my goal of "just 
change the typedef to switch" by using it.  Are you saying that it's 
actually possible to use indirect_iterator to get the test program from 
my first post to switch from using a direct to an indirect container, by 
just changing a single line in the program?  If so, could you please 
tell me which line should be changed to what, because I honestly can't 
see it for myself?  I enclose a copy of the test program at the bottom 
of this post for your convenience.

If it's *not* possible to do this with indirect_iterator, can we at 
least agree that the proxy package strives (whether it succeeds or not) 
to achieve something that is not already offered by the existing packages?

If we were to agree on this, the next question would of course be "So 
what?", or in other words:

--Would it be any useful to be able to switch containers like that?

The problem here is of course that "usefulness" is very much in the eye 
of the beholder, so all that I can say with certainty is that I 
personally would find it quite useful, and that I don't see why other 
people as well shouldn't sometimes find themselves in situations when 
they would want to change container types easily.  After all, isn't one 
of the great benefits of the STL containers that they have (reasonably) 
uniform interfaces, so that it's easy to switch between the different 
container types, often by just changing a typedef?

Whether others agree that it's a worthwhile quest or not, this is what 
I'm looking for, and this is what I haven't been able to find in the 
existing packages.

If there was such a package, I would of course prefer it if there were 
as few restrictions as possible on when and how it could be used, but 
since I'm aware that this is the real world, I am prepared to accept it 
if there are certain caveats and restrictions as long as they can be 
clearly documented, and as long as the situations where the package 
*can* be used still represent a sizable portion of everyday use.

I'll briefly state the main "claims" of the proxy package design, and 
try to  summarize where I think it stands today, after the discussion 
here in this thread.

1) By using a proxy object, which is essentially a shared_ptr with the 
pointer arithmetic removed and with the comparison operators redefined 
to compare the elements, and storing such proxy objects in an STL 
compatible container, we can use all the algorithms in the STL on the 
Container< proxy<T> >, and get the same result as with a Container<T>. 
(This works even with the standard STL iterators and in the absence of 
any of the other components of the package, so it could be used as a 
standalone feature if desired.)

2) By making proxy<T> implicitly convertible to T&, a proxy<T> can be 
used (almost) as a T when it comes to assignments and argument passing. 
  In the situations when it doesn't work, such as if a function takes a 
U argument and was expecting another user-defined conversion from T to U 
to let it handle a T arguments as well, the compiler will generate a 
type error.

3) By letting proxy_container define an extra variant for each member 
function that would normally take a proxy<T> argument, and letting the 
extra variant accept a T instead, we complete the last part of the 
symmetry with direct containers as far as entire T objects are concerned.

4) By defining operator-> in for proxy_container's iterators to do a 
double dereferencing, the meaning of that expression remains the same 
for a proxy_container iterator as it would for the direct container 
iterator.  operator* keeps its normal semantics and does a single 
dereferencing.  This definition is necessary to keep Claim 1 valid, and 
to keep the proxy_container working as one would expect from an indirect 
container in general.

Can any of these claims be irreparably shot down?  *That* is the 
question that I would like to have an answer to.

Possible killers

Your objection that the STL standard is phrased in a way that allows 
implementations to reject would-be iterators because of the semantics of 
an operator that won't be used and which doesn't even have to exist is 
indeed a serious one, but I would still be interested to know if there 
are any other potential show-stoppers as far as these claims are concerned.

If this STL definition were to turn out that the *only* thing that makes 
it impossible to provide a "typedef switchable" container, I think that 
that in itself would be a very interesting thing to know.  I understand 
your reluctance to add more finely-grained iterator categories than 
necessary to the standard, but if an otherwise meaningful design was 
broken solely by the fact that the STL lists requirements that exceed 
its actual needs, wouldn't that at the least be a serious argument for 
considering a revision of those requirements?  One solution could 
perhaps be to introduce some "minimal iterator" categories that 
contained only what the STL algorithms that also work on built-in types 
actually need, and reduce the requirements for those algorithms 
accordingly, but otherwise keep everything as is?

Anyway, I've noted the objection you make, but I'm still interested to 
know if this is the only one of this dignity, or if there are more.

Restrictions and caveats

On use:
U1)  The meaning of (*x).y and x->y is not the same for proxy_iterator, 
so if the program uses the (*x).y form, the package can't be used.

U2)   If  the code that surrounds the container expects another 
user-defined conversion from T to U to take place, this won't work and 
the compiler will generate a type mismatch error, because only one 
implicit user-defined conversion is allowed, and that one has already 
been used up by the implicit conversion from proxy<T>.

On the underlying container:
C1)  The underlying container must define its iterators as classes.

If it turns out that this restriction can be lifted that would be great 
news, but if some unforeseen problem should arise with it, it's a 
restriction that I (personally) would be able to live with.  In the demo 
implementation the package works directly for all the implemented 
classes except vector with MSVC6, and for that case I don't think the 
workaround of using a deque is unreasonable.  I am fully aware that both 
the workaround and the implementation in general are crude and could be 
rewritten in a much more sophisticated way, but right now its only 
purpose in life is to demonstrate a design that is built on the four 
claims above.  For that purpose it works with vector/deque/list under 
both gcc and MSVC6, so with all its faults, the demo already seems to 
cover what could possibly be the six most widely used containers in the 
world.

Implementation issues

Loads, no need to repeat them here, but all fixable it seems.

But if there's a flaw in the basic design, it won't help a bit to 
implement it in the most sophisticated manner imaginable, the result 
will just be rubbish anyway.

Since I am not at all entirely convinced yet that the four claims are as 
rock-steady as I'd like them to be, I would much rather discuss what 
further restrictions and caveats can be found against the claims as 
such, before going on to discuss things that could be fixed in the 
implementation.  I find it very encouraging, however, that the 
impression I get from reading your comments is that the implementation 
issues are all entirely soluble, as long as it's done in the proper way.

I hope this explains why I'm being so bone-headed.  :-)

/Christian

//===================================================================
int main (int argc, char* argv[])
//-------------------------------------------------------------------
{
   person a_person;
   person someone_special("Alice", 27);
   ifstream in_file("test_proxy.in");

   typedef std::vector<person> buf_type;         // <----
//  typedef proxy_vector<person>::self buf_type;    // <----

   buf_type buf(5, person("Undefined", -1));
   buf.front() = person("First", 1);
   *(buf.begin() + 1) = person("Second", 2);
   buf[2] = person("Third", 3);
   (buf.begin() + 3)->name = "Incomplete";

   while (a_person.read(in_file)) {
     buf.push_back(a_person);
   }

   std::sort(buf.begin(), buf.end());

   for (buf_type::iterator it = buf.begin(); it != buf.end(); ++it) {
     cout << *it;
     if (it->age < 0) cout << "  Not a proper age";
     if (*it == someone_special) cout << "  Someone special";
     if (it != buf.begin() && (*it == *(it – 1)))
       cout << "  Duplicate record";
     cout << endl;
   }

   buf_type::iterator end_it = std::unique(buf.begin(), buf.end());
   cout << "\nNumber of unique records: " << (end_it - buf.begin());

   cout << "\n\nCalls to 'person's copy constructor: "
        << calls_to_copy_constructor << endl;
   return 0;
}