Indigo icon indicating copy to clipboard operation
Indigo copied to clipboard

core: replace `RedBlackMap` and `RedBlackSet` implementation with standard containers

Open mkviatkovskii opened this issue 3 years ago • 0 comments

Motivation Currently Indigo uses own-written implementation of ordered associative containers and ordered sets using red-black trees. The implementation could be found in core/indigo-core/common/base_cpp/red_black.h. In many cases order of elements is not important and int is a key type, so it could be easily replaced with hash maps and also lead to performance improvement. Same for unordered sets.

ToDo

  1. Find all places in code that use RedBlackMap<K, V>, check if K is trivially hashable and order of elements is required, and replace it with std::map<K, V> or std::unordered_map<K, V> depending on the situation.
  2. Find all places in code that use RedBlackSet<K>, check if K is trivially hashable and order of elements is required, and replace it with std::set<K> or std::unordered_set<K> depending on the situation.
  3. Check if core/indigo-core/common/base_cpp/red_black.h and eliminate it if it's not required anymore.

mkviatkovskii avatar Nov 11 '21 20:11 mkviatkovskii