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

[danibe]

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.

 

[Victor Bazarov]

[..]
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

 

[Kai-Uwe Bux]

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

 

[danibe]

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.

 

[danibe]

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?

 

[Martin Vejnar]

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:

> 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.

 

[Axter]

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

 

[danibe]

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.

 

[Martin Vejnar]

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`.

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.

 

[danibe]

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).

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.

 

[Daniel T.]

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).


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.