shared_ptr to object in stl set container?

newer
Boost matix question from a newbie

Galen

13 Dec 2011 13 Dec '11

3:23 a.m.

Hi, -- I'm trying to use shared_ptr in a stl set, but am having trouble with find() Any help? Documentation on this seems hard to find. -- Also, are the overloaded < and == useful or correct here? thanks! Output is: ------------------ 0 adding neighbor 1 0 adding neighbor 2 1 adding neighbor 0 2 adding neighbor 1 0's neighbors 1 has 1 neighbors 0 2 has 1 neighbors 1 NOT WORKING is 1 a neighbor of 0? 0 is 0 a neighbor of 1? 0 Code below: ------------------- #include<set> #include<iostream> #include using namespace std; //use typedef instead in actual code #define NodePtr boost::shared_ptr<Node> // TODO: should this extend shared_ptr? class Node { private: int id; set<NodePtr> neighbors; public: Node() { } Node(int newID) { id = newID; } ~Node() { } int getID() { return id; } int addNeighbor(NodePtr newNode) { int newID; newID = newNode->id; // if not already a neighbor, add if (!isNeighbor(newID)) neighbors.insert(newNode); } set<NodePtr> getNeighbors() { return neighbors; } bool isNeighbor(int searchID) { set<NodePtr>::iterator it; // check if this neighbor already in list NodePtr searchNode(new Node(searchID)); it = neighbors.find(searchNode); // if not found, add to neighbors if (it == neighbors.end()) { return false; } //else return true; } //overload == for find() bool operator== (NodePtr otherNode) { cout << "==: " << otherNode->id << " " << id << endl; return (otherNode->id == id); } //overload < in case we want to sort bool operator< (NodePtr otherNode) { return (id < otherNode->id); } }; int main() { // the nodes are pointers to Node objects NodePtr n0(new Node(0)); NodePtr n1(new Node(1)); NodePtr n2(new Node(2)); cout << n0->getID() << " adding neighbor " << n1->getID() << endl; n0->addNeighbor(n1); cout << n0->getID() << " adding neighbor " << n2->getID() << endl; n0->addNeighbor(n2); cout << n1->getID() << " adding neighbor " << n0->getID() << endl; n1->addNeighbor(n0); // cout << n2->getID() << " adding neighbor " << n0->getID() << endl; // n2->addNeighbor(n0); cout << n2->getID() << " adding neighbor " << n1->getID() << endl; n2->addNeighbor(n1); set<NodePtr> neighbors = n0->getNeighbors(); set<NodePtr>::iterator NB; int id = n0->getID(); cout << id << "'s neighbors" << endl; for (NB = neighbors.begin(); NB != neighbors.end() ; NB++) { set<NodePtr> neighborsList = (*NB)->getNeighbors(); cout << (*NB)->getID() << " has " << neighborsList.size() << " neighbors" << endl; cout << (*neighborsList.begin())->getID() << endl; } // http://www.engr.sjsu.edu/wbarrett/SortFind.htm cout << "NOT WORKING" << endl; cout << "is 1 a neighbor of 0? " << n0->isNeighbor(1) << endl; cout << "is 0 a neighbor of 1? " << n1->isNeighbor(0) << endl; }

Show replies by date

Rob Desbois

13 Dec 13 Dec

9:49 a.m.

On 13 December 2011 03:23, Galen wrote:

...

-- I'm trying to use shared_ptr in a stl set, but am having trouble with find() Any help? Documentation on this seems hard to find.

Firstly: http://www.boost.org/doc/libs/1_46_1/libs/smart_ptr/shared_ptr.htm#compariso... I know you are overloading the comparison operators for your particular shared_ptr, but you're doing so in a way that fundamentally changes what the comparison means - i.e. instead of NodePtr1 == NodePtr2 comparing pointers, as is default - and useful - for shared_ptr, you're making it compare the nodes. I understand why, but wouldn't recommend it. Secondly: http://www.boost.org/doc/libs/release/libs/ptr_container/ The ptr_container library excels at exactly this sort of usage, and allows for natural comparisons without you needing to hijack another type's operators. Your operators are likely not being called because they are of the incorrect signature. The type of a member equality operator should be as shown: struct Foo { bool operator==(const Foo& f) const; // this is the incorrect equivalent of your operator // bool operator==(Foo f); } The const parameter is the correct way to do it, but it is most likely the * method* not being const that prevents your operators from being invoked. All in all, I'd suggest replace the containers you have with boost::ptr_set<Node> and your life will be much easier :-) --rob -- Rob Desbois Blog: http://theotherbranch.wordpress.com/ "I disapprove of what you say, but I’ll defend to the death your right to say it", Voltaire

Nathan Ridge

10:06 a.m.

...

