3803. flat_foo constructors taking KeyContainer lack KeyCompare parameter

Section: 23.6.8 [flat.map], 23.6.9 [flat.multimap], 23.6.11 [flat.set], 23.6.12 [flat.multiset] Status: C++23 Submitter: Arthur O'Dwyer Opened: 2022-10-25 Last modified: 2023-11-22

Priority: 1

View other active issues in [flat.map].

View all other issues in [flat.map].

View all issues with C++23 status.

Discussion:

flat_set's current constructor overload set has these two overloads:

explicit flat_set(container_type cont);
template<class Allocator>
  flat_set(const container_type& cont, const Allocator& a);

I believe it should have these two in addition:

flat_set(const key_compare& comp, container_type cont);
template<class Allocator>
  flat_set(const key_compare& comp, const container_type& cont, const Allocator& a);

with corresponding deduction guides. Similar wording changes would have to be made to all the flat_foo containers.

Tony Table:

struct LessWhenDividedBy {
  int divisor_;
  bool operator()(int x, int y) const { return x/divisor_ < y/divisor_; }
};
std::flat_set<int, LessWhenDividedBy> s(data.begin(), data.end(), LessWhenDividedBy(10));
// BEFORE AND AFTER: okay, but cumbersome
std::flat_set<int, LessWhenDividedBy> s(data);
// BEFORE AND AFTER: oops, this default-constructs the comparator

std::flat_set<int, LessWhenDividedBy> s(LessWhenDividedBy(10), data);
// BEFORE: fails to compile
// AFTER: compiles successfully

[2022-11-04; Reflector poll]

Set priority to 1 after reflector poll.

[2023-02-09 Tim adds wording]

For each construction that takes containers, this wording allow a comparator to be specified as well. Differing from the suggestion in the issue, the comparator goes last (but before the allocator), for consistency with every other constructor of flat_meow taking a comparator. (This is inconsistent with priority_queue, but consistency among the type's own constructors seems more important.)

[Issaquah 2023-02-09; LWG]

Move to Immediate for C++23

[2023-02-13 Approved at February 2023 meeting in Issaquah. Status changed: Immediate → WP.]

Proposed resolution:

This wording is relative to N4928.

1. Add a new bullet to 23.6.1 [container.adaptors.general] p6 as indicated:

   -6- A deduction guide for a container adaptor shall not participate in overload resolution if any of the following are true:

   1. — (6.?) It has both KeyContainer and Compare template parameters, and is_invocable_v<const Compare&, const typename KeyContainer::value_type&, const typename KeyContainer::value_type&> is not a valid expression or is false.

2. Modify 23.6.8.2 [flat.map.defn] as indicated:

   namespace std {
     template<class Key, class T, class Compare = less<Key>,
              class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
     class flat_map {
     public:
       […]
       // 23.6.8.3 [flat.map.cons], construct/copy/destroy
       flat_map() : flat_map(key_compare()) { }
   
       flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
                const key_compare& comp = key_compare());
       template<class Allocator>
         flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                  const Allocator& a);
       template<class Allocator>
         flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                  const key_compare& comp, const Allocator& a);
   
       flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
                const key_compare& comp = key_compare());
       template<class Allocator>
         flat_map(sorted_unique_t, const key_container_type& key_cont,
                  const mapped_container_type& mapped_cont, const Allocator& a);
       template<class Allocator>
         flat_map(sorted_unique_t, const key_container_type& key_cont,
                  const mapped_container_type& mapped_cont, 
                  const key_compare& comp, const Allocator& a);
       […]
     };
   
     template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_map(KeyContainer, MappedContainer, Compare = Compare())
         -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compareless<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
   
     template<class KeyContainer, class MappedContainer, class Allocator>
       flat_map(KeyContainer, MappedContainer, Allocator)
         -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
     template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
       flat_map(KeyContainer, MappedContainer, Compare, Allocator)
         -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compare, KeyContainer, MappedContainer>;
   
   
     template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare = Compare())
         -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compareless<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
   
     template<class KeyContainer, class MappedContainer, class Allocator>
       flat_map(sorted_unique_t, KeyContainer, MappedContainer, Allocator)
         -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
     template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
       flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare, Allocator)
         -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compare, KeyContainer, MappedContainer>;
     […]
   }
   

