Vladimir Prus


Monday, July 26, 2004

Sets and sequences

If you need to keep some objects unique, and at the same time store/output them in linear sequence, for example, to quickly access by index, the obvious solution is to use std::set, and then run through this set and assign indexes. But the important thing is that indexes should be assigned after you've populated the set, otherwise when you output the linear sequence, the order of objects will be different that the order of indices. It seems trivial, but for the last two days I have a second bug where indices were assigned during insertion in set. Clearly, those bugs were not caught by simple tests -- who would ever guess that a tool works only if the sources are in alphabetical order?! This reminds me of a class I wrote a long time ago: numbered_set. For each inserted element it would return a numerical index which would never change in future, but it also could efficiently check for duplicates. Or maybe it's time to try Boost.Multi_index in practice.

No comments: