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

Subject: Re: [boost] [Container] interest in a flat_unordered_map
From: Jeremy Maitin-Shepard (jeremy_at_[hidden])
Date: 2015-09-18 18:47:10

On Fri, Sep 18, 2015 at 2:24 PM, Francois Duranleau <
xiao.bai.xiong_at_[hidden]> wrote:

> On Fri, Sep 18, 2015 at 4:09 PM, Treb Connell <trebconnell_at_[hidden]>
> 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.