3. Modify 23.6.8.3 [flat.map.cons] as indicated:

   flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
            const key_compare& comp = key_compare());
   

   -1- Effects: Initializes c.keys with std::move(key_cont), and c.values with std::move(mapped_cont), and compare with comp ; value-initializes compare; sorts the range [begin(), end()) with respect to value_comp(); and finally erases the duplicate elements as if by:

   auto zv = ranges::zip_view(c.keys, c.values);
   auto it = ranges::unique(zv, key_equiv(compare)).begin();
   auto dist = distance(zv.begin(), it);
   c.keys.erase(c.keys.begin() + dist, c.keys.end());
   c.values.erase(c.values.begin() + dist, c.values.end());
   

   -2- Complexity: Linear in N if the container arguments are already sorted with respect to value_comp() and otherwise N log N, where N is the value of key_cont.size() before this call.

   template<class Allocator>
     flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
              const Allocator& a);
   template<class Allocator>
     flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
              const key_compare& comp, const Allocator& a);
   

   -3- Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.

   -4- Effects: Equivalent to flat_map(key_cont, mapped_cont) and flat_map(key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -5- Complexity: Same as flat_map(key_cont, mapped_cont) and flat_map(key_cont, mapped_cont, comp), respectively.

   flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
            const key_compare& comp = key_compare());
   

   -6- Effects: Initializes c.keys with std::move(key_cont), and c.values with std::move(mapped_cont), and compare with comp ; value-initializes compare.

   -7- Complexity: Constant.

   template<class Allocator>
     flat_map(sorted_unique_t s, const key_container_type& key_cont,
              const mapped_container_type& mapped_cont, const Allocator& a);
   template<class Allocator>
     flat_map(sorted_unique_t s, const key_container_type& key_cont, 
              const mapped_container_type& mapped_cont, const key_compare& comp,
              const Allocator& a);
   

   -8- Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.

   -9- Effects: Equivalent to flat_map(s, key_cont, mapped_cont) and flat_map(s, key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -10- Complexity: Linear.

4. Modify 23.6.9.2 [flat.multimap.defn] as indicated:

   namespace std {
     template<class Key, class T, class Compare = less<Key>,
              class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
     class flat_multimap {
     public:
       […]
       // 23.6.9.3 [flat.multimap.cons], construct/copy/destroy
       flat_multimap() : flat_multimap(key_compare()) { }
   
       flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
                     const key_compare& comp = key_compare());
       template<class Allocator>
         flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                       const Allocator& a);
       template<class Allocator>
         flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                       const key_compare& comp, const Allocator& a);
   
       flat_multimap(sorted_equivalent_t, 
                     key_container_type key_cont, mapped_container_type mapped_cont,
                     const key_compare& comp = key_compare());
       template<class Allocator>
         flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
                       const mapped_container_type& mapped_cont, const Allocator& a);
       template<class Allocator>
         flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
                       const mapped_container_type& mapped_cont, 
                       const key_compare& comp, const Allocator& a);
       […]
     };
   
     template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_multimap(KeyContainer, MappedContainer, Compare = Compare())
         -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compareless<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
   
     template<class KeyContainer, class MappedContainer, class Allocator>
       flat_multimap(KeyContainer, MappedContainer, Allocator)
         -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
     template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
       flat_multimap(KeyContainer, MappedContainer, Compare, Allocator)
         -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compare, KeyContainer, MappedContainer>;
   
   
     template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare = Compare())
         -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compareless<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
   
     template<class KeyContainer, class MappedContainer, class Allocator>
       flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Allocator)
         -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
     template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
       flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare, Allocator)
         -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
                     Compare, KeyContainer, MappedContainer>;
     […]
   }
   

