P0429R9 <flat_map>

[StephanTLavavej]

P0429R9 <flat_map>
LWG-3786 Flat maps' deduction guides need to default Allocator to be useful
LWG-3803 flat_meow constructors taking KeyContainer lack KeyCompare parameter
LWG-3816 flat_map and flat_multimap should impose sequence container requirements
LWG-3884 flat_meow is missing allocator-extended copy/move constructors
LWG-3987 Including <flat_meow> doesn't provide std::begin/end

Feature-test macro:

#define __cpp_lib_flat_map 202207L

Internal VS-PR-420058 has taught the IDE about this new extensionless header - thanks @CaseyCarter!

[duanqn]

Hi, can I work on this?

[duanqn]

I read through the docs and started to work on this on my branch duanqn/STL:duanqn/flat_map. It is far from complete and I need more time to work on the implementation (and probably need help / reviews from experts later). Looks like it's going to be different from the boost implementation as the standard requires flat_map to store keys & values in separate containers.

[StephanTLavavej]

Sure, I'll move this to Investigating as you're looking into it.

[frederick-vs-ja]

Some thoughts on implementation details.

For iterator types:

• iterator and const_iterator shouldn't be dependent on key_compare.
• The use of zip_view can be avoided.
  • If iterator is denoted as _Ziperator<KeyContainer::const_iterator, MappedContainer::iterator>, then
  • const_iterator can be denoted as _Ziperator<KeyContainer::const_iterator, MappedContainer::const_iterator>, and
  • the iterator type used for ranges::unique (and perhaps ranges::sort) can be denoted as _Ziperator<KeyContainer::iterator, MappedContainer::iterator>.
• flat_map and flat_multimap can share the same iterator and const_iterator types.
• It might be better to make iterator types ADL-proof (see WG21-P2538R1), i.e. making them non-template nested classes of some class templates may be better.

For nested classes:

• Likewise, different flat_maps, or a flat_map and a flat_multimap may share
  • the same value_compare type, given Key, T, and Compare are the same, and/or
  • the same containers type, given KeyContainer and MappedContainer are the same.
• But we should keep value_compare and containers ADL-proof, they should still be non-template nested classes of class templates.
• An LWG issue seems to be needed for SCARY value_compare and containers - it's observable whether flat_map<K, V, CompX, KC, VC>::containers and flat_map<K, V, CompY, KC, VC>::containers are the same type. Edit: this is now LWG-3963.

[duanqn]

Thanks @frederick-vs-ja for sharing her/his/their insights. I briefly read the implementation of ranges::zip_view::iterator. Here are my thoughts on flat_map::iterator:

• Suppose iter is a flat_map::iterator, then *iter should return flat_map::iterator::reference type, which should be flat_map::value_type instead of flat_map::value_type&. When operator * is called on flat_map::iterator, a pair of std::pair<Key, T> is temporarily created.
• flat_map::iterator::pointer should be defined as void.
• Do I need to prevent people from writing things like std::sort(fmap.begin(), fmap.end());?

If there is anything wrong or anything I missed, please point it out, thanks~

[duanqn]

Also, I have implemented the constructors as written in P0429R9, but I am curious why the constructors are written as
flat_map(key_container_type key_cont, mapped_container_type mapped_cont);
rather than
template <class KC, class MC> flat_map(KC&& key_cont, MC&& mapped_cont); to handle lvalue & rvalue references?
I believe this has already been discussed by C++ experts but I just cannot see the reason.

Also the constructor flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont); is required to have constant time complexity. This means the containers are move-constructed, but wouldn't it introduce a copy when passing the arguments?

[frederick-vs-ja]

Thanks @frederick-vs-ja for sharing her/his/their insights. I briefly read the implementation of ranges::zip_view::iterator. Here are my thoughts on flat_map::iterator:

• Suppose iter is a flat_map::iterator, then *iter should return flat_map::iterator::reference type, which should be flat_map::value_type instead of flat_map::value_type&. When operator * is called on flat_map::iterator, a pair of std::pair<Key, T> is temporarily created.
• flat_map::iterator::pointer should be defined as void.
• Do I need to prevent people from writing things like std::sort(fmap.begin(), fmap.end());?

If there is anything wrong or anything I missed, please point it out, thanks~

Hmm... I believe flat_map's iterator types should be proxy iterators and their operator* should return pair<const K&, M&> or pair<const K&, const M&> (the reference or const_reference type of flat_map). But this doesn't seem to be strictly specified in the standard...

Edit: I've filed LWG-3966 for this.

I think std::sort or std::ranges::sort on a flat_map is automatically forbidden for most cases in pratice.

[duanqn]

Returning pair<const K&, M&> sounds like a good idea.

[CaseyCarter]

Also, I have implemented the constructors as written in P0429R9, but I am curious why the constructors are written as flat_map(key_container_type key_cont, mapped_container_type mapped_cont); rather than template <class KC, class MC> flat_map(KC&& key_cont, MC&& mapped_cont); to handle lvalue & rvalue references? I believe this has already been discussed by C++ experts but I just cannot see the reason.

I suspect LWG thought it wasn't worth the bother to make this constructor's specification more complicated given that container moves are generally cheap enough that the extra move construction has no noticeable impact.

Also the constructor flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont); is required to have constant time complexity. This means the containers are move-constructed, but wouldn't it introduce a copy when passing the arguments?

If the arguments are lvalues, yes, they'll be copied when passed by value. If the user wants to avoid copies, they can use rvalue arguments. In any case, that all happens in the caller so it's not our problem.

[duanqn]

Hi @StephanTLavavej , is it possible for you to make a collaboration branch for flat_map too? I feel that I may not be able to spend a lot of time testing the current implementation, and I shouldn't block the progress of the entire STL on this.

[StephanTLavavej]

@duanqn Done! You can create an initial PR for it when you're ready.

[duanqn]

@duanqn Done! You can create an initial PR for it when you're ready.

Thanks! And also thanks for merging my PR :)