This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of WP status.

3803. flat_foo constructors taking KeyContainer lack KeyCompare parameter

Section: 24.6.9 [flat.map], 24.6.10 [flat.multimap], 24.6.11 [flat.set], 24.6.12 [flat.multiset] Status: WP Submitter: Arthur O'Dwyer Opened: 2022-10-25 Last modified: 2023-02-13

Priority: 1

View other active issues in [flat.map].

View all other issues in [flat.map].

View all issues with WP 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 Status changed: Immediate → WP.]

Proposed resolution:

This wording is relative to N4928.

  1. Add a new bullet to 24.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 24.6.9.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:
        […]
        // 24.6.9.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 24.6.9.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 24.6.10.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:
        […]
        // 24.6.10.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 24.6.10.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 24.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 24.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 24.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 24.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.