5. Modify 23.6.9.3 [flat.multimap.cons] as indicated:

   flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
                 const key_compare& comp = key_compare());
   

   -1- Effects: Initializes c.keys with std::move(key_cont), and c.values with std::move(mapped_cont), and compare with comp ; value-initializes compare; and sorts the range [begin(), end()) with respect to value_comp().

   -2- Complexity: Linear in N if the container arguments are already sorted with respect to value_comp() and otherwise N log N, where N is the value of key_cont.size() before this call.

   template<class Allocator>
     flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                   const Allocator& a);
   template<class Allocator>
     flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                   const key_compare& comp, const Allocator& a);
   

   -3- Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.

   -4- Effects: Equivalent to flat_multimap(key_cont, mapped_cont) and flat_multimap(key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -5- Complexity: Same as flat_multimap(key_cont, mapped_cont) and flat_multimap(key_cont, mapped_cont, comp), respectively.

   flat_multimap(sorted_equivalent_t, key_container_type key_cont, mapped_container_type mapped_cont,
                 const key_compare& comp = key_compare());
   

   -6- Effects: Initializes c.keys with std::move(key_cont), and c.values with std::move(mapped_cont), and compare with comp ; value-initializes compare.

   -7- Complexity: Constant.

   template<class Allocator>
     flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont,
                  const mapped_container_type& mapped_cont, const Allocator& a);
   template<class Allocator>
     flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont, 
                   const mapped_container_type& mapped_cont, const key_compare& comp,
                   const Allocator& a);
   

   -8- Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.

   -9- Effects: Equivalent to flat_multimap(s, key_cont, mapped_cont) and flat_multimap(s, key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -10- Complexity: Linear.

6. Modify 23.6.11.2 [flat.set.defn] as indicated:

   namespace std {
     template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
     class flat_set {
     public:
       […]
   
       // [flat.set.cons], constructors
       flat_set() : flat_set(key_compare()) { }
   
       explicit flat_set(container_type cont, const key_compare& comp = key_compare());
       template<class Allocator>
         flat_set(const container_type& cont, const Allocator& a);
       template<class Allocator>
         flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);
   
       flat_set(sorted_unique_t, container_type cont, const key_compare& comp = key_compare())
         : c(std::move(cont)), compare(compkey_compare()) { }
       template<class Allocator>
         flat_set(sorted_unique_t, const container_type& cont, const Allocator& a);
       template<class Allocator>
         flat_set(sorted_unique_t, const container_type& cont, 
                  const key_compare& comp, const Allocator& a);
   
       […]
     };
   
   
     template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_set(KeyContainer, Compare = Compare())
         -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
     template<class KeyContainer, class Allocator>
       flat_set(KeyContainer, Allocator)
         -> flat_set<typename KeyContainer::value_type, less<typename KeyContainer::value_type>, KeyContainer>;
     template<class KeyContainer, class Compare, class Allocator>
       flat_set(KeyContainer, Compare, Allocator)
         -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
   
     template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_set(sorted_unique_t, KeyContainer, Compare = Compare())
         -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
     template<class KeyContainer, class Allocator>
       flat_set(sorted_unique_t, KeyContainer, Allocator)
         -> flat_set<typename KeyContainer::value_type, less<typename KeyContainer::value_type>, KeyContainer>;
     template<class KeyContainer, class Compare, class Allocator>
       flat_set(sorted_unique_t, KeyContainer, Compare, Allocator)
         -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
   
     […]
   }
   

7. Modify 23.6.11.3 [flat.set.cons] as indicated:

   flat_set(container_type cont, const key_compare& comp = key_compare());
   

   -1- Effects: Initializes c with std::move(cont) and compare with comp , value-initializes compare, sorts the range [begin(), end()) with respect to compare, and finally erases all but the first element from each group of consecutive equivalent elements.

   -2- Complexity: Linear in N if cont is already sorted with respect to compare and otherwise N log N, where N is the value of cont.size() before this call.

   template<class Allocator>
     flat_set(const container_type& cont, const Allocator& a);
   template<class Allocator>
     flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);
   

   -3- Constraints: uses_allocator_v<container_type, Allocator> is true.

   -4- Effects: Equivalent to flat_set(cont) and flat_set(cont, comp), respectively, except that c is constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -5- Complexity: Same as flat_set(cont) and flat_set(cont, comp), respectively.

   template<class Allocator>
     flat_set(sorted_unique_t s, const container_type& cont, const Allocator& a);
   template<class Allocator>
     flat_set(sorted_unique_t s, const container_type& cont, const key_compare& comp, const Allocator& a);
   

   -6- Constraints: uses_allocator_v<container_type, Allocator> is true.

   -7- Effects: Equivalent to flat_set(s, cont) and flat_set(s, cont, comp), respectively, except that c is constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -8- Complexity: Linear.

