How about implement gtsam::KeyValueMap with hashable container?
demul opened this issue · 4 comments
Feature
It seems that gtsam::KeyValueMap is implemented based on boost::ptr_map.
And boost::ptr_map is implemented based on std::map (https://www.boost.org/doc/libs/1_81_0/libs/ptr_container/doc/ptr_map.html)
std::map is implemented with red-black tree.
So the time complexity of gtsam::KeyValueMap::find is O(logN).
So, gtsam::Value::exists takes O(logN).
Motivation
I want to make gtsam::Value::exists faster.
Pitch
The time complexity of gtsam::Value::exists becomes constant time.
Alternatives
How about using std::unordered_map instead of boost::ptr_map?
I think last time we discussed it's because we can't break API in 4.x
KeyValueMap uses std::map in the current develop, so I'm not sure what the issue is asking for.
@varunagrawal
std::map is implemented with red-black tree, so KeyValueMap::find takes O(logN).
I thought replacing std::map with std::unordered_map will be better because std::unordered_map is a hashable container, so KeyValueMap::find will takes O(1).
@ProfFan
Thank you, so maybe this feature request is going to be addressed on next version(5.X) API?
And would you give me the link for the discussion before?
@varunagrawal std::map is implemented with red-black tree, so KeyValueMap::find takes O(logN). I thought replacing std::map with std::unordered_map will be better because std::unordered_map is a hashable container, so KeyValueMap::find will takes O(1).
@ProfFan Thank you, so maybe this feature request is going to be addressed on next version(5.X) API? And would you give me the link for the discussion before?
You can search in the issues, it's long long time ago. Actually what you can even do is just make a fork replacing Value to be a simple map, and then make a PR :)