Your operators are likely not being called because they are of the incorrect signature. The type of a member equality operator should be as shown: struct Foo { bool operator==(const Foo& f) const;

// this is the incorrect equivalent of your operator // bool operator==(Foo f); }

The const parameter is the correct way to do it, but it is most likely the method not being const that prevents your operators from being invoked.

Actually, the reason the operator< is not being invoked is because the way it's defined, it compares a Node object to a NodePtr: class Node { ... bool operator<(NodePtr otherNode) { return (id < otherNode->id); } }; What you want is an operator< that compares a NodePtr to a NodePtr, because this is what set<NodePtr>::find() will call. This needs to be defined as a non-member function: bool operator<(NodePtr a, NodePtr b) { return a->getID() < b->getID(); } Having said that, Rob is right that using ptr_container is a better approach. Regards, Nate

Rob Desbois

12:40 p.m.

On 13 December 2011 10:06, Nathan Ridge wrote:

...

...
Your operators are likely not being called because they are of the incorrect signature.

...

Actually, the reason the operator< is not being invoked is because the way it's defined, it compares a Node object to a NodePtr:

Doh! I thought I had a feeling there was something more there :-( -- Rob Desbois Blog: http://theotherbranch.wordpress.com/ "I disapprove of what you say, but I’ll defend to the death your right to say it", Voltaire

Jeff Flinn

1 p.m.

Rob Desbois wrote:

...

On 13 December 2011 10:06, Nathan Ridge mailto:zeratul976@hotmail.com> wrote:

> Your operators are likely not being called because they are of the > incorrect signature. > > ... >

Actually, the reason the operator< is not being invoked is because the way it's defined, it compares a Node object to a NodePtr:

Doh! I thought I had a feeling there was something more there :-(

IMHO, a better approach may be to supply std::set's sort predicate rather than overloading global operator<(). There may be places where you want to compare NodePtr's with normal pointer comparison semantics. Jeff

Igor R

10:07 a.m.

...

-- I'm trying to use shared_ptr in a stl set, but am having trouble with find() Any help? Documentation on this seems hard to find.

-- Also, are the overloaded < and == useful or correct here?

No, std algorithms won't call your comparison operators, because those of boost::shared_ptr do not compare pointees. You can define in your cpp something like this (operator ==() is not needed for your particular case): namespace boost { template<class T> bool operator <(const shared_ptr<T> &lhs, const shared_ptr<T> &rhs) { if (!lhs && !rhs) return false; return *lhs < *rhs; } } Then move your operator <() out of Node class, and your programm will work.

Igor R

10:16 a.m.

...

template<class T> bool operator <(const shared_ptr<T> &lhs, const shared_ptr<T> &rhs) { if (!lhs && !rhs) return false; return *lhs < *rhs; } }

Sorry, I meant "if (!lhs || !rhs)".

Rob Desbois

12:52 p.m.

On 13 December 2011 10:07, Igor R wrote:

...

...
-- I'm trying to use shared_ptr in a stl set, but am having trouble with find() Any help? Documentation on this seems hard to find.

-- Also, are the overloaded < and == useful or correct here?

No, std algorithms won't call your comparison operators, because those of boost::shared_ptr do not compare pointees. You can define in your cpp something like this (operator ==() is not needed for your particular case):

operator<() is needed for set sorting, but he does need operator==() for the find() to work. namespace boost

...

{ template<class T> bool operator <(const shared_ptr<T> &lhs, const shared_ptr<T> &rhs) { if (!lhs && !rhs) return false; return *lhs < *rhs; } }

Then move your operator <() out of Node class, and your programm will work.

Your program might work, but anyone else who might include your operator<() definition in their own code will be extremely surprised when this doesn't work as expected: ASSERT_FALSE(shared_ptr<Foo>(new Foo()) == shared_ptr<Foo>(new Foo())); When I compare 2 pointers, smart or raw, I want to know if the pointers are equal not the subobjects. This is the reason I would strongly recommend not doing this, regardless of whether this code will be used by others or not. Follow POLS - Principle Of Least Surprise; to override the equality operator for all shared_ptr<> instances would be staggeringly surprising, but even for 1 is unexpected. A possible alternative, if you didn't wish to use boost::ptr_set for some reason, would be to provide your own less than comparator for the set type, though that still leaves you with the custom 'find' behaviour. For that you could use std::find_if, but it won't give you as good performance as set's own methods (linear vs. logarithmic IIRC). I guess another alternative would be a shared_ptr wrapper that does the dereferencing compare as you want, but that may prove tricky to do. I'd still recommend ptr_container. -- Rob Desbois Blog: http://theotherbranch.wordpress.com/ "I disapprove of what you say, but I’ll defend to the death your right to say it", Voltaire

Lars Viklund

1:38 p.m.

On Tue, Dec 13, 2011 at 12:52:33PM +0000, Rob Desbois wrote:

...

On 13 December 2011 10:07, Igor R wrote:

...
...
-- I'm trying to use shared_ptr in a stl set, but am having trouble with find() Any help? Documentation on this seems hard to find.

-- Also, are the overloaded < and == useful or correct here?

No, std algorithms won't call your comparison operators, because those of boost::shared_ptr do not compare pointees. You can define in your cpp something like this (operator ==() is not needed for your particular case):

operator<() is needed for set sorting, but he does need operator==() for the find() to work.

Sets do not "need" op<. The default comparator template argument is std::less<K>, which has a fallback implementation using op< for things not explicitly specialized. In any way, if you can change the type of the set, you can provide a custom comparator. std::set<K>::find doesn't use op==. It uses the comparator in a fashion akin to !(key_comp(a,b) || key_comp(b,a)), that is, if neither key is less than the other, it's by necessity equivalent. -- Lars Viklund | zao@acc.umu.se

Rob Desbois

4:28 p.m.

n 13 December 2011 13:38, Lars Viklund wrote:

...

On Tue, Dec 13, 2011 at 12:52:33PM +0000, Rob Desbois wrote:

...
On 13 December 2011 10:07, Igor R wrote:

...
...
-- I'm trying to use shared_ptr in a stl set, but am having trouble with find() Any help? Documentation on this seems hard to find.

-- Also, are the overloaded < and == useful or correct here?

No, std algorithms won't call your comparison operators, because those of boost::shared_ptr do not compare pointees. You can define in your cpp something like this (operator ==() is not needed for your particular case):

operator<() is needed for set sorting, but he does need operator==() for the find() to work.

Sets do not "need" op<. The default comparator template argument is std::less<K>, which has a fallback implementation using op< for things not explicitly specialized.

Apologies - what I meant included that, though was unclear.

...

std::set<K>::find doesn't use op==. It uses the comparator in a fashion akin to !(key_comp(a,b) || key_comp(b,a)), that is, if neither key is less than the other, it's by necessity equivalent.

Ah, I didn't know that, though it makes sense thinking about it. Thanks :-) -- Rob Desbois Blog: http://theotherbranch.wordpress.com/ "I disapprove of what you say, but I’ll defend to the death your right to say it", Voltaire

Igor R

4:42 p.m.

...

Your program might work, but anyone else who might include your operator<()> definition in their own code will be extremely surprised when this doesn't> work as expected:> ASSERT_FALSE(shared_ptr<Foo>(new Foo()) == shared_ptr<Foo>(new Foo()));>> When I compare 2 pointers, smart or raw, I want to know if the pointers are equal not the subobjects.

Well, I'd argue with the last sentence, but please note that I wasn't talking about operator == at all. I mentioned operator <, which is documented in shared_ptr as follows: "Returns: an unspecified value such that operator< is a strict weak ordering as described in section 25.3 [lib.alg.sorting] of the C++ standard; under the equivalence relation defined by operator<, !(a < b) && !(b < a), two shared_ptr instances are equivalent if and only if they share ownership or are both empty. Throws: nothing." So as long as operator< implements strict weak ordering, it's fine.

Rob Desbois

5:01 p.m.

On 13 December 2011 16:42, Igor R wrote:

...

...
Your program might work, but anyone else who might include your operator<()> definition in their own code will be extremely surprised when this doesn't> work as expected:> ASSERT_FALSE(shared_ptr<Foo>(new Foo()) == shared_ptr<Foo>(new Foo()));>> When I compare 2 pointers, smart or raw, I want to know if the pointers are equal not the subobjects.

Well, I'd argue with the last sentence, but please note that I wasn't talking about operator == at all. I mentioned operator <, which is documented in shared_ptr as follows:

Well..the last sentence was my personal opinion so I'm quite confident in it ;-) I realised in my previous response that set::find() wouldn't need operator==, so my quote above is probably not so relevant now. As for operator<() comparisons - I don't expect I would want that comparison for pointers so a 'hijacking' of it through a global (or at least ADL-findable) operator<() is less relevant. As Lars points out though, the comparator can be provided as part of the set<> type, which is a much nicer means of providing the compare operation.

...

"Returns: an unspecified value such that operator< is a strict weak ordering as described in section 25.3 [lib.alg.sorting] of the C++ standard; under the equivalence relation defined by operator<, !(a < b) && !(b < a), two shared_ptr instances are equivalent if and only if they share ownership or are both empty. Throws: nothing." So as long as operator< implements strict weak ordering, it's fine.

The important point here IMO is that comparison is based on shared ownership. If that is the case, then Galen's implementation of isNeighbor() won't work as it's not based on ownership comparison but pointee comparison. -- Rob Desbois Blog: http://theotherbranch.wordpress.com/ "I disapprove of what you say, but I’ll defend to the death your right to say it", Voltaire

4821

Age (days ago)

4821

Last active (days ago)

List overview

Download

11 comments

6 participants

participants (6)

Galen
Igor R
Jeff Flinn
Lars Viklund
Nathan Ridge
Rob Desbois