Binary search trees (AVL trees)

Discussion in 'C Programming' started by jacob navia, Jan 3, 2010.

  1. jacob navia

    jacob navia Guest

    Continuing the container library I have started the more complex
    containers: trees.

    I implemented over the holidays the AVL trees in a small module of
    around 600 lines. Obviously the bare minimum: insert/delete and
    find. There is an equal method to compare two trees.

    This is a powerful container that can search a giga-object database with
    just around 30 comparisons...

    But it is still not the red/black trees used by the C++ crowd, that will
    be done later.

    This trees implement sets, i.e. all elements are unique, and there are
    no keys, the element itself is the key and it is stored just behind
    each node.

    What bothers me is the enormous overhead of the 64 bit pointers:

    typedef struct tagBinarySearchTreeNode {
    char hidden;
    char factor;
    struct tagBinarySearchTreeNode *left;
    struct tagBinarySearchTreeNode *right;
    char data[];
    } BinarySearchTreeNode;

    Size: 24 bytes overhead

    To store the "hidden" bit and the 3 bits needed for the factor
    I am wasting 8 bytes since the pointers must be aligned at an
    8 byte boundary... Besides I am wasting 16 bytes in those two
    pointers when there will be very few applications that will use
    trees of more than 4Giga objects... and in fact most applications
    will fit in 65535 objects.

    If we limit ourselves to 65535 objects in the tree, we could
    allocate a table with 65535 nodes, and instead of using 8 byte pointers
    we could use 16 bit unsigned shorts that would index into that
    table. At the same time, we eliminate the alignment bytes.

    We would have then:

    typedef st+ruct tagBinarySearchTreeNode {
    char hidden;
    char factor;
    unsigned short left;
    unsigned short right;
    char data[];
    } BinarySearchTreeNode;

    Size: 6 bytes overhead. An improvement of 300% !!

    Limiting the number of objects to 4 Giga objects yields
    still an improvement of 100% since our node would take
    12 bytes.

    It is in this flexibility to elimnate waste where C could
    make a big contribution precisely.
     
    jacob navia, Jan 3, 2010
    #1
    1. Advertising

  2. jacob navia

    jacob navia Guest

    jacob navia a écrit :
    [snip]

    After posting that, I have just discovered that I can do the transition
    between the smallish 65535 limited trees to the 32 bit ones AUTOMATICALLY!

    Since I keep the count of the elements in the tree header, when I arrive
    at inserting the 65537th element I have just to change the POINTER of
    the vtable to point to the vtable of the 32 bit version, reallocate the
    nodes in 32 bits and go on!

    This is completely impossible to do in C++ since an object can't change
    dynamically its class at runtime.

    This idea has far reaching consequences for doing dynamically adaptive
    data structures. I could start all containers in the "smallish" version,
    and grow as needed.

    What is interesting in the C version is that it is completely dynamic.
    You can adapt the data structure to new conditions AS NEEDED, without
    having to fix everything during the compilation.

    True, the insertion of the 65537th element will take some time... :)

    Happily for C++ users, the library will be available for them too.

    Just add the

    extern "C"

    jacob
     
    jacob navia, Jan 3, 2010
    #2
    1. Advertising

  3. jacob navia

    Gene Guest

    On Jan 3, 2:43 pm, jacob navia <> wrote:
    > Continuing the container library I have started the more complex
    > containers: trees.
    >
    > I implemented over the holidays the AVL trees in a small module of
    > around 600 lines. Obviously the bare minimum: insert/delete and
    > find. There is an equal method to compare two trees.
    >
    > This is a powerful container that can search a giga-object database with
    > just around 30 comparisons...
    >
    > But it is still not the red/black trees used by the C++ crowd, that will
    > be done later.
    >
    > This trees implement sets, i.e. all elements are unique, and there are
    > no keys, the element itself is the key and it is stored just behind
    > each node.
    >
    > What bothers me is the enormous overhead of the 64 bit pointers:
    >
    > typedef struct tagBinarySearchTreeNode {
    >         char               hidden;
    >         char               factor;
    >         struct tagBinarySearchTreeNode *left;
    >         struct tagBinarySearchTreeNode *right;
    >         char               data[];
    >
    > } BinarySearchTreeNode;
    >
    > Size: 24 bytes overhead
    >
    > To store the "hidden" bit and the 3 bits needed for the factor
    > I am wasting 8 bytes since the pointers must be aligned at an
    > 8 byte boundary... Besides I am wasting 16 bytes in those two
    > pointers when there will be very few applications that will use
    > trees of more than 4Giga objects... and in fact most applications
    > will fit in 65535 objects.
    >
    > If we limit ourselves to 65535 objects in the tree, we could
    > allocate a table with 65535 nodes, and instead of using 8 byte pointers
    > we could use 16 bit unsigned shorts that would index into that
    > table. At the same time, we eliminate the alignment bytes.
    >
    > We would have then:
    >
    > typedef st+ruct tagBinarySearchTreeNode {
    >         char               hidden;
    >         char               factor;
    >         unsigned short     left;
    >         unsigned short     right;
    >         char               data[];
    >
    > } BinarySearchTreeNode;
    >
    > Size: 6 bytes overhead. An improvement of 300% !!
    >
    > Limiting the number of objects to 4 Giga objects yields
    > still an improvement of 100% since our node would take
    > 12 bytes.
    >
    > It is in this flexibility to elimnate waste where C could
    > make a big contribution precisely.


    Not much surprise that 8-byte pointers need 8 bytes. This is why 64-
    bit technology is not widespread: memory still has costs.

    I'm curious about "hidden" and "factor". Last time I implemented AVL
    trees, only 2 bits of balance information were needed.

    Is the final "data" field meant to be a pointer to node data? If so,
    you'd be better off with void*. It avoids at some casts and is more
    evokative of what is meant.

    I agree with defining nodes with just "data" and not key and value.
    IME most applications require a way to get the key while working with
    the value, so you end up maintaining extra pointers or storing keys
    twice anyway. It's more flexible to think of "key" and "value" as
    functions on structured data rather than separately stored values.
    (FWIW, the Containers library of Ada 2005 took this approach for sets
    in the form of very elegant generic definitions. Worth checking out.)

    I suggest that tree equality is most cleanly provided by implementing
    iterators rather than a special purpose traversal. A pair of
    iterators makes equality testing trivial. Iterators that can start at
    any given element and step in either direction are particularly handy:
    they make the trees usable in many cases where you'd normally like a
    vector/list but need to avoid O(n) per op behaviors. With AVL trees,
    the absolute maximum depth is only about 100 or so. Consequently
    iterator stacks can have fixed sizes.

    You might consider offering a container that manages bare nodes:

    typedef struct tagBinarySearchTreeNode {
    struct tagBinarySearchTreeNode *left, *right;
    char balance;
    } BinarySearchTreeNode;

    Now the user can define his or her own nodes that extend this. I
    believe that for Intel architectures at least, this gives you access
    to the 7 characters that otherwise would be padding. I.e.

    typedef struct tagBinarySearchTreeNode {
    struct tagBinarySearchTreeNode *left, *right;
    char balance;
    char data[7];
    } MySearchTreeNode;

    will still be packed in 24 bytes. (I have not checked this.) Or a 4-
    byte integer index ought to fit as well.

    It's a bit ugly, but I've done this by preprocessor with stuff like:

    /* header file binarytrees.h */
    #ifndef BINARY_TREE_DATA
    #define BINARY_TREE_DATA
    #endif

    typedef struct tagBinarySearchTreeNode {
    struct tagBinarySearchTreeNode *left, *right;
    char balance;
    BINARY_TREE_DATA
    } BinarySearchTreeNode;
    /* end header file binarytrees.h */

    Now you can do stuff like

    typedef struct {
    ...
    } MY_DATA;

    #define BINARY_TREE_DATA MY_DATA data[1];
    #include "binarytrees.h"
    #undef BINARY_TREE_DATA

    Finally, trees that allow duplicate keys, have many uses. You should
    consider supporting them. Iterators make that easier, too.
     
    Gene, Jan 3, 2010
    #3
  4. jacob navia

    jacob navia Guest

    Gene a écrit :
    >
    > I'm curious about "hidden" and "factor". Last time I implemented AVL
    > trees, only 2 bits of balance information were needed.


    You are right of course!

    I need 2 bits for the factor and 1 bit for the hidden bit. It was
    as conceptual typo :)

    Thanks a lot for your detailed answer.

    There is a lot of info there. I will read it again tomorrow.

    Thanks

    jacob
     
    jacob navia, Jan 3, 2010
    #4
  5. jacob navia

    Ben Pfaff Guest

    jacob navia <> writes:

    > Gene a écrit :
    >>
    >> I'm curious about "hidden" and "factor". Last time I implemented AVL
    >> trees, only 2 bits of balance information were needed.

    >
    > You are right of course!
    >
    > I need 2 bits for the factor and 1 bit for the hidden bit. It was
    > as conceptual typo :)


    What is the "hidden bit"?

    You can eliminate the "factor" field entirely by using a
    scapegoat tree, which doesn't have any per-node overhead at all.
    If you don't really need the "hidden bit" also, then you could
    get rid of those 8 bytes of overhead entirely.
    --
    "Your correction is 100% correct and 0% helpful. Well done!"
    --Richard Heathfield
     
    Ben Pfaff, Jan 3, 2010
    #5
  6. jacob navia

    jacob navia Guest

    Ben Pfaff a écrit :
    > jacob navia <> writes:
    >
    >> Gene a écrit :
    >>> I'm curious about "hidden" and "factor". Last time I implemented AVL
    >>> trees, only 2 bits of balance information were needed.

    >> You are right of course!
    >>
    >> I need 2 bits for the factor and 1 bit for the hidden bit. It was
    >> as conceptual typo :)

    >
    > What is the "hidden bit"?
    >


    A small "optimization", instead of erasing some data, I declare
    it "hidden", what saves for some time a tree reorganization.

    > You can eliminate the "factor" field entirely by using a
    > scapegoat tree, which doesn't have any per-node overhead at all.


    Yes, I know. They are a better data structure. They will be implemented
    later, probably before red/black trees

    > If you don't really need the "hidden bit" also, then you could
    > get rid of those 8 bytes of overhead entirely.


    That's a good point. AVL trees are widely used though, and I want
    to start this stuff with easy structures first, to better understand
    what I am doing.

    :)

    Thanks for your answer.
     
    jacob navia, Jan 3, 2010
    #6
  7. jacob navia

    jacob navia Guest

    remod a écrit :
    > jacob navia ha scritto:
    >> Yes, I know. They are a better data structure. They will be implemented
    >> later, probably before red/black trees

    >
    > Are you suggesting you will offer different data structures? If that's
    > the case I would be interested in understing the rationale behind your
    > choice.
    >


    AVL trees are very simple, and even if they need sme data per node, they
    offer a simple structure for small/medium size applications.

    > I'm working on a container library too


    This is strange, I have been discussing my container library in this
    discussion group since november if I remember well, and very often.
    It is the first time thatI hear about your project.

    I have published the interface and some code here.

    What do you think of it?

    Does your library follow those conventions too?


    > but I've decided to implement a
    > single data structure and support the key/value abstraction that is very
    > easy to use.
    >


    Yes, it is easy to use if your data has a key. I will implement that
    later, for data that has a key.

    > My intent is to create a library with dynamic structures that are as
    > simple to use as those offered by modern scripting languages.


    What do you understand by "dynamic"?

    > First
    > version of a program is (hopefully) quickly whipped up using that
    > library, than, if performance are an issue, the programmer could focus
    > on a more efficient data structure. My take is that more often than not,
    > the performance would be adequate for the task.
    >


    Well, the goal of my project is to get a STANDARD interface for
    containers in C, so that we could use a language-wide interface.

    I have discussed this at length in this forum. Maybe you can access
    my posts about it.


    > I'm currently using hash tables but I have considered (and I might
    > change to one of the) various types of balanced trees (I was considering
    > a treap or a scapegoat tree).
    >


    I am afraid that a songle structure can't be OK for ALL uses.

    I have implemented Strings, string collections, arraylists, hash tables,
    bitstrings, and now binary search trees. All those containers have
    different requirements and objectives.

    > The key point, though, is that the implementation of the container would
    > be hidden to the programmer using the library. He/she will just use the
    > API for Sets, Stacks, Queue, Vectors, etc without knowing how they are
    > implemented.


    My project will be open source with no copyright (no GPL either) so that
    anyone can use it, and adapt it as he/she sees fit. Nothing is hidden,
    but not all things are standardized. Actually, the objective is to
    propose an interface standard, and propose a sample implementation.

    >
    > PS: I sent a question on the lcc newsgroup, have you had the opportunity
    > of reading it?
    >


    Yes, but I was completely busy with the container stuff and could not do
    what you requested, sorry.
     
    jacob navia, Jan 3, 2010
    #7
  8. "jacob navia" <> wrote in message
    news:hhqth2$g3$...
    > jacob navia a écrit :
    > [snip]
    >
    > After posting that, I have just discovered that I can do the transition
    > between the smallish 65535 limited trees to the 32 bit ones AUTOMATICALLY!
    >
    > Since I keep the count of the elements in the tree header, when I arrive
    > at inserting the 65537th element I have just to change the POINTER of
    > the vtable to point to the vtable of the 32 bit version, reallocate the
    > nodes in 32 bits and go on!
    >
    > This is completely impossible to do in C++ since an object can't change
    > dynamically its class at runtime.


    And as far as I know, neither can a C structure variable.
    Is this an extension specific to lcc?

    Dennis
     
    Dennis \(Icarus\), Jan 3, 2010
    #8
  9. jacob navia <> writes:
    [...]
    > My project will be open source with no copyright (no GPL either) so that
    > anyone can use it, and adapt it as he/she sees fit. Nothing is hidden,
    > but not all things are standardized. Actually, the objective is to
    > propose an interface standard, and propose a sample implementation.

    [...]

    In other words, you want it to be public domain.

    My understanding is that, under most current copyright laws,
    anything you create is automatically copyrighted by default.
    To release it to the public domain, you have to say so explicitly.

    See, for example, <http://www.sqlite.org/copyright.html>. I presume
    they got it right. I am not a lawyer; please do not take my word
    on anything I say on this topic without checking elsewhere.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Jan 3, 2010
    #9
  10. jacob navia

    Stefan Ram Guest

    remod <> writes:
    >I'm working on a container library too but I've decided to implement a
    >single data structure and support the key/value abstraction that is very
    >easy to use.


    This is 2010. C is one of the most widespread programming
    languages, and containers (like AVL trees) are one of the
    most widespread entities in programming and known for
    decades now.

    Shouldn't there be a great choice of container libraries for
    C around already? What is the point in writing one's own
    instead of reusing someone else's container library?
     
    Stefan Ram, Jan 4, 2010
    #10
  11. jacob navia

    Stefan Ram Guest

    remod <> writes:
    >The Lua language, for example, has been very successful in using
    >hashtables as its single data container (actually a combination of a
    >vector and an hashtable). All the other data structures (trees, Queues,
    >lists, ...) can be implemented on top of Lua tables. I wanted to try to
    >do something similar for C


    It might turn out that the hard problem in C will be memory management.
    I read that Lua uses a garbage collector.

    http://lua-users.org/wiki/GarbageCollectionTutorial
     
    Stefan Ram, Jan 4, 2010
    #11
  12. jacob navia

    James Guest

    "jacob navia" <> wrote in message
    news:hhqs1k$u8c$...
    > Continuing the container library I have started the more complex
    > containers: trees.

    [...]

    FWIW, here is example code for the producer side of a hashed "trie" designed
    for holding unsigned integers that might be of interest you:


    http://groups.google.com/group/comp.programming/msg/339cd675b7894282
    (please read all...)
     
    James, Jan 4, 2010
    #12
  13. "jacob navia" <> wrote in message
    news:hhqs1k$u8c$...
    > Continuing the container library I have started the more complex
    > containers: trees.
    >
    > I implemented over the holidays the AVL trees in a small module of
    > around 600 lines. Obviously the bare minimum: insert/delete and
    > find. There is an equal method to compare two trees.


    [...]

    Be sure to check out Judy Arrays:

    http://judy.sourceforge.net




    Well, beware of patent:

    http://www.google.com/patents?id=0SYPAAAAEBAJ


    :^o
     
    Chris M. Thomasson, Jan 4, 2010
    #13
  14. On 3 Jan, 20:09, jacob navia <> wrote:
    > jacob navia a écrit :


    > After posting [about an implementaion of a tree], I have just discovered that I can do > the transition
    > between the smallish 65535 limited trees to the 32 bit ones AUTOMATICALLY!
    >
    > Since I keep the count of the elements in the tree header, when I arrive
    > at inserting the 65537th element I have just to change the POINTER of
    > the vtable to point to the vtable of the 32 bit version, reallocate the
    > nodes in 32 bits and go on!
    >
    > This is completely impossible to do in C++ since an object can't change
    > dynamically its class at runtime.


    nonsense. Anything you can do in C you can do in C++. You can't change
    types dynamically in either C or C++. You can change representaion in
    mid flow if you hide the implementation, in either language.

    [a real C++ version would be a template and pass reference parameters
    etc.]

    class GrowableTree
    {
    public:
    void add (Element*);
    /* etc. */

    private:
    Tree* pimpl_; /* the actual implementaion */
    int64 count_;
    };

    GrowableTree::add (Element* e)
    {
    if (count_ < 0xffff)
    pimpl->add(e);
    {
    // code probably not exception safe */
    Tree* new_tree = new Tree64();
    deep_copy (new_tree, pimpl_);
    delete pimpl_;
    pimpl_ = new_tree;
    }
    count_++;
    }


    > This idea has far reaching consequences for doing dynamically adaptive
    > data structures. I could start all containers in the "smallish" version,
    > and grow as needed.


    I bet this isn't original

    > What is interesting in the C version is that it is completely dynamic.
    > You can adapt the data structure to new conditions AS NEEDED, without
    > having to fix everything during the compilation.
    >
    > True, the insertion of the 65537th element will take some time... :)


    too true!

    > Happily for C++ users, the library will be available for them too.
    >
    > Just add the
    >
    > extern "C"
     
    Nick Keighley, Jan 4, 2010
    #14
  15. On Jan 4, 2:43 am, jacob navia <> wrote:
    > I implemented over the holidays the AVL trees in a small module of
    > around 600 lines. Obviously the bare minimum: insert/delete and
    > find. There is an equal method to compare two trees.


    Will you allow the caller to traverse through a subtree,
    coroutine style? (I mentioned "traverser structures" in a
    recent thread, though with little or no response.)

    > ...
    > What bothers me is the enormous overhead of the 64 bit pointers


    Assuming your users would be content even if the structure
    limits them to a mere quintillion nodes, then you *do* have
    "spare bits" in your 64-bit pointers; the problem is
    accessing them *portably* in C. For example, on *many*
    implementations your struct pointers will "smell like"
    char pointers but will have 2 low-order zero-bits.
    Surely I'm not the only one that would "want my cake and to
    eat it too" on such matters.

    James Dow Allen
     
    James Dow Allen, Jan 4, 2010
    #15
  16. jacob navia

    jacob navia Guest

    Nick Keighley a écrit :
    > On 3 Jan, 20:09, jacob navia <> wrote:
    >> jacob navia a écrit :

    >
    >> After posting [about an implementaion of a tree], I have just discovered that I can do > the transition
    >> between the smallish 65535 limited trees to the 32 bit ones AUTOMATICALLY!
    >>
    >> Since I keep the count of the elements in the tree header, when I arrive
    >> at inserting the 65537th element I have just to change the POINTER of
    >> the vtable to point to the vtable of the 32 bit version, reallocate the
    >> nodes in 32 bits and go on!
    >>
    >> This is completely impossible to do in C++ since an object can't change
    >> dynamically its class at runtime.

    >
    > nonsense. Anything you can do in C you can do in C++.


    No. In C++ you can't manipulate the vtable for an object...
    It is the compiler that manages it. You can't even access it.

    > You can't change
    > types dynamically in either C or C++.


    True. But in C you canchange the vtable for an object,
    what you can't do in C++.

    > You can change representaion in
    > mid flow if you hide the implementation, in either language.
    >
    > [a real C++ version would be a template and pass reference parameters
    > etc.]
    >
    > class GrowableTree
    > {
    > public:
    > void add (Element*);
    > /* etc. */
    >
    > private:
    > Tree* pimpl_; /* the actual implementaion */


    What is "Tree"???

    It points to a 64 bit or to a 32 or 16 bit Tree?
    They are different types!


    > int64 count_;
    > };
    >
    > GrowableTree::add (Element* e)
    > {
    > if (count_ < 0xffff)
    > pimpl->add(e);


    You are missing an "else" here I suppose...

    > {
    > // code probably not exception safe */
    > Tree* new_tree = new Tree64();


    The type of "Tree" pointer is not specified.
    It is a pointer to WHAT?


    > deep_copy (new_tree, pimpl_);
    > delete pimpl_;
    > pimpl_ = new_tree;
    > }
    > count_++;
    > }
    >
    >
    >> This idea has far reaching consequences for doing dynamically adaptive
    >> data structures. I could start all containers in the "smallish" version,
    >> and grow as needed.

    >
    > I bet this isn't original
    >



    You bet that I am always wrong Keighly. It is quite boring at the end.
    OK. You are right and I am wrong.

    happy?
     
    jacob navia, Jan 4, 2010
    #16
  17. jacob navia

    jacob navia Guest

    James Dow Allen a écrit :
    > On Jan 4, 2:43 am, jacob navia <> wrote:
    >> I implemented over the holidays the AVL trees in a small module of
    >> around 600 lines. Obviously the bare minimum: insert/delete and
    >> find. There is an equal method to compare two trees.

    >
    > Will you allow the caller to traverse through a subtree,
    > coroutine style? (I mentioned "traverser structures" in a
    > recent thread, though with little or no response.)
    >


    For all containers we have the "Apply" function:
    bool (*Apply)(<container ptr> ST,int (*Applyfn)(const void
    *data,void *arg),void *arg);

    In the "arg" function you pass an argument to the applied function.
    You can then, pass a structure pointer or whatever is needed.

    >> ...
    >> What bothers me is the enormous overhead of the 64 bit pointers

    >
    > Assuming your users would be content even if the structure
    > limits them to a mere quintillion nodes, then you *do* have
    > "spare bits" in your 64-bit pointers; the problem is
    > accessing them *portably* in C. For example, on *many*
    > implementations your struct pointers will "smell like"
    > char pointers but will have 2 low-order zero-bits.
    > Surely I'm not the only one that would "want my cake and to
    > eat it too" on such matters.
    >


    Interesting idea but surely not portable...
    In any case, what is my main objective is the INTERFACE as
    a method table. I am doing a sample implementation only,
    specialized implementations could be much more aggressive in
    their implementations for a specific machine environment.


    > James Dow Allen
     
    jacob navia, Jan 4, 2010
    #17
  18. jacob navia

    gwowen Guest

    On Jan 3, 8:09 pm, jacob navia <> wrote:

    > This is completely impossible to do in C++ since an object can't change
    > dynamically its class at runtime.


    Of course it can. Use the pimpl idiom (which is very similar to what
    you do in C). Your base class contains a pointer to an
    implementation, and the methods merely forward the calls. Need to
    change the object at runtime? Simply point to a different
    implementation.

    Jacob, you clearly know a lot about C, but a vast amount of what you
    assert about C++ is simply flat-out wrong.
     
    gwowen, Jan 4, 2010
    #18
  19. jacob navia

    jacob navia Guest

    gwowen a écrit :
    > On Jan 3, 8:09 pm, jacob navia <> wrote:
    >
    >> This is completely impossible to do in C++ since an object can't change
    >> dynamically its class at runtime.

    >
    > Of course it can. Use the pimpl idiom (which is very similar to what
    > you do in C). Your base class contains a pointer to an
    > implementation, and the methods merely forward the calls. Need to
    > change the object at runtime? Simply point to a different
    > implementation.
    >
    > Jacob, you clearly know a lot about C, but a vast amount of what you
    > assert about C++ is simply flat-out wrong.


    As far as I understood pimpl stuff it was a "handle", i.e. a way
    of hiding the implementation from other classes. There are restrictions
    (secific to C++) about virtual functions, etc. Maybe those handles could
    be used here, but my knowledge of C++ is surely not enough to see if
    they actualy can be used:

    In the code presented by keighley above, it was the base class that made
    the switch. In my example it would be the derived class that makes it.

    Maybe it could be done, let's say it can be done but it hasn't been done.

    As far as I know, this is not used in the STL...

    jacob
     
    jacob navia, Jan 4, 2010
    #19
  20. jacob navia

    gwowen Guest

    On Jan 4, 11:08 am, jacob navia <> wrote:
    > As far as I understood pimpl stuff it was a "handle", i.e. a way
    > of hiding the implementation from other classes.


    That's certainly its most common use...

    > There are restrictions (specific to C++) about virtual functions, etc.


    There are, but there's nothing stopping you using pimpl to
    (effectively) implement your own vtable.

    > Maybe it could be done, let's say it can be done but it hasn't been done.


    Correct (to the best of my knowledge).

    > As far as I know, this is not used in the STL...


    I don't know of any STL implementation that does it. One certainly
    could, there are very few constraints on the implementation details,
    besides some guarantees on algorithmic complexity (for example, there
    are some STL implementations that use different implementations for
    short and long strings, and flip between them if the string grows or
    shrinks too much)
     
    gwowen, Jan 4, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Nobody

    question on AVL trees

    Nobody, Dec 24, 2004, in forum: C++
    Replies:
    0
    Views:
    345
    Nobody
    Dec 24, 2004
  2. Paul Emmons

    AVL trees

    Paul Emmons, Jul 5, 2003, in forum: C Programming
    Replies:
    1
    Views:
    586
    Mike Wahler
    Jul 5, 2003
  3. Evangelista Sami

    question on avl trees

    Evangelista Sami, Nov 21, 2003, in forum: C Programming
    Replies:
    1
    Views:
    311
    Noah Roberts
    Nov 21, 2003
  4. ptrSriram

    Help : Merging Binary Search Trees

    ptrSriram, Dec 10, 2005, in forum: C Programming
    Replies:
    3
    Views:
    1,033
    Thad Smith
    Dec 12, 2005
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,148
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page