Hello wonderful helpful Godot community members. If anyone can help, I will be extremely grateful. I have been learning C++ and Godot’s API/gdextention for hobby and fun the last couple months and it’s mostly gone smoothly. I made a character controller that I’m very proud of that can run around, crouch, climb stairs, and interact with buttons. I’ve learned a lot along the way and now I’m trying to go back and clean some stuff up that I feel was too hacky or incorrect.
I could not figure out iterating over a HashMap to delete the keys. I settled on storing a vector of the keys that needed deletion and doing a second for loop after to delete those keys from the HashMap, works fine but some added complexity and a second loop I’d like to avoid. I think HashMap can be iterated over and mutated safely and I’m just missing something.
So I am back at it.
Would this function properly iterate over a second entry in the HashMap if there was one?
It doesn’t seem remove returns an iterator and there’s nothing like erase_if or remove_if?
void InteractableComponent::_physics_process(double delta)
{
if (players_hovering.size() == 0) return;
for (auto i = players_hovering.begin(); i != players_hovering.end(); ++i)
{
auto m_key = i -> key;
if (i -> value < m_engine -> get_physics_frames())
players_hovering.erase(m_key);
UtilityFunctions::print("Removing key");
if (players_hovering.is_empty()) break;
}
}
If anyone has any insight I will be very very happy to learn. Thank you so much for your time and reading.
So when I was right I thought I wrong. All in the name of premature optimization. I was reading ways that a std::unordered_map can be iterated over and trying to apply them in a way that doesn’t make sense for the godot container class. Thanks again for your advice Silnarm, I can rest easy tonight without over thinking this one. Appreciate it a lot,
I just had a peek in the source, and it does not resize on element removal, so in theory it could work the same as std::unordered_map, the interface just doesn’t support it
I think you are right! It would not compile with next_it = it + 1; but there was an overload for ++it;
It appears to be removing my character from the list as intended with this code. Until I get multiplayer and a second character in here to interact as well, I won’t be certain
Edit: After adding a print out it seems like it may not be actually removing the value from the hashmap this way. The loop is breaking but continues to repeat every frame. Curious for sure.
void InteractableComponent::_physics_process(double delta)
{
if ( players_hovering.size() == 0 ) return;
for ( auto i = players_hovering.begin(); i != players_hovering.end(); )
{
if ( i->value < m_engine->get_physics_frames() )
{
auto next_i = ++i;
players_hovering.remove(i);
UtilityFunctions::print("removed from list");
i = next_i;
}
else{++i;}
}
UtilityFunctions::print("exited for loop");
}
Interesting, I was getting a segfault after moving the character out of the zone that would refresh the value keeping the key valid.
There doesn’t appear to be an overload for i++ on the iterator, it would only compile with ++i;
At least for now the deletion list on the side is working as intended, and you made me feel better about the approach.
Vector<CharacterController*> removal_list;
for ( auto i = players_hovering.begin(); i != players_hovering.end(); ++i )
{
if ( i->value < m_engine->get_physics_frames() )
{
removal_list.append ( i -> key );
}
}
for ( int i = 0; i < removal_list.size(); i++ )
{
players_hovering.erase( removal_list[i] );
}
Of course.
Copy constructor is not deleted, so you could copy the iterator, increment the original and then delete with the copy, but yeah… nothing wrong with the two loop solution, and if it aint broke…
I really should listen. If it is not broke, don’t fix it, and never prematurely optimize.
I ended up losing sleep pondering this one a lot last night. I am not a programmer by profession, I never went to any secondary education and am not that smart, but am absolutely fascinated by computer science and love the feeling of understanding anything, or getting passed a confusion.
I ended up re-implementing the function with a std::unordered_map to be able to profile it against the HashMap and Vector after and learn about profiling functions. My stubborn self will not actually leave this function in my prototype that no one else will see as I really want to use Godot containers, but had to test the implementation. And I am going to benchmark it against the second loop using a HashMap and Vector.
This works as expected with a std::unordered_map
void Component::_physics_process(double delta)
{
if (uomap.size() == 0) return;
for (auto it = uomap.begin(); it != uomap.end();)
{
if (it->second == removal_condition)
{
it = uomap.erase(it);
}
else{++it;}
}
}
Two-Loop “Mark and Sweep” removal using Vector and HashMap
void Component::_physics_process(double delta)
{
if (hm.size() == 0) return;
Vector<key_type> removal_list;
for (auto it = hm.begin(); it != hm.end(); ++it)
{
if (it ->value == removal_condition)
{
removal_list.append (it -> key);
}
}
for (int it = 0; it < removal_list.size(); it++)
{
hm.erase(removal_list[it]);
}
}
Lastly I hope to design a loop like you described to remove elements by saving a iterator copy and removing on the next loop. I couldn’t quite nail the syntax . Using remove[it] wouldn’t properly remove the pair. I also tried tracking the key and doing an .erase() by that on the next loop with no results. Pretty stumped! Maybe I’m fighting nature.
void Component::_physics_process(double delta)
{
if (hm.size() == 0) return;
bool remove_last_iterator = false;
HashMap<Key, Value>::Iterator iterator_copy;
for (auto it = hm.begin(); it != hm.end(); ++it)
{
if (remove_last_iterator)
{
hm.remove(iterator_copy);
remove_last_iterator = false;
}
if (it -> key == removal_condition)
{
iterator_copy = it;
remove_last_iterator = true;
}
}
}
A HashMap is basically the Godot internal C++ version of the GDScript Dictionary type Variant. It is a key value associative container. If you’re doing your code in GDscript you can just use dictionaries and not worry about anything. The dictionary Variant has more overhead than a HashMap.
No, I meant which exact implementation. I wasn’t sure you were talking about godot::HashMap as none of your code shows any declarations. Sadly, Godot’s implementation of erase() doesn’t return the iterator. In STL associative containers erase() always returns the iterator pointing to the element following the erased element. There’s a common idiom for iterating/erasing in a single loop:
for(auto i = map.begin(); i != map.end();){
if(some_condition)
i = map.erase(i);
else
++i;
}
So if you use std::map or std::unordered_map you can do it like that.
Well actually good question. I was trying to iterate over godot::HashMap from templates/hashmap.h in the godot-cpp extension bindings. I couldn’t find AHashMap in the templates for godotcpp, and assumed it was the “HashMap” from the core container types on that docs page. I did get a std::unordered_map to do what I intended but am trying to find out if I can do something similar to the godot container. In my previous post I posted what was working on the unordered map using the returned iterator from .erase()
Right. Yeah, Godot’s erase() only returns a bool. I generally prefer STL containers as you get the whole assortment of common iterative tasks in <algorithm> that almost completely eliminate the need to manually iterate.
I see, I will consider ending my pointless mission of trying to fight the godot container and allow myself to use the STL library instead of dying on a strange hill on a learning project . Thanks for guiding me off my weird path, I am done with iterators. Modern C++ here we go. Cheers.
Ok, I can actually sleep tonight. Thank you. I guess that is the true solution to the original question, but a better answer is to just use the STL library. This is working the same as the deletion list and second loop, and the std::unordered_map loop. You’re the man.
void InteractableComponent::_physics_process(double delta)
{
if (players_hovering.size() == 0) return;
for ( auto i = players_hovering.begin(); i != players_hovering.end(); )
{
if ( i -> value < m_engine->get_physics_frames() )
{
auto j = i;
++i;
UtilityFunctions::print("Removing key-value pair");
players_hovering.remove(j);
}
else
{
++i;
}
}
UtilityFunctions::print("Loop broken");
}
. Using remove[it] wouldn’t properly remove the pair. I also tried tracking the key and doing an .erase() by that on the next loop with no results. Pretty stumped! Maybe I’m fighting nature.