8. Modify 23.6.12.2 [flat.multiset.defn] as indicated:

   namespace std {
     template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
     class flat_multiset {
     public:
       […]
   
       // [flat.multiset.cons], constructors
       flat_multiset() : flat_multiset(key_compare()) { }
   
       explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
       template<class Allocator>
         flat_multiset(const container_type& cont, const Allocator& a);
       template<class Allocator>
         flat_multiset(const container_type& cont, const key_compare& comp, const Allocator& a);
   
       flat_multiset(sorted_equivalent_t, container_type cont, const key_compare& comp = key_compare())
         : c(std::move(cont)), compare(compkey_compare()) { }
       template<class Allocator>
         flat_multiset(sorted_equivalent_t, const container_type& cont, const Allocator& a);
       template<class Allocator>
         flat_multiset(sorted_equivalent_t, const container_type& cont, 
                       const key_compare& comp, const Allocator& a);
   
       […]
     };
   
   
     template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_multiset(KeyContainer, Compare = Compare())
         -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
     template<class KeyContainer, class Allocator>
       flat_multiset(KeyContainer, Allocator)
         -> flat_multiset<typename KeyContainer::value_type, less<typename KeyContainer::value_type>, KeyContainer>;
     template<class KeyContainer, class Compare, class Allocator>
       flat_multiset(KeyContainer, Compare, Allocator)
         -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
   
     template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
       flat_multiset(sorted_equivalent_t, KeyContainer, Compare = Compare())
         -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
     template<class KeyContainer, class Allocator>
       flat_multiset(sorted_equivalent_t, KeyContainer, Allocator)
         -> flat_multiset<typename KeyContainer::value_type, less<typename KeyContainer::value_type>, KeyContainer>;
     template<class KeyContainer, class Compare, class Allocator>
       flat_multiset(sorted_equivalent_t, KeyContainer, Compare, Allocator)
         -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
   
     […]
   }
   

9. Modify 23.6.12.3 [flat.multiset.cons] as indicated:

   flat_multiset(container_type cont, const key_compare& comp = key_compare());
   

   -1- Effects: Initializes c with std::move(cont) and compare with comp , value-initializes compare, and sorts the range [begin(), end()) with respect to compare.

   -2- Complexity: Linear in N if cont is already sorted with respect to compare and otherwise N log N, where N is the value of cont.size() before this call.

   template<class Allocator>
     flat_multiset(const container_type& cont, const Allocator& a);
   template<class Allocator>
     flat_multiset(const container_type& cont, const key_compare& comp, const Allocator& a);
   

   -3- Constraints: uses_allocator_v<container_type, Allocator> is true.

   -4- Effects: Equivalent to flat_multiset(cont) and flat_multiset(cont, comp), respectively, except that c is constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -5- Complexity: Same as flat_multiset(cont) and flat_multiset(cont, comp), respectively.

   template<class Allocator>
     flat_multiset(sorted_equivalent_t s, const container_type& cont, const Allocator& a);
   template<class Allocator>
     flat_multiset(sorted_equivalent_t s, const container_type& cont, const key_compare& comp, const Allocator& a);
   

   -6- Constraints: uses_allocator_v<container_type, Allocator> is true.

   -7- Effects: Equivalent to flat_multiset(s, cont) and flat_multiset(s, cont, comp), respectively, except that c is constructed with uses-allocator construction (20.2.8.2 [allocator.uses.construction]).

   -8- Complexity: Linear.