Task #2781
closed
Fib and FaceMap should be implemented using std::map instead of std::list
100%
Description
Currently, the Fib holds a collection of FibEntries in an std::list and FaceMap holds a collection of FaceMapEntries in an std::list.
Lookup could be optimized by using std::map.
Updated by Vince Lehman almost 9 years ago
- Subject changed from Fib should be implemented using std::map instead of std::list to Fib and FaceMap should be implemented using std::map instead of std::list
- Description updated (diff)
Updated by Nicholas Gordon over 7 years ago
- Target version changed from v0.3.0 to v0.3.1
Updated by Nicholas Gordon over 7 years ago
It seems to me that map is overkill. std::map orders the elements, and I'm not sure that's useful to us. If we are looking to optimize lookup and order is irrelevant, then std::unordered_map is best. It is essentially a hash map.
Can anyone comment if there would be some reason to order the FIB entries?
Updated by Nicholas Gordon over 7 years ago
- Status changed from New to Code review
- % Done changed from 0 to 90
I have taken the liberty of assuming that lookup will always be more important in these cases. I have pushed my patch to gerrit. It compiles and passes the tests.
Updated by Nicholas Gordon over 7 years ago
Consulting with Vince has revealed to me that unordered_map has some issues when using strings as the key type, and overcoming these costs incurs a significant memory cost. As such, the patch has been refactored to use std::map. (as per the original specification!)
Updated by Nicholas Gordon over 7 years ago
- Status changed from Code review to Closed
- % Done changed from 90 to 100