Bradd W. Szonye wrote:
>
> Bill Wade wrote in message <6aisf1$n8s$1@uuneo.neosoft.com>...
> >
> >If you just want smaller impact in the objects, make all pointers contain
> >the vtable for the fully constructed, most derived object.  In the objects,
> >use a single bit to indicate if it is fully constructed.  For partially
> >constructed object use some other means (an expensive global mapping from
> >pointers to current dynamic type) for dynamic type resolution.
> >
> >You could also have a slightly different language where even for partially
> >constructed objects, virtual dispatch occurred using the fully constructed
> >object's methods.
>
> [Briefly: you're right about the vidx model not playing well with sl's.]
>
> I wouldn't want that! If that were acceptable, I wouldn't worry so much
> about the model being conforming. However, you did (indirectly) give me an
> idea! The big clue was "use an expensive mapping" for the tricky case.
>
> You might not be able to find a spare bit in the object, but you can do
> something else. Instead of setting the global pointer to the most derived
> class, give it a trap representation. Use some sort of snap technique (like
> float emulation) to adjust the vptrs when used. I guess you'd still have to
> store the "real" vptr somewhere (thereby losing at least some of the space
> savings for this class), but then I don't expect that a lot of polymorphic
> classes are handing out their this pointers during construction.
>
> Thanks for the tip!

Another idea:

