Re: [boost] [Container] interest in a flat_unordered_map

On Fri, Sep 18, 2015 at 2:24 PM, Francois Duranleau < xiao.bai.xiong@gmail.com> wrote:

On Fri, Sep 18, 2015 at 4:09 PM, Treb Connell wrote:

...

I could make a new concept for this, pay the cost for making it truly O(1), or *since the common case is not O(N) would it be okay to consider these bidirectional iterators*?

How about letting the user decide and making the iterator behavior choice a template boolean argument, and select the appropriate implementation based on that (e.g like many container options are done in Boost.Intrusive)?

Leaving the option up to the user is nice, but I agree that users are unlikely to want to pay a performance penalty just to avoid iteration being slow in the case that the capacity is much larger than the size. Users are likely to be careful already how they use such a container given that they have specifically chosen to use a flat_ container rather than the default. Making it a compile-time option might make the code significantly more complex and also hurt compile times. Unrelated to the iterator issue, since there are various trade-offs to the different open addressing/flat hashing approaches, it might be better to give the container a more specific name, or ideally if you have the energy, implement multiple approaches. I'd say just document it as bidirectional iterators but explain how they work/the performance considerations. It is already well-established that the standard iterator categories are not defined in a sufficiently flexible way. Big-O notation is also pretty meaningless when applied to actual software.