tzlaine / flat_map Goto Github PK
View Code? Open in Web Editor NEWflat_map standardization proposal
flat_map standardization proposal
From Daniel Krügler on the LEWG mailing list:
- [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."
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.
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
flat_map/paper/containers-lib.tex
Line 1040 in d96b01d
[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.
I was just curious what license the code is released under if any?
template <class InputIterator> void insert(sorted_unique_t, InputIterator first, InputIterator last);
Expects: The range
[first,last)
is sorted with respect tovalue_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 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?
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.
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
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.
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>;
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).
flat_map/implementation/flat_map
Lines 1231 to 1248 in 428ee6f
I've made a benchmark of a manual flat map via a vector of pairs vs your implementation and discovered, that searching for an element is significantly slower. The cause of this is, that find checks (__compare(*__it, __k), __key_lower_bound
already checked that. So you are checking it twice. Both gcc and clang doesn't found this possible implementation.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.