Using pointers to elements of STL containers in my code?

Question

Is it a good idea/style to store elements of some class in an standard container, and then have some other classes store pointers to them?

Let's say I have class A and a std::set<A>. I then create class B that has an A* member, and that pointer points to some A in the set. Is this guaranteed to work in the standard library? What about std::map, std::unordered_set and std::unordered_map?

For example:

class A {};
std::set<A> set; //then fill with some elements

class B{
    A* a;
};

B b;
B.a = &(*set.begin());

What would be the better option? Perhaps storing pointers to a class inside the STL container? I like the current approach because I don't have to care about deleting the elements myself. — DiplomateProgrammer
– DiplomateProgrammer, Commented Jan 2, 2021 at 16:58
This is a super bad idea, because all of your A objects are owned by the std::set<A>. You're going to run into nightmares of dangling pointers and use after frees. What you should do is instead use a std::set<std::shared_ptr<A>> and create the A objects separately. Then you can pass around std::shared_ptr<A> as you need. — Tumbleweed53
– Tumbleweed53, Commented Jan 2, 2021 at 17:01
@Bathsheba Rebalancing of the RBTree has no effect on validity of pointers to the elements. — eerorika
– eerorika, Commented Jan 2, 2021 at 17:35
@Tumbleweed53 There are operations where the iterators are invalidated without invalidating the pointers. On top of that, iterators expose your implementation. It comes with advantages and disadvantages. — JVApen
– JVApen, Commented Jan 2, 2021 at 18:26
I'm not sure that an iterator does give you more security, it doesn't nullify if you remove the element, at best it has some assertions in a development build. You would be better off with address sanitizer. The shared_ptrs can share ownership, however it can extend life time for good and for worse with all consequences. Both approaches can be appropriate and both cause issues. — JVApen
– JVApen, Commented Jan 2, 2021 at 20:57

JVApen · Accepted Answer · 2021-01-02 18:20:02Z

3

On doubt it's a good idea to check the documentation.

For example for std::set: insert

No iterators or references are invalidated. If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid. (since C++17)

Similar can be read for erase:

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

So from this (and the docs for the other functions) it's safe to conclude that references (and pointers to the elements) are OK to be used as long as you don't erase the element from the set.

If we check the same for unordered_set: insert:

If rehashing occurs due to the insertion, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated. Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count(). If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid. (since C++17)

And the same for erase:

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

So also here we can conclude that taking the pointer to the element should be safe as long as the element is stored inside of the unordered_set.

I'll leave the unordered_map to you to validate, however as std::unordered_set is a special case of std::unordered_map without having a value, I expect it to behave similar.

EDIT: wether it's a good idea or not is hard to say. The containers come with guarantees and requirements. If these match your use case, it's worth trying it. From my experience I would recommend encapsulating these kind of things in some class with a specific name and expose the things you need to use. That way, if you decide to change the implementation, you know what you provide and what ain't a requirement.

edited Jan 2, 2021 at 18:20

answered Jan 2, 2021 at 17:14

JVApen

11.5k5 gold badges37 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

DiplomateProgrammer Over a year ago

Thank you, it seems it's indeed going to work. However, I was also wondering about whether it's a good idea/pattern overall. Do you have any thoughts?

JVApen Over a year ago

It is a pattern I've already used in production code. It ain't a golden bullet, though it solves some problems. If you encapsulate it in a class, you can always change the implementation afterwards. I would say: try it, if you at a point get stuck you can always refactor to something else.

eerorika · Accepted Answer · 2021-01-02 17:44:02Z

Is this guaranteed to work in STL?

Your example container is empty, so behaviour of indirecting through the iterator is undefined. If that weren't the case, the program would work.

I was also wondering about whether it's a good idea/pattern overall.

One challenge is that the lifetime of the pointed object is not bound to the pointer and the pointer can be invalidated. As such, you need to be very careful to make sure that the pointer will not be used once it becomes invalid.

This can easily be solved by using shared pointers at the cost of some overhead.

What about map, unordered_set and unordered_map?

This works with all container classes.

It varies between container classes which operations invalidate pointers to elements.

All these mentioned containers are node based data structures. Pointers (references) to their elements are invalidated only when the pointed element is erased. Other containers have stricter conditions.

Collectives™ on Stack Overflow

Using pointers to elements of STL containers in my code?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related