CODEWITHSUNDEEP
c++stl
DiplomateProgrammer
DiplomateProgrammer

Reputation: 179

Using pointers to elements of STL containers in my code?

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());

Upvotes: 3

Views: 275

Answers (2)

JVApen
JVApen

Reputation: 11317

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.

Upvotes: 3

eerorika
eerorika

Reputation: 238461

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.

Upvotes: 1

Related Questions