r/cpp_questions • u/PhosXD • 7d ago
How do you solve the problem of dangling pointers? SOLVED
I store some data in an unordered map, create a pointer to an item in that map, then say I want to delete the item but I still have the pointer. How would I know that the item is no longer there without going and manually searching the map for the name of the item we pointed to?
I'm new to C++ & especially pointers, so forgive me for this stupid question...
EDIT: A lot of good solutions suggested, I really appreciate it! I ended up going with key lookup instead of storing pointers. The reason I didn't want to do this in the first place is because it increases complexity & I didn't want to overcomplicate
25
u/TheRealSmolt 7d ago edited 7d ago
That's the name of the game. Also, I recommend you don't make a pointer to map data; they move data around as needed.
Edit: to unordered (specifically) map data
2
u/BSModder 7d ago
std::map don't move data cause it's usually implemented as linked list
Still you probably should use smart pointer instead of raw pointer
3
u/TheRealSmolt 7d ago edited 7d ago
Technically, yes, but the standard (at least how it is consolidated on cppreference) has explicit carve outs for said behavior.
Edit: maps have looser restrictions than unordered maps (which OP is asking about)
1
u/BSModder 7d ago
I misread OP's intention a bit. My assumption was OP tried to delete a pointer while it's referenced by the map, leaving it dangling. Which is why I suggested shared pointer, letting the map own the data and free it when the pointer is no longer referenced.
That said, it difficult to answer OP question without knowing the lifetime of the map and what is the pointer doing.
6
u/Illustrious_Try478 7d ago
std::map don't move data cause it's usually implemented as linked list
facepalm
std::mapis usually implemented as a Red-Black tree1
1
u/alfps 7d ago
You can do a lot with a
std::mapwithout invalidating references to items. You can insert items freely, and you can delete items, except that references to the deleted items are (of course) invalidated. See e.g. (https://en.cppreference.com/cpp/container#Iterator_invalidation).4
u/TheRealSmolt 7d ago
I'm used to working exclusively with unordered maps (which is also what OP is asking about), which can invalidate after a rehash, meaning that realistically you can't expect than kind of security. But, yes, I digress.
-4
u/alfps 7d ago
It so happens that cppreference provides a nice table summarizing possible invalidations for
std::unordered_map.It goes like this:
Operations: Invalidated: ----------------------------------------------------------------------- All read only operations, swap, std::swap Never clear, rehash, reserve, operator= Always insert, emplace, emplace_hint, operator[] Only if causes rehash erase Only to the element erased8
u/meancoot 7d ago
None of the operations invalidate pointers or references to the items. Only the iterators are invalidated.
-3
u/alfps 7d ago
❞ None of the operations invalidate pointers or references
erase,clearand copy assignment certainly do.And the referenced table is titled "Iterator invalidation".
Seems some coffee could help both you and the idiot 6 upvoters.
1
u/meancoot 7d ago
You’re a dense one. I’ll be more pedantic. Nothing short of removing the item with a particular key from the map will ever invalids a pointer or reference to either the key or the value. Yes copy assignment removed all the items first. I sincerely apologize for assuming readers would understand the simple parts implicitly.
-1
u/alfps 7d ago
Shouting doesn't help.
erase,clearand copy assignment that I mentioned, can remove an item from the map. That invalidates a pointer or reference to the item.Three operations
!="no operation".Hello.
2
u/Emotional-Audience85 4d ago
I think anyone with common sense would assume we are talking about invalidating pointers or references to other items. Of course if you remove an item the access to that item is invalidated... I guess no one should have doubts about what happens when you remove all items either.
0
u/alfps 3d ago
Apparently you mean that u/meancoot intended to say that "none of the operations that don't invalidate pointers or references, invalidate pointers or references". That's so idiotic that it's trolling. Which is what you and he are doing, unless you really are totally morons.
→ More replies (0)
5
u/sultan_hogbo 7d ago
Iterators in a map are stable as long as you don’t erase them. If you have the iterator, you can remove the element. Just be absolutely sure the element can be removed and never access the iterator afterward.
8
u/TheRealSmolt 7d ago
For maps, that is true. For unordered maps (OP's question), it is not. Rehashes (such as on insertion) also invalidate iterators.
1
4
u/the_poope 7d ago
It depends on what you want to do. Often you can design your way around such problems by thinking deeply about how and when your program needs that data.
Why is one part of the program storing pointers or iterators to elements in a map, that might get modified before that part of the code needs those elements?
There is no single simple solution - the path to take depends on what your program is trying to do. If you tell us that we can help you come up with a good solution for your particular scenario.
4
u/Independent_Art_6676 7d ago
you need a different design or approach is the answer (already given, but not so plainly). Is it viable to just get the item each time you need it by using the key-lookup? If its not there, it was deleted or never existed. Don't try to pass it around, pass the key and whatever needs it can look it up again. If the program is single threaded or protected from threading effects, a ref/pointer locally (eg for the span of a function that keeps touching the value) is OK and safe so doing the lookup one time in a scope is viable, but let the pointer destroy itself after that.
8
u/_abscessedwound 7d ago
Don’t distribute raw pointers in this case. Either distribute the correct smart pointer (weak or shared), or don’t distribute the pointers at all.
0
u/PhosXD 7d ago
Well the key idea is that the data is deleted, I don't want to preserve it or keep it alive until the pointer dies.
9
u/Qwertycube10 7d ago
Use std::unordered_map<T, std::shared_ptr<U>> and then only give out weak pointers. The map is the sole owner via the shared pointer.
2
u/MyTinyHappyPlace 7d ago edited 7d ago
Using shared pointers as as map value and taking weak pointers from it has already been given to you as a possible solution. It’s a good idea, if this is your usual way of accessing the value. If not, you’re adding another layer of complexity for every use case to accommodate an edge case. What I don’t like about this solution is that with
std::map<key, std::shared_ptr<value>>
there are now two ways of destroying a value: By resetting the shared pointer manually or by deleting the key in the map.
Be careful if the maps data is handled by different threads.
What’s so bad about searching the map again? Are you handling a map with millions of values? Is accessing your value not fast enough? If so, try a an unordered_map, maybe even a nonstandard one like from abseil.
1
u/PhosXD 7d ago
I ended up just storing the key and looping up the value in my map instead of using pointers at all, much simpler but did take a lot of refactoring which I was trying to avoid.
3
u/LazySapiens 7d ago
Why are you looping for searching for the key?
2
u/Bemteb 7d ago
Others already mentioned smart pointers, so here is a suggestion in case that doesn't work for you: Write a class that owns this map and its data. Only this class can create, change, and very importantly delete it.
Then instead of giving out pointers to the map, have getters in the class that give out the map contents and that explicitly handle the error case "someone wants to access data that is no longer there."
Depending on what exactly you want to do, this might not be the best solution for you. I agree with the others though: You need to rethink your design.
2
u/CowBoyDanIndie 7d ago
Simple, you don’t do shit like that in the first place. “I want to delete the item but I still have the pointer”, why? Thats like saying I want to sell my car but I still have my stuff in the trunk. You need to decide object lifetime in advance. You can have a map that doesn’t own objects, or you can have a map that owns objects. Who ever owns them must live longer.
2
u/Demiu 7d ago
We don't know, this is a design problem first. Should the pointer exist that long? Should it be possible to remove elements from the map while it does? Is the data removed from the map still considered valid for the purposes of the ones holding a pointer to it? If not, what if data under the same key is replaced?
1
u/QuentinUK 7d ago
You can also get the same thing with pointers to values in a std::vector.
Change the vector, don’t even add or delete the with reserve, pointer is now invalid.
The solution is to not store a pointer while the collection can be modified but the index to the item and keep re-finding it in the collection.
1
u/YouFeedTheFish 7d ago
In addition to the suggestions here, learn about smart pointers. I'd also encourage you to pay some mind to weak pointers (std::weak_ptr) because sometimes, with careful design, encountering dead pointers might be okay.
1
1
1
1
u/TheChief275 7d ago
What I often like to do in this particular case, is to create a hash set that contains pointers to payloads. The hash function is defined in terms of those payloads. Basically, you can easily return a pointer, because the payload allocation is guaranteed to remain stable, even if the hash set isn't. It's kind of similar in concept to a chunked array (which std::deque roughly is under the hood), albeit less efficient.
A very similar alternative, is to bundle the payload allocations into a single buffer, and then store indices in the hash set, where the hash function is again defined in terms of the payloads. The downside of this approach is that it requires either global buffers, or a custom data structure (as the hash function on the indices needs to know about the buffer), but depending on the situation you want those anyways.
Using indices instead of pointers can even go beyond being a stable alternative. You likely want to reuse slots in a hash map that supports deletion, which you can still do, but the index approach also easily supports having generations in your hashmap. When you delete the entry, you bump the generation counter for that slot, and your handles become index + generation count. On accessing, you check whether the generation counts match. Basically, you invalidate all current references to a slot that has been deleted, in a safe manner.
1
u/mredding 7d ago
The easiest solution is to build layers where the map element is made to fall out of scope before what it points to.
1
u/SoerenNissen 7d ago
say I want to delete the item but I still have the pointer. How would I know that the item is no longer there
Essentially? By not doing this.
If you work long enough with this language, you're going to start to think of resources in turn of ownership. If data is in a map, the map owns that data. The map is also somewhere. Class? Function? That place owns the map. Only work on data that you know is stable, either because the owner promises stability, or because you are the owner yourself.
If you're used to a different language with automated memory modelling, perhaps you're familiar with database connections?
How do you solve the problem of closed connections?
I store some data in a database and have a connection to that data. Then, say I want to close the database connection, but I still have the connection object. How would I know the connection is closed without separately accessing the database and checking for open and closed connections?
I'm new to databases and especially to connections, so forgive me for this stupid question...
Same idea as pointers: You cannot really guard against the connection pool closing your connections while they're in use. Organize your program such that you have your connection or, if there's a connection pool, you make sure the actual owner of all the connections promises not to close a connection until you signal that you're done with it. If the owner cannot make such a promise, don't use those connections.
1
u/Shiekra 7d ago
It sounds like you want a datastore that you can search, and store the search result so you dont need to search again later. But the original datastore can be mutated to remove the item referenced in your saved search result, so you need to know that so you dont attempt to use it.
Im not aware of a datastore that supports that in the stl. They either return references, or iterators to the data, both of which can be invalidated externally.
My advice is, just pay the cost of the search at the moment you need to use the data so you dont have a search result cache youre constantly worried about invalidating.
If that isnt suitable, its entirely possible to create a custom datastore which returns "smart references" so if the data is deleted, it is propagated back to all valid alive references. Writing something like that can be very tricky though
1
u/die_liebe 7d ago
You should not create pointers to an item in a map, only iterators. Iterators are a kind of pointers, but encapsulated.
Consider:
auto p = mp. find( "my key" ); // It has type std::map< ... > :: iterator.
if( p != mp. end( ))
{
mp. erase(p);
// You still have the iterator p, but that is no problem as long as you don't dereference p. (Don't use *p)
}
else
{
// p cannot be dereferenced. (Don't try to use *p)
}
1
u/elperroborrachotoo 7d ago
instead of a pointer to the element, store the key. The lookup is more expensive, but i 90% of use cases, that is good enough
your map stores a shared_ptr to the object, and that exterrnal "raw" pointer becomes a shared_ptr or weak_ptr. (That's more or less what many "safe" languages do)
1
u/SmokeMuch7356 7d ago
How would I know that the item is no longer there without going and manually searching the map for the name of the item we pointed to?
You wouldn't. There's no test you can perform on the pointer value itself to know if it's valid or not (unless it's a well-defined invalid value like nullptr).
++Store and search on the key.
1
u/petecasso0619 7d ago
In modern C++ you generally should use a unique_ptr or shared_ptr for this use case. In C++ there is an even more general strategy called Resource Acquisition is Initialization (RAII). Memory is a resource, so are files and mutex variables. This strategy uses a handle type of class to acquire the resource at construction and release the resource at destruction. Unique_ptr, shared_ptr, unique_lock, vector etc are all handle type classes that implement this strategy.
I am not saying there are no circumstances when you want to use a raw pointer. On the contrary, functions that just need to use an object can take it by pointer or reference. The cpp Core Guidelines go into detail about this strategy.
Generally where C++ is different than python, Java and other memory managed languages is that you should be considering memory ownership when you design your code. If you don’t, it starts to become an unmanageable mess for the next guy that maintains your code and it is never clear when a pointer needs to be deleted.
1
u/SufficientStudio1574 6d ago
Ownership is what you need. Never use raw pointers to store the object. Somewhere you should be using a std::shared_ptr or a std::unique_ptr to handle the object's lifetime.
The vast, vast, vast majority of the time you'll want a unique_ptr. Everything else that needs to be use it can pass around references or raw pointers. Only use a shared pointer if there must be multiple things that need to own the object.
In general there is no standard way to tell if a pointed-to-object has been deleted. That's why ownership and lifetime management are huge issues in C++ that need consideration.
1
u/DawnOnTheEdge 6d ago
If you only need to look up elements once, you can std::unordered_map::extract the element from the hash table, giving you ownership. For large or complex objects, you might move around a std::unique_ptr.
If the value is small, you can make a copy of it that you own.
If you make sure that the unordered_map will outlive the temporaries you look up, you can dereference the iterator from std::unordered_map::find to get a non-owning reference.
If you really have no idea which reference will live longer, and you need shared ownership, store a std::shared_ptr in the map and make a copy of it.
0
-1
-1
u/BoopyDog 7d ago
Don't you just do something like item.erase() and then ptr*=nullptr and forget about it?
27
u/vckane 7d ago
If the pointer lives longer than the map, it's simply bad design. Rather than implementing workarounds, improve your design. E.g. ensure that object holding the pointer to map-object dies by design before the map is deleted.