As the size of the object usually matters only for arrays, you could
set up the rule that the vptr is always stored in front of the array
the object belongs to (single objects would be treated as one-element
arrays for this purpose). Then you need a way to decide if your object
is the first one in the array. This could be done in two ways (plus
those I don't see now ;-)):

- allocate one extra char for the object (this may cause the same
  space consumption as a vptr for pointer-aligned classes, but may
  be much less for char-aligned classes). A flag would in principle
  be sufficient, but a faster implementation would be to store the
  number of objects to skip, or 255, if it's at least 255 objects
  (that is, if you encounter '255', you must look again after going
  so far).
- store this information in the pointers (in this case, a flag is not
  enough, instead the index or offset has to be stored; OTOH this also
  allows easy range checking support in debugging versions).

This solution could have another size advantage: If you store the size
of dynamic objects in the vtbl, you can replace the size value of the
memory block by the vptr (if your vtbls are all aligned at an even
number
of bytes, and allocation is in even sizes as well, you can use the
lowest bit to decide if it is a size or a vptr, by setting it to 1
for size, as vptrs are more often accessed). This way, the vptr
itself wouldn't occupy any space at all. Of course, if there is an
user supplied operator new, you cannot assume anything about memory
layout, so you have to allocate extra memory for the vptr again.


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Bradd W. Szonye wrote:[...]

> This leads me to ask another question: I've heard that the traditional
> cfront vptr-in-object memory model is not the only possible choice for C++,
> but what are some alternatives with comparable performance?

I have read report on super-optimizing experimental compilers, and they do use other techniques. It was called Vortex.
It uses global-program class analysis to determine the number of implementations for a particular vtable or virtual
function. It then either generate: a non-virtual function (one impl.), in-code switch statement (few impl.), a cache of
more probable vtable results (many impl., with test-run feedback). The gain of putting in-code tests is to avoid loading
a different page in memory where the vtable is located and it allows optimizations to be done accross calls (if only for
the look-ahead instruction of many RISC jump).
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Bradd W. Szonye wrote in message <6a7fli$gtj@examiner.concentric.net>...
>I think I would call this alternate-alternate model the 'vidx-in-object'
>model, where 'vidx' means "virtual table index" instead of the more common
>"virtual table pointer." I'd call it the 'vi' model, but then I might
>confuse "virtual index" with my favorite editor. (Okay, second favorite,
but
>I don't have authority to install vim everywhere I work.)

This would not be desirable in environments where "linking" occurs at run
time (.dll,.so) since the size of the family tree can change dynamically.

If you just want smaller impact in the objects, make all pointers contain
the vtable for the fully constructed, most derived object.  In the objects,
use a single bit to indicate if it is fully constructed.  For partially
constructed object use some other means (an expensive global mapping from
pointers to current dynamic type) for dynamic type resolution.

You could also have a slightly different language where even for partially
constructed objects, virtual dispatch occurred using the fully constructed
object's methods.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Bill Wade wrote in message <6aisf1$n8s$1@uuneo.neosoft.com>...
>
>If you just want smaller impact in the objects, make all pointers contain
>the vtable for the fully constructed, most derived object.  In the objects,
>use a single bit to indicate if it is fully constructed.  For partially
>constructed object use some other means (an expensive global mapping from
>pointers to current dynamic type) for dynamic type resolution.
>
>You could also have a slightly different language where even for partially
>constructed objects, virtual dispatch occurred using the fully constructed
>object's methods.

[Briefly: you're right about the vidx model not playing well with sl's.]

I wouldn't want that! If that were acceptable, I wouldn't worry so much
about the model being conforming. However, you did (indirectly) give me an
idea! The big clue was "use an expensive mapping" for the tricky case.

You might not be able to find a spare bit in the object, but you can do
something else. Instead of setting the global pointer to the most derived
class, give it a trap representation. Use some sort of snap technique (like
float emulation) to adjust the vptrs when used. I guess you'd still have to
store the "real" vptr somewhere (thereby losing at least some of the space
savings for this class), but then I don't expect that a lot of polymorphic
classes are handing out their this pointers during construction.

Thanks for the tip!
---
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <6a0t54$k83@examiner.concentric.net>, "Bradd W. Szonye"
<bradds@concentric.net> wrote:

> [put vtable ptr in every pointer to object instead of object itself]
>
...
> Now, hopefully I've convinced you that the "alternate" object model is worth
> considering even if it's not ideal for all applications. The question
> remains, can you implement "fat" polymorphic pointers without burdening all
> the non-polymorphic pointers with a vptr?

The real question is, can you implement them at all? When an object's type
changes, how do all pointers to it get their vtable pointer updated? When
does an object's type change, you ask? Well, every time a derived class
constructor/base class destructor executes.

--
Chelly Green | chelly@eden.com | C++ - http://www.eden.com/~chelly
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Bill Wade wrote in message <6a3be4$6qu$1@uuneo.neosoft.com>...
>
>You've listed a number of ... reasons [for the vptr-in-pointer model].
> I'll take the opposite side [and argue it well!].
>
>If pod* is size four and poly* is size eight, you must either use void* of
>size eight, or change the meaning of the conversion poly* to void* to
poly*.

I'd say that sizeof(void*) would have to be 8, to support the definition of
void*.

>void* should be the same size as char* or there are serious compatibility
>problems.

There are probably some issues here, although I didn't think that it would
impact a reasonably well-written program, at least not in semantics. Could
you discuss some of the compatibility issues?

>If void* is not big enough to hold a poly*, you lose the implementation
>choice of implementing structures using void* code.  I can no longer give C
>libraries void pointers to my polymorphic objects.  Instead I must give
them
>void pointers to my pointers to my objects.

Unless this is what you mean--yes, sizeof(void*) >= sizeof(poly*). I see how
this is a problem for C compatibility. There are two possibilities here;
either the same implementor provides a C implementation with sizeof(void*)
== "8" or the extern "C" calling convention includes adjusting the address
to address-of-most-derived and stripping the type information from void*s. I
think the latter would work and is preferable, but there may be more hidden
issues here.

>Doubling the size of pointers approximately doubles the cost (time and
>space) of pass-by-(pointer or reference) for polymorphic objects, while
>making the cost of pass by value smaller by a constant amount.  Since pass
>by reference is the preferred form for most polymorphic objects, I would
>expect a net loss in performance for typical programs.

I'm embarassed to admit that I'd glossed over this in my mind, probably
because I've been lured in by the "generic programming fad" in C++, and I
work less with polymorphic types these days. It's a good argument. I'd
casually say "It's a size-speed optimization, put in a compiler switch at
link time to set the object module," although of course then you just
postpone the incompatibility problems to shared libraries and dynamic
linking.

>Pointers  become more sensitive to lifetime issues.  Don't try this at
home:
>
>struct A; A* gp = NULL;
>struct A { A(){ gp = this; } virtual ~A() };
>struct B: public A { virtual ~B() };

I stripped your nice little tricky code down to the minimum to exhibit the
problem. Yuck. I see what you mean, although I had to stare at it for a
while. The compiler has 4 choices:

1. Go back and fix the vptr of "gp" during the construction of B objects.
(yuck)
2. Clone the vtbl for each B object so that it can be fixed during
construction. (yuck)
3. Use a handle-based pointer system (fixes the pointer size problem, but
adds even more speed overhead, yuck)
4. Use magic. (yuck)

The traditional model only has to fix the vptr in the A subobject during
construction. I guess this leads to a fifth choice:

5. Revert to the traditional model for the uncommon case where "this" gets
moved outside the object during construction (can of worms, yuck, but maybe
this one is solvable).

Okay, so this is a major icky criticism of the alternate model.

But I'd still like to ask boldly whether the alternate model leads to a
conforming implementation, if the problems can be worked out.
---
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Bill Wade wrote in message <6a3be4$6qu$1@uuneo.neosoft.com>...
>
>You've listed a number of ... reasons [for putting vptrs in pointers].
>I'll take the opposite side.

[The alternate model does not handle the case of assigning 'this' to a
variable outside the object very well.]

I've given this some more thought, and re-phrased the two sides of this
debate.

My original hypothesis:
S1. Polymorphism is irrelevant or trivial when an object's type is
statically known.
S2. Polymorphism is important when an object is accessed by reference.
S3. Additional information can be stored in references/pointers to
polymorphic types without impacting references/pointers to non-polymorphic
type with sufficient optimizer intelligence (still unproved, and the subject
of this thread).
Therefore,
H. Type information (eg, vptrs) should appear in references/pointers, not
among the object data, since that is where the information is necessary.
Corollary: this can result in significant space savings, which is desirable.

Mr. Wade's counter:
W1. During construction, an object's static type changes.
W2. It is possible to assign 'this' to pointers outside the object during
construction.
Therefore,
C. The implementation must be able to adjust the type of 'p' where the
assignment 'p = this' occurs during construction of a base class.

I must agree that statement C is a valid criticism of my hypothesis, H.
There are only a few valid ways to cope with the 'p = this' problem; the
ones obvious to me either involve tracking 'this' and changing it everywhere
or associating the type with the object itself, which negates the benefits
of my alternate object model. Neither is particularly satisfactory.

One solution, using handles for pointers, leads to some other nice effects,
like simplifying automatic memory management and memory reallocation, but it
certainly does not improve speed or space performance. So I'll concede that
my alternate model may not be viable from a performance standpoint--unless
somebody more innovative than I can address the problem of statement C.

This leads me to ask another question: I've heard that the traditional
cfront vptr-in-object memory model is not the only possible choice for C++,
but what are some alternatives with comparable performance?

Finally, it occurred to me that there still are some optimizations of the
vptr-in-object model which may be viable. For example, consider another
implementation with 32-bit vptrs. The optimizer could determine that an
entire inheritance hierarchy has fewer than 256 classes and that each class
in the hierarchy has byte alignment; it then can replace the 32-bit vptr
with an 8-bit index into a 256-element vtbl array. This handles the
hierarchy of lightweight character objects (in my earlier article) fairly
well, probably better than either vptr-in-object or vptr-in-reference. Of
course, the space advantange of this might be nullified by the performance
disadvantage of using 8-bit indices on a particular platform.

I think I would call this alternate-alternate model the 'vidx-in-object'
model, where 'vidx' means "virtual table index" instead of the more common
"virtual table pointer." I'd call it the 'vi' model, but then I might
confuse "virtual index" with my favorite editor. (Okay, second favorite, but
I don't have authority to install vim everywhere I work.)
---
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <69osom$jf3@examiner.concentric.net>,
Bradd W. Szonye <bradds@concentric.net> wrote:
>    Under an alternate object model:
>    1. sizeof(poly) == sizeof(pod)
>    2. sizeof(poly[1000]) == sizeof(pod[1000])
>    3. sizeof(poly *) == 8   // vptr + address
>    4. sizeof(pod *) == 4
>    5. minimum sizeof(vector<T>::iterator) == 4
>    6. minimum sizeof(set<T>::iterator) == 4
>
>Some notes: where I'd expect the big win is in #2: the savings of not
>putting vtable pointers in heavily-allocated, lightweight objects. (Also,

Is case 2 very likely?  Since we're talking about polymorphic objects,
aren't we much more likely to have poly*[1000] than poly[1000]?  If we
have a large array of pointers to poly, your new model would in fact
take up more space than the standard model does.

- Marc
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Marc Sherman wrote in message <6a0a4g$rf1@shell.magma.ca>...
>In article <69osom$jf3@examiner.concentric.net>,
>Bradd W. Szonye <bradds@concentric.net> wrote:
>>    Under an alternate object model:
>>    1. sizeof(poly) == sizeof(pod)
>>    2. sizeof(poly[1000]) == sizeof(pod[1000])
>>    3. sizeof(poly *) == 8   // vptr + address
>>    4. sizeof(pod *) == 4
>>    5. minimum sizeof(vector<T>::iterator) == 4
>>    6. minimum sizeof(set<T>::iterator) == 4
>>
>>Some notes: where I'd expect the big win is in #2: the savings of not
>>putting vtable pointers in heavily-allocated, lightweight objects. (Also,
>
>Is case 2 very likely?  Since we're talking about polymorphic objects,
>aren't we much more likely to have poly*[1000] than poly[1000]?  If we
>have a large array of pointers to poly, your new model would in fact
>take up more space than the standard model does.

That's the same criticism to come up as last time: that you're more likely
to have pointers to polymorphic objects than arrays of them. However, I'm
not sure how the alternate model uses more space; the cost for poly*[1000]
merely shifts the vptrs from 1000 objects to 1000 pointers. There's O(C)
additional space in the pointers used to actually iterate the array,
probably one each for begin, end, and current. The pointer overhead only
becomes a problem if, say, two arrays of poly*[1000] each point to the
objects, but that's a shared ownership problem that we usually try to avoid.

As for the likelihood of case 2, it depends on how often you create vectors,
lists, sets, and maps of polymorphic objects. Perhaps developers would
design "contained" objects as non-polymorphic, since you can't use the
polymorphism in a container anyway. On the other hand, it might be common to
create objects which appear in containers but still work in a
virtual-dispatch system like COM. Within the application (or management
subsystem), they are non-polymorphic, but they expose a virtual interface to
external systems.

The main object is to provide a way to allow large arrays of polymorphic
type at considerably reduced overhead without adding significant overhead to
pointers-to-non-poly or arrays of pointers to poly. It makes things like
collections of lightweight, polymorphic objects much more space-efficient,
so long as the individual collections (or large subsequences within them)
have the same actual type.

For a rough example of how this would be useful: you have a polymorphic
character base type 'character', a non-polymorphic character-sequence
container 'char_seq', and a document container 'doc'. The document container
collects char_seqs, and the sequences hold arrays of character-derived
objects, giving access to them as 'character &' or 'character *'. A char_seq
uses an allocator or cloning object with methods to create and destroy
(groups of) characters, and to specify character width. It merely puts a
convenient interface around this.

Hopefully the example is clear: I'll clarify if not. Now consider the memory
usage: each char_seq has a 'character*' in it with a hidden vptr. The actual
characters have no vptrs, just the 1-4 bytes needed for the character
itself. The doc object creates no vptrs either, since char_seq is
non-polymorphic. Now, your character types can use polymorphism to implement
metrics, behavior, etc. at very little memory cost (1 vptr per run of
same-style characters) or development effort. You get the benefits of
polymorphism *and* lightweight objects without having to code some tricky
work-around based on a flyweight pattern.

Is that a compelling reason to want to take the vptrs out of the objects and
put them in the pointers? Personally, I just feel that it makes sense to put
the type information in the references, not the objects: the object type is
known except when accessed by reference. And my own coding style tends to
use more objects than references, since I work so much with non-polymorphic
containers like vector<>.

Now, hopefully I've convinced you that the "alternate" object model is worth
considering even if it's not ideal for all applications. The question
remains, can you implement "fat" polymorphic pointers without burdening all
the non-polymorphic pointers with a vptr?
---
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Bradd W. Szonye wrote in message <6a0t54$k83@examiner.concentric.net>...
>Now, hopefully I've convinced you that the "alternate" object model is
worth
>considering even if it's not ideal for all applications. The question
>remains, can you implement "fat" polymorphic pointers without burdening all
>the non-polymorphic pointers with a vptr?

You've listed a number of 'for' reasons.  I'll take the opposite side.


If pod* is size four and poly* is size eight, you must either use void* of
size eight, or change the meaning of the conversion poly* to void* to poly*.

void* should be the same size as char* or there are serious compatibility
problems.

If void* is not big enough to hold a poly*, you lose the implementation
choice of implementing structures using void* code.  I can no longer give C
libraries void pointers to my polymorphic objects.  Instead I must give them
void pointers to my pointers to my objects.

Doubling the size of pointers approximately doubles the cost (time and
space) of pass-by-(pointer or reference) for polymorphic objects, while
making the cost of pass by value smaller by a constant amount.  Since pass
by reference is the preferred form for most polymorphic objects, I would
expect a net loss in performance for typical programs.

Pointers  become more sensitive to lifetime issues.  Don't try this at home:

struct A;
A* gp;
struct A
{
  A(){ gp = this; gp->Foo(); }    // Call A::Foo() since we're not yet a B.
  virtual void Foo();
};
struct B: public A
{
  virtual void Foo();
};

void Bar()
{
  B b;
  gp->Foo();    // Call B::Foo()
}

With your design it would be tough for an implementation to correctly call
both A::Foo and B::Foo.

Cheers.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

I have a feeling that this has come up before, but I'll ask anyway: what's
the output of this very short program (or is it ill-formed)?

#include <iostream>

struct incomplete_type_one;
struct incomplete_type_two;

int main()
{
    incomplete_type_one * p1;
    incomplete_type_two * p1;
    std::cout << sizeof p1 << endl;
    std::cout << sizeof p2 << endl;
    std::cout << (sizeof p1 == sizeof p2) << endl; // ***
    return 0;
}

In particular, I'm curious about the output of the marked line. Someone (I
think it was Mr. Kanze) once said that the interaction between separate
compilation and incomplete types in C++ implies that all pointers-to-class
had to have the same size and alignment requirement.

Is that implication true, or does it depend on the assumption that the
compiler can't know the complete types during the translation phase? In
other words, would a compiler be conforming if it could "magically" find the
definition of an incomplete type and use it to adjust a pointer's properties
(including size)? And could a compiler diagnose an error in the above
program, where the types are never completed? (I'm not sure that it's an
error to never complete the types, however, so long as they're never used.)

In particular, I wonder whether a compiler with a sophisticated link
phase--which is sure to become more common because of templates--could
search for the actual class defintion and optimize the properties of a
pointer based on whether the type is a POD-struct, an aggregate, a
non-polymorphic type, or a polymorphic type.

This of course goes back to my old idea to put the vtable pointers in the
pointers and not in the object data. It's a much more realistic idea if you
only pay for what you use: that is, only the size of pointer-to-polymorphic
increases, while the size of pointer-to-POD stays the same. Assume that an
address and a vtable pointer each are 4 bytes in size, and that the classes
'poly' and 'pod' are polymorphic and non-polymorphic, respectively, with the
same amount of member data:

    Under the typical C++ object model:
    1. sizeof(poly) == sizeof(pod) + 4
    2. sizeof(poly[1000]) == sizeof(pod[1000]) + 4000
    3. sizeof(poly *) == 4
    4. sizeof(pod *) == 4
    5. minimum sizeof(vector<T>::iterator) == 4
    6. minimum sizeof(set<T>::iterator) == 4

    Under an alternate object model:
    1. sizeof(poly) == sizeof(pod)
    2. sizeof(poly[1000]) == sizeof(pod[1000])
    3. sizeof(poly *) == 8   // vptr + address
    4. sizeof(pod *) == 4
    5. minimum sizeof(vector<T>::iterator) == 4
    6. minimum sizeof(set<T>::iterator) == 4

Some notes: where I'd expect the big win is in #2: the savings of not
putting vtable pointers in heavily-allocated, lightweight objects. (Also,
you don't need the vptrs on the stack, since the fully derived type is known
there too).  Where the answer to my question above becomes important is in
#4: the size of a non-polymorphic pointer. If it can be 4 bytes, then #6 is
easy: the set nodes aren't polymorphic, so the iterators can be simple node
pointers. The vector iterator is a little trickier: fortunately, the T in
vector<T> is not actually subject to polymorphism, so the iterator can store
the value internally as just the address (an int, char*, whatever) and
replace the type information when actually dereferenced.

Comments, criticisms?
--
Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]