can std::set hold pointers to keys instead of the keys themselves?

Discussion in 'C++' started by danibe@my-deja.com, Dec 17, 2005.

  1. Guest

    I never had any problems storing pointers in STL
    containers such std::vector and std::map. The benefit
    of storing pointers instead of the objects themselves
    is mainly saving memory resources and performance (STL
    containers hold *copies* of what's passed to them via
    the insert() method).

    However, I am not sure how to accomplish that using
    std::set. For various reasons, I cannot use vector or
    map in my application. But I would like to use the
    same optimization I have always used with STL
    containers, which is letting them store pointers to
    the items, not the items themselves.

    In particular, the following code snippet compiles and
    works beautifully (albeit no so efficient):

    ================ WORKING CODE SNIPPET ================
    typedef std::set<CItemKey, std::less<CItemKey> > TItemKeys;
    typedef TItemKeys::const_iterator TItemKeysConstIterator;
    typedef TItemKeys::iterator TItemKeysIterator;

    TItemKeys m_items;

    const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    {
    TItemKeysConstIterator it = m_items.find(rItemKey);

    if (it != m_items.end())
    return static_cast<const CItem*>(it->getOwner());
    else
    return (NULL);
    }
    ======================================================


    However, when I modify this to be pointer based
    (notice the subtle difference), it does not even
    compile! It fails on the find() statement for
    inability to convert the type of the parameter (or the
    return value):

    ================ WORKING CODE SNIPPET ================
    typedef std::set<CItemKey*, std::less<CItemKey> > TItemKeys;
    typedef TItemKeys::const_iterator TItemKeysConstIterator;
    typedef TItemKeys::iterator TItemKeysIterator;

    TItemKeys m_items;

    const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    {
    TItemKeysConstIterator it = m_items.find(rItemKey);

    if (it != m_items.end())
    return static_cast<const CItem*>(it->getOwner());
    else
    return (NULL);
    }
    ======================================================

    What am I doing wrong?

    I also tried modifying m_items.find(rItemKey) to
    m_items.find(&rItemKey) but that doesn't help either.
    Obviously I ran into a mental block here.

    Is there a way to accomplish what I am trying to
    achieve (storing pointers in a set)? Or is this
    fundamentally incorrect, as set by definition must
    contain keys, not pointers to keys?

    Thanks.
     
    , Dec 17, 2005
    #1
    1. Advertising

  2. wrote:
    > [..]
    > However, when I modify this to be pointer based
    > (notice the subtle difference), it does not even
    > compile! It fails on the find() statement for
    > inability to convert the type of the parameter (or the
    > return value):
    >
    > ================ WORKING CODE SNIPPET ================


    Did you mean "NON-WORKING CODE SNIPPET"?


    > typedef std::set<CItemKey*, std::less<CItemKey> > TItemKeys;
    > typedef TItemKeys::const_iterator TItemKeysConstIterator;
    > typedef TItemKeys::iterator TItemKeysIterator;
    >
    > TItemKeys m_items;
    >
    > const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    > {
    > TItemKeysConstIterator it = m_items.find(rItemKey);


    The trick is that you're looking for the element in 'm_items' that
    _points_ to the same _value_ as 'rItemKey', but 'find' only looks
    for the same _pointer_. Changing it to

    TItemKeysConstIterator it = m_items.find(&rItemKey);

    should help it compile, but I don't see it work very well because
    the item you pass will very unlikely have the same address as any
    item in the set.

    You probably want to use 'std::find' with your own, custom predicate
    that will dereference the pointer and compare it to the value you
    need.

    > if (it != m_items.end())
    > return static_cast<const CItem*>(it->getOwner());
    > else
    > return (NULL);
    > }
    > ======================================================
    >
    > What am I doing wrong?
    >
    > I also tried modifying m_items.find(rItemKey) to
    > m_items.find(&rItemKey) but that doesn't help either.


    Doesn't help in what way? Does it compile?

    > Obviously I ran into a mental block here.
    >
    > Is there a way to accomplish what I am trying to
    > achieve (storing pointers in a set)? Or is this
    > fundamentally incorrect, as set by definition must
    > contain keys, not pointers to keys?


    Well, you're twisting the definition. Your set doesn't contain
    _pointers_to_keys_. It contains _pointers_. They are both values
    and keys. Now, if you had some kind of custom comparator to make
    your stored values compared with dereferencing, then you might get
    closer to achieving what you want. Look at the second template
    argument for std::set.

    V
     
    Victor Bazarov, Dec 17, 2005
    #2
    1. Advertising

  3. Kai-Uwe Bux Guest

    wrote:

    > I never had any problems storing pointers in STL
    > containers such std::vector and std::map. The benefit
    > of storing pointers instead of the objects themselves
    > is mainly saving memory resources and performance (STL
    > containers hold *copies* of what's passed to them via
    > the insert() method).
    >
    > However, I am not sure how to accomplish that using
    > std::set. For various reasons, I cannot use vector or
    > map in my application. But I would like to use the
    > same optimization I have always used with STL
    > containers, which is letting them store pointers to
    > the items, not the items themselves.
    >
    > In particular, the following code snippet compiles and
    > works beautifully (albeit no so efficient):
    >
    > ================ WORKING CODE SNIPPET ================
    > typedef std::set<CItemKey, std::less<CItemKey> > TItemKeys;
    > typedef TItemKeys::const_iterator TItemKeysConstIterator;
    > typedef TItemKeys::iterator TItemKeysIterator;
    >
    > TItemKeys m_items;
    >
    > const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    > {
    > TItemKeysConstIterator it = m_items.find(rItemKey);
    >
    > if (it != m_items.end())
    > return static_cast<const CItem*>(it->getOwner());
    > else
    > return (NULL);
    > }
    > ======================================================
    >
    >
    > However, when I modify this to be pointer based
    > (notice the subtle difference), it does not even
    > compile! It fails on the find() statement for
    > inability to convert the type of the parameter (or the
    > return value):
    >
    > ================ WORKING CODE SNIPPET ================
    > typedef std::set<CItemKey*, std::less<CItemKey> > TItemKeys;


    You are using a comparison function that produces a type mismatch. Either
    use std::less<T*> or something like

    pointee_comapare ( CItemKey const * a, CItemKey const b * b ) {
    return (*a) < (*b);
    }

    > typedef TItemKeys::const_iterator TItemKeysConstIterator;
    > typedef TItemKeys::iterator TItemKeysIterator;
    >
    > TItemKeys m_items;
    >
    > const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    > {
    > TItemKeysConstIterator it = m_items.find(rItemKey);
    >
    > if (it != m_items.end())
    > return static_cast<const CItem*>(it->getOwner());
    > else
    > return (NULL);
    > }
    > ======================================================
    >
    > What am I doing wrong?
    >
    > I also tried modifying m_items.find(rItemKey) to
    > m_items.find(&rItemKey) but that doesn't help either.
    > Obviously I ran into a mental block here.
    >
    > Is there a way to accomplish what I am trying to
    > achieve (storing pointers in a set)? Or is this
    > fundamentally incorrect, as set by definition must
    > contain keys, not pointers to keys?


    A map can contain pointers. However, recall that a std::map<T> uses
    std::less<T> to keep the entries sorted for fast retrieval. If you use
    std::map<T*> instead, the comparison predicate used by default will compare
    the pointers not the pointees. If you want to use the pointers just for
    efficiency, this will not be what you want. Instead, you need to provide
    your own comparison function instead of std::less<T*> that forwards the
    comparison to the pointees.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Dec 17, 2005
    #3
  4. Guest

    Victor Bazarov wrote:
    > Did you mean "NON-WORKING CODE SNIPPET"?

    Yes. Sorry for the typo. The second code snippet is the non-working
    one.


    > The trick is that you're looking for the element in 'm_items' that
    > _points_ to the same _value_ as 'rItemKey', but 'find' only looks
    > for the same _pointer_. Changing it to
    >
    > TItemKeysConstIterator it = m_items.find(&rItemKey);
    >
    > should help it compile, but I don't see it work very well because
    > the item you pass will very unlikely have the same address as any
    > item in the set.


    You are right and I knew that even before the change. However, since I
    am not that proficient in STL, I wanted first to make it compile and
    then take care of correct comaprison function.

    Right now I cannot decipher the cryptic compilaation error messages
    that VC++ gives me.

    It says:

    ============ START QUOTE ================
    'class std::_Tree<class CItemKey *,
    class CItemKey *,
    struct std::set<class CItemKey *,
    struct std::less<class CItemKey *>,
    class std::allocator<class CItemKey *> >::_Kfn,
    struct std::less<class CItemKey *>,
    class std::allocator<class CItemKey *> >::const_iterator __thiscall
    std::set<class CItemKey *,
    struct std::less<class CItemKey *>,
    class std::allocator<class CItemKey *> >::find(class CItemKey *const &
    ) const' :


    cannot convert parameter 1 from 'const class CItemKey *' to 'class
    CItemKey *const & '

    Reason: cannot convert from 'const class CItemKey *' to 'class
    CItemKey *const '
    Conversion loses qualifiers
    ============ END QUOTE ================

    Obviously there is a constness problem here, but I don't understand
    where a conversion from 'const CItemKey *' to 'CItemKey *const' was
    attempted.
     
    , Dec 18, 2005
    #4
  5. Guest

    wrote:
    > Obviously there is a constness problem here, but I don't understand
    > where a conversion from 'const CItemKey *' to 'CItemKey *const' was
    > attempted.


    OK - I found the problem:

    All I had to do to make the set::find() call compile was to cast the
    parameter "properly". The resulting compilable code looks like this:

    ================= START QUOTE =============
    const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    {
    CItemKey* const pItemKeyToFind =
    const_cast<CItemKey* const>(&rItemKey);

    TItemKeysConstIterator it = m_items.find(pItemKeyToFind);

    (*it)->getContainer();

    if (it != m_items.end())
    return static_cast<const CItem*>((*it)->getOwner());
    else
    return (NULL);
    }
    ================= END QUOTE =============

    I now have to take care of handling the comparison correctly (so that
    it it doesn't compare pointers but pointees).

    My only confusion now is why is the cast needed? That is, why was
    set::find() implemented in such a way that it would require a
    <CItemKey* const> as a parameter, while <const CItemKey* const> simply
    would not compile?

    This is especially baffling in light of the fact that set::find is
    declared as follows:

    const_iterator find(const Key& key) const;

    which means that the both the item and what points to it are const. Or
    am I missing something here?
     
    , Dec 18, 2005
    #5
  6. > My only confusion now is why is the cast needed? That is, why was
    > set::find() implemented in such a way that it would require a
    > <CItemKey* const> as a parameter, while <const CItemKey* const> simply
    > would not compile?
    >
    > This is especially baffling in light of the fact that set::find is
    > declared as follows:
    >
    > const_iterator find(const Key& key) const;
    >
    > which means that the both the item and what points to it are const. Or
    > am I missing something here?


    The problem with the `const` qualifier is that it applies to what is
    written to the _left_. For example:

    int * const i; // A constant pointer to non-constant int
    int const * j; // A non-constant pointer to constant int
    int const * const k; // Everything is constant

    The only exception to this is when `const` is the leftmost word. In
    effect `const int *` is the same as `int const *`.

    Now when you take a look at the type of `find` method's first parameter,
    you see it is `const Key &`. By applying the above rule, this is
    equivalent to `Key const &`. When the template gets specialized, it
    changes to `CItemKey * const &`. That's why you cannot pass `const
    CItemKey *`, the types are not compatible.

    I believe that instead of casting away constness, you should change the
    template parameter to `const CItemKey *` like this:

    typedef std::set<const CItemKey *> ItemKeys;

    > I now have to take care of handling the comparison correctly (so that
    > it it doesn't compare pointers but pointees).


    You can do that by writing your own comparison function and use it
    instead of `std::less`. For example:

    bool MyLess(const CItemKey * x, const CItemKey * y)
    {
    return (*x) < (*y);
    }

    typedef std::set<const CItemKey *, MyLess> ItemKeys;

    I hope this was helpful.
    Martin.
     
    Martin Vejnar, Dec 18, 2005
    #6
  7. Axter Guest

    wrote:
    > I never had any problems storing pointers in STL
    > containers such std::vector and std::map. The benefit
    > of storing pointers instead of the objects themselves
    > is mainly saving memory resources and performance (STL
    > containers hold *copies* of what's passed to them via
    > the insert() method).
    >
    > However, I am not sure how to accomplish that using
    > std::set. For various reasons, I cannot use vector or
    > map in my application. But I would like to use the
    > same optimization I have always used with STL
    > containers, which is letting them store pointers to
    > the items, not the items themselves.
    >
    > In particular, the following code snippet compiles and
    > works beautifully (albeit no so efficient):
    >
    > ================ WORKING CODE SNIPPET ================
    > typedef std::set<CItemKey, std::less<CItemKey> > TItemKeys;
    > typedef TItemKeys::const_iterator TItemKeysConstIterator;
    > typedef TItemKeys::iterator TItemKeysIterator;
    >
    > TItemKeys m_items;
    >
    > const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    > {
    > TItemKeysConstIterator it = m_items.find(rItemKey);
    >
    > if (it != m_items.end())
    > return static_cast<const CItem*>(it->getOwner());
    > else
    > return (NULL);
    > }
    > ======================================================
    >
    >
    > However, when I modify this to be pointer based
    > (notice the subtle difference), it does not even
    > compile! It fails on the find() statement for
    > inability to convert the type of the parameter (or the
    > return value):
    >
    > ================ WORKING CODE SNIPPET ================
    > typedef std::set<CItemKey*, std::less<CItemKey> > TItemKeys;
    > typedef TItemKeys::const_iterator TItemKeysConstIterator;
    > typedef TItemKeys::iterator TItemKeysIterator;
    >
    > TItemKeys m_items;
    >
    > const CItem* CContainer::getItem(const CItemKey& rItemKey) const
    > {
    > TItemKeysConstIterator it = m_items.find(rItemKey);
    >
    > if (it != m_items.end())
    > return static_cast<const CItem*>(it->getOwner());
    > else
    > return (NULL);
    > }
    > ======================================================
    >
    > What am I doing wrong?
    >
    > I also tried modifying m_items.find(rItemKey) to
    > m_items.find(&rItemKey) but that doesn't help either.
    > Obviously I ran into a mental block here.
    >
    > Is there a way to accomplish what I am trying to
    > achieve (storing pointers in a set)? Or is this
    > fundamentally incorrect, as set by definition must
    > contain keys, not pointers to keys?
    >
    > Thanks.


    Consider using a smart pointer that uses value semantic.
    Example:
    http://code.axter.com/copy_ptr.h

    The above smart pointer uses value semantic instead of poitner
    semantic, so when a comparison is performed, it compares the object
    instead of the address of the pointer.
    The copy_ptr works great with std::set.
    You can also use the following COW pointer which also uses value
    semantics:
    http://code.axter.com/cow_ptr.h
     
    Axter, Dec 18, 2005
    #7
  8. Guest

    Martin Vejnar wrote:
    > I hope this was helpful.


    Yes, thank you - it was very helpful.

    > I believe that instead of casting away constness, you should change the
    > template parameter to `const CItemKey *` like this:
    >
    > typedef std::set<const CItemKey *> ItemKeys;
    >


    But that means that the items stored (not the pointers to them) are
    const, right? If so, this is not what I need. I need a container
    (std::set in this case) that stores modifiable items.

    > You can do that by writing your own comparison function and use it
    > instead of `std::less`. For example:
    >
    > bool MyLess(const CItemKey * x, const CItemKey * y)
    > {
    > return (*x) < (*y);
    > }
    >
    > typedef std::set<const CItemKey *, MyLess> ItemKeys;
    >


    I used a function object for that purpose (works beautifuly). Is there
    a fundamental difference between your approach and the function object
    approach?

    Thanks.
     
    , Dec 20, 2005
    #8
  9. wrote:
    > Martin Vejnar wrote:
    >>I believe that instead of casting away constness, you should change the
    >>template parameter to `const CItemKey *` like this:
    >>
    >> typedef std::set<const CItemKey *> ItemKeys;
    >>

    >
    >
    > But that means that the items stored (not the pointers to them) are
    > const, right? If so, this is not what I need. I need a container
    > (std::set in this case) that stores modifiable items.
    >


    You shouldn't modify keys of sortable containers. If you do so, the
    `std::set` will no longer be sorted correctly. If you need to change a
    value in `std::set` you must `erase` and re-`insert` it. But if you just
    want to store key-value pairs you're better off using `std::map`.

    >
    >>You can do that by writing your own comparison function and use it
    >>instead of `std::less`. For example:
    >>
    >> bool MyLess(const CItemKey * x, const CItemKey * y)
    >> {
    >> return (*x) < (*y);
    >> }
    >>
    >> typedef std::set<const CItemKey *, MyLess> ItemKeys;
    >>

    >
    > I used a function object for that purpose (works beautifuly). Is there
    > a fundamental difference between your approach and the function object
    > approach?
    >


    Fundamental difference? I have no idea.

    Martin.
     
    Martin Vejnar, Dec 20, 2005
    #9
  10. Guest

    Martin Vejnar wrote:
    > You shouldn't modify keys of sortable containers. If you do so, the
    > `std::set` will no longer be sorted correctly. If you need to change a
    > value in `std::set` you must `erase` and re-`insert` it.


    You are right. I overlooked this point. Thanks for clarifying this
    issue for me.
    (fortunately I haven't reached a case in which I need to modify those
    key objects while in the container, but if I do, I will make sure that
    I do it the way you outlined).

    > >>You can do that by writing your own comparison function and use it
    > >>instead of `std::less`. For example:
    > >>
    > >> bool MyLess(const CItemKey * x, const CItemKey * y)
    > >> {
    > >> return (*x) < (*y);
    > >> }
    > >>
    > >> typedef std::set<const CItemKey *, MyLess> ItemKeys;
    > >>

    > >
    > > I used a function object for that purpose (works beautifuly). Is there
    > > a fundamental difference between your approach and the function object
    > > approach?
    > >

    >
    > Fundamental difference? I have no idea.
    >


    This is what I did:
    class CItemKeyPtrLess
    {
    public:
    bool operator()(const CItemKey* const pKeyA,
    const CItemKey* const pKeyB) const
    {
    return (*pKeyA) < (*pKeyB);
    }
    };

    (I know I could have used a struct there, but I preferred sticking to
    the textbook (by Leen Ammeraal).

    I am curious to know whether there is an advantage of using either way.
     
    , Dec 20, 2005
    #10
  11. Daniel T. Guest

    In article <>,
    wrote:

    > Martin Vejnar wrote:
    > > You shouldn't modify keys of sortable containers. If you do so, the
    > > `std::set` will no longer be sorted correctly. If you need to change a
    > > value in `std::set` you must `erase` and re-`insert` it.

    >
    > You are right. I overlooked this point. Thanks for clarifying this
    > issue for me.
    > (fortunately I haven't reached a case in which I need to modify those
    > key objects while in the container, but if I do, I will make sure that
    > I do it the way you outlined).
    >
    > > >>You can do that by writing your own comparison function and use it
    > > >>instead of `std::less`. For example:
    > > >>
    > > >> bool MyLess(const CItemKey * x, const CItemKey * y)
    > > >> {
    > > >> return (*x) < (*y);
    > > >> }
    > > >>
    > > >> typedef std::set<const CItemKey *, MyLess> ItemKeys;
    > > >>
    > > >
    > > > I used a function object for that purpose (works beautifuly). Is there
    > > > a fundamental difference between your approach and the function object
    > > > approach?
    > > >

    > >
    > > Fundamental difference? I have no idea.
    > >

    >
    > This is what I did:
    > class CItemKeyPtrLess
    > {
    > public:
    > bool operator()(const CItemKey* const pKeyA,
    > const CItemKey* const pKeyB) const
    > {
    > return (*pKeyA) < (*pKeyB);
    > }
    > };
    >
    > (I know I could have used a struct there, but I preferred sticking to
    > the textbook (by Leen Ammeraal).
    >
    > I am curious to know whether there is an advantage of using either way.


    Your way may be slightly faster than using the pointer to function
    because yours is more likely to be inlined. The speed difference is
    probably nothing you would ever notice though.


    --
    Magic depends on tradition and belief. It does not welcome observation,
    nor does it profit by experiment. On the other hand, science is based
    on experience; it is open to correction by observation and experiment.
     
    Daniel T., Feb 3, 2006
    #11
    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.

Share This Page