2

Often I have a map for which the keys are only used for importing, exporting and setup. During the performance critical stage, the values are of importance, not the keys.

I would like to use a data structure that acts like a map but gives me the option to just use a simple std::vector of mapped values when the keys are irrelevant.

The implementation seems reasonably simple. Just use a pair of equally sized vectors in which to store the key and value respectively, sorted with respect to the key vector. Insertions and deletions will be less efficient than in boost::flat_map, but that is a compromise I'm willing to make in order to get instant access to the vector of key unencumbered values.

Is this a terrible idea? If not, is there an existing implementation I can use?

That
  • 25
  • 3
Richard Forrest
  • 601
  • 1
  • 7
  • 9
  • If the values are just stored in key order, wouldn't that just be an array? If you store the keys in one vector and the values in the other vector of that order, it seems like the keys become unnecessary, unless I am misinterpreting what you mean – Jason Aug 04 '15 at 15:04
  • 1
    Yes, this sounds very much like a simple vector that you keep sorted based on the key. – Mark Jansen Aug 04 '15 at 15:12
  • @Jason: I want to use the structure as a map on some occasions and as an array (sorted on the key) on others. I am hoping that ignoring the keys on the latter occasions will also improve cache-locality. – Richard Forrest Aug 04 '15 at 15:13
  • @MarkJansen: Yes. That would be the basic implementation. But a pair or naked vectors would need a certain amount of bookkeeping code around them to keep them synchronised. Also it would be nice if they could be used as if they were a map. The implementation would not be entirely trivial. – Richard Forrest Aug 04 '15 at 15:19
  • @RichardForrest In that case, I'm not sure if there's an existing data structure to do exactly that, but you could probably code one up fairly easily – Jason Aug 04 '15 at 15:22
  • It seems like you could either store a `std::pair` or use a second `std::vector`. `boost::flat_map` doesn't maintain a vector of `std::pair` values sorted by keys? – Jason Aug 04 '15 at 15:22
  • boost::flat_map would not be suitable as it would cause the keys to be loaded into the cache as well as the values when just accessing the values. – Richard Forrest Aug 04 '15 at 15:46
  • Possibly a `std::vector` twice the cardinality, but a second `std::vector` would probably be most cache friendly. – Jason Aug 04 '15 at 15:58
  • I think you're on the right track, see http://stackoverflow.com/questions/236172/how-do-i-sort-a-stdvector-by-the-values-of-a-different-stdvector for some help. – Mark Ransom Aug 04 '15 at 16:48
  • Assuming there are no insertions/removals during the performance critical phase: you could use a normal map during importing/exporting/setup and then create a sorted vector of just the values for the performance critical part. This would waste some memory, but it should be much easier to implement. Or, if there will be insertions/removals, but only very very rare, you could mark the value-vector dirty and re-create it on-the-fly at the next value-vector-access. – Paul Groke Aug 04 '15 at 19:01

0 Answers0