mdds 1.1.0

Share Button

I’m pleased to announce the availability of mdds 1.1.0. As always, the source package can be downloaded from the project’s home page.

This release includes the addition of 2 new data structures – trie_map and packed_trie_map, significant performance improvement on sorted_string_map, general bug fixes on some of the existing data structures, enhancement on multi_type_matrix, and support for user-defined event handlers for multi_type_vector.

Huge thanks to Markus Mohrhard for sorted_string_map’s performance improvement as well as the bug fixes and the enhancement on multi_type_matrix’s walk() method.

In addition, thanks to David Tardon, we now use automake as our build system which will simplify the process of package generation and integrity check among other things.

Here is the full list of changes since version 1.0.0:

  • all
    • switched our build system to using automake.
  • packed_trie_map (new)
    • new data structure that implements a trie also known as a prefix tree. This implementation requires all key values be known at construction time, after which its content is considered immutable. Internally it packs all its nodes in a single contiguous array for space and lookup efficiencies.
  • trie_map (new)
    • new data structure that implements a trie. It works similar to packed_trie_map except that this version is mutable.
  • multi_type_matrix
    • added a variant of walk() that takes the upper-left and lower-right corners to allow walking through a subset of the original matrix.
  • multi_type_vector
    • fixed incorrect return values of the increment and decrement operators of in-block iterators. They would previously return a value_type pointer which did not conform to the behaviors of STL iterators.
    • added support for custom event handlers for element block acquisitions and releases.
  • flat_segment_tree
    • fixed incorrect return values of the increment and decrement operators of its leaf-node iterators as in multi_type_vector’s fix.
  • sorted_string_map
    • significantly improved the performance of its find() method by switching from using linear search to using binary search. The improvement is especially visible with a large number of elements.


I’ve also added Doxygen documentation for this library for those who are more used to the Doxygen style comprehensive code documentation. The official API documentation has also received some love in the code examples for multi_type_vector. I plan on adding more code examples to the documentation as time permits.