tzlaine / flat_map Goto Github PK

template <typename Container, typename Cmp>
using flat_map = basic_flat_map<Container, Cmp>;

template <typename Key, typename Value, typename Cmp>
using flat_map = basic_flat_map<std::vector<std::pair<Key, Value>>, Cmp>;

[flatmap.capacity] p2

Can size_type == size_t be smaller than one of the container size_types,
e.g. when the latter are extended integer types?

I don't know.  This is like this because Marshall suggested to
hard-code size_t from the beginning, and no one has objected since.

Seems important to find out.  I want to know what happens if the min
"overflows" and thus loses information.  I think we cater for
extended integer types elsewhere, too.

template <class InputIterator>
void insert(sorted_unique_t, InputIterator first, InputIterator last);

Expects: The range [first,last) is sorted with respect to value_comp().
Effects: Equivalent to: insert(first, last).
Complexity: Linear.

Consider

flat_set<CaseInsensitiveString> s = {"a", "c", "e", "g", "i", "k"};
CaseInsensitiveString arr[5] = {"A", "B", "E", "F", "I", "J"};
s.insert(sorted_unique, arr, arr+5);

I can think of only two ways to implement the insert.

One, we could find the insertion point for A and insert it to produce Acegik, then find the insertion point for B (which we know must be to the right of A) and insert it to produce ABcegik, then find the insertion point for C... and so on. This requires O(n) insertions, which means it's order n^2 in general.

Two, we could append ABEFIJ to the end of the container (order n), stable-sort it to produce aABceEFgiIJk (order n log n), and then unique it (order n) to produce ABcEFgIJk. This is order n log n in general.

So I don't think it's possible to do it in "Linear" time.

Separately, note that if insertion into the underlying container — or sorting the underlying container — ever throws an exception, then we have no idea what is the state of the underlying container, which means we may have broken our "always-sorted-and-uniqued" invariant. If sort ever throws, we basically have to clear the entire container, if we want to preserve our invariant.

From Jens's review:

[flatmap.defn]

Editorially, we should make the exposition-only data members
italics (yes, that's new for the containers section, but the
right approach).

D0429R7 says, about the non-sorted_unique constructor:

\effects Initializes \tcode{c.keys} with \tcode{std::move(key_cont)} and
\tcode{c.values} with \tcode{std::move(mapped_cont)}; value-initializes
\tcode{compare}; sorts the range \range{begin()}{end()} with respect to
\tcode{value_comp()}; and finally erases the range
\range{ranges::unique(*this, value_comp())}{end()};

Unfortunately, ranges::unique is specified to accept a BinaryPredicate representing an equality relation, whereas value_comp() is specified to represent a less-than relation. So the current wording would do something horribly wrong — it would remove everything except the duplicate elements!

The semantics are salvageable, but I don't think we can use ranges::unique to express them.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p1206r7.pdf

Similarly to existing container adaptors, e.g. priority_queue, this class should also expose the underlying containers and comparing functor as protected.

Currently, they just forward to the InputIterator first, last ctors, but those have different requirements.

I'm writing one piece of software where I use small set (and maps) of characters. Because they are small, using set<char> or unordered_set<char> seemed like too much overhead. I considered using boost::flat_set<char> but then that would internally use vector<char>. But why vector<char> when you have a std::string. It has short string optimization, vector does not, and has much faster find functions. 5-10x faster then using std::search or even std::binary_search when the string is small enough (and sorted of course).

Ended up writing custom set class that is pretty much the same as flat_set backed by a string except for the function find which uses string.find, and not std::lower_bound. All the other set functions just reuse std::lower_bound, upper_bound and std::equal_range.

As I see, if i want to have flat_map backed by a string, I can do the following

flat_map<char, int, bool (*) (char, char), std::string> m(std::char_traits<char>::lt);

What I don't get here is fast enough find function because most likely it will use std::lower_bound internally.

Commit 60ff99a contains a gross changed{} fro the whole thing, because it is likely to be rewritten again. Fix this.

From Daniel Krügler on the LEWG mailing list:

2. [flatmap.defn]: The specification of flat_map::containers and
   flat_multimap::containers is currently not structured-binding
   friendly, albeit the access function extract seems to be a valid
   use-case for it (In fact your specification of [flatmap.erasure] and
   [flatmultimap.erasure] seems to imply structured-binding to be
   working, but that seems a bit too subtle to me). To add explicit
   support for structured-binding I suggest to add the following wording
   of power:

"For a flat_map<Key, T>, the member type containers has data members
and special members specified above. It has no base classes or members
other than those specified."

and

"For a flat_multimap<Key, T>, the member type containers has data
members and special members specified above. It has no base classes or
members other than those specified."

From P1222R6:

  template <class Container, class Allocator>
    flat_set(Container, Allocator)
      -> flat_set<@\placeholder{cont-value-type}@<Container>>;

This deduction guide is suspect because it takes an Allocator parameter and drops it on the floor. For example,

std::polymorphic_allocator<int> a;
auto fs = std::flat_set(std::pmr::vector{1,2,3}, a);

will end up deducing

std::flat_set<int> fs = std::flat_set<int>(std::pmr::vector{1,2,3}, a);

and then of course that doesn't compile.
Comparing the signature of this guide to the guides for stack and queue, we see that if this guide exists at all, it should really look like

  template <class Container, class Allocator>
    flat_set(Container, Allocator)
      -> flat_set<@\placeholder{cont-value-type}@<Container>,
                   std::less<@\placeholder{cont-value-type}@<Container>>,
                   Container>;

so that the above example would end up deducing

std::flat_set<int, std::less<int>, std::pmr::vector<int>> fs = std::flat_set<int, std::less<int>, std::pmr::vector<int>>(std::pmr::vector{1,2,3}, a);

But that's a major change, in that

auto fs2 = std::flat_set{1,2,3};

would no longer compile at all.

So you need to decide: should flat_set{1,2,3} have the "obvious" meaning, in the same way that std::set{1,2,3} does? Or should it be ill-formed, in the same way that std::stack{1,2,3} is?

This:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2363r3.html

may or may not make it for 23, so put the equivalent changes to the P0429 wording on a branch.

if you have a flat_map<const K, const V>, then it seems flat_map<const K, const V>::__pair_type will be std::pair<K, V>, leaving the type with no conversion to std::pair<const K, const V> despite that being its value_type.

See https://github.com/tzlaine/flat_map/blob/master/implementation/flat_map#L50

I was just curious what license the code is released under if any?

On Tue, May 24, 2022 at 1:45 PM Jonathan Wakely via Lib
[email protected] wrote:

On Tue, 24 May 2022 at 19:42, Jonathan Wakely [email protected] wrote:

On Tue, 24 May 2022, 17:43 Nico Josuttis via Lib, [email protected] wrote:

Thanks Casey.

Don't we create incondistencies with other containers then, which might confuse programmers?

And confuse implementors, in this case!

So what about the two sets of constructors taking ranges?

We have this, which no other containers or container adaptors have:

template <ranges::input_range R>
explicit flat_set(const R& range,
const key_compare& comp = key_compare());

And this one doesn't have any constraint that range_value_t is convertible to value_type, which we get from the container-compatible-range constraint for the ones like this:

True. I'd be happy to change this to
template ... (R&& ...). However, since
you're the only one that has raised this so far, and this seems like
it might be controversial, I'll ask others to chime in.

Zach