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

4365. boyer_moore_searcher and boyer_moore_horspool_searcher should be constexpr-friendly

Section: 22.10.18.3 [func.search.bm], 22.10.18.4 [func.search.bmh] Status: New Submitter: Hewill Kang Opened: 2025-09-03 Last modified: 2025-09-15

Priority: Not Prioritized

View other active issues in [func.search.bm].

View all other issues in [func.search.bm].

View all issues with New status.

Discussion:

Currently, boyer_moore_searcher and boyer_moore_horspool_searcher are not constexpr-friendly because their underlying implementation needs to precompute the shift table, which usually requires a vector or unordered_map to store.

Thanks to P3372R3, unordered containers are now constexpr-friendly. Although std::hash still lacks constexpr support, users can provide their own hash functions to use unordered containers at compile time.

Given that both boyer_moore_searcher and boyer_moore_horspool_searcher can take a custom hash, it makes perfect sense that they could be constexpr-friendly.

Not to mention that library implementations usually simply use arrays instead of hash tables for the common string case because characters only have 256 values, so unordered_map is not actually used.

Proposed resolution:

This wording is relative to N5014.

1. Modify 22.10.18.3 [func.search.bm] as indicated:

   namespace std {
     template<class RandomAccessIterator1,
              class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
              class BinaryPredicate = equal_to<>>
     class boyer_moore_searcher {
     public:
       constexpr boyer_moore_searcher(RandomAccessIterator1 pat_first,
                                      RandomAccessIterator1 pat_last,
                                      Hash hf = Hash(),
                                      BinaryPredicate pred = BinaryPredicate());
   
       template<class RandomAccessIterator2>
         constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
           operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   
     private:
       RandomAccessIterator1 pat_first_;   // exposition only
       RandomAccessIterator1 pat_last_;    // exposition only
       Hash hash_;                         // exposition only
       BinaryPredicate pred_;              // exposition only
     };
   }
   

   constexpr boyer_moore_searcher(RandomAccessIterator1 pat_first,
                                  RandomAccessIterator1 pat_last,
                                  Hash hf = Hash(),
                                  BinaryPredicate pred = BinaryPredicate());
   

   -1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.

   […]

   template<class RandomAccessIterator2>
     constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
       operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   

   -5- Mandates: RandomAccessIterator1 and RandomAccessIterator2 have the same value type.

2. Modify 22.10.18.4 [func.search.bmh] as indicated:

   namespace std {
     template<class RandomAccessIterator1,
              class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
              class BinaryPredicate = equal_to<>>
     class boyer_moore_horspool_searcher {
     public:
      constexpr boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                                              RandomAccessIterator1 pat_last,
                                              Hash hf = Hash(),
                                              BinaryPredicate pred = BinaryPredicate());
   
       template<class RandomAccessIterator2>
         constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
           operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   
     private:
       RandomAccessIterator1 pat_first_;   // exposition only
       RandomAccessIterator1 pat_last_;    // exposition only
       Hash hash_;                         // exposition only
       BinaryPredicate pred_;              // exposition only
     };
   }
   

   constexpr boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                                           RandomAccessIterator1 pat_last,
                                           Hash hf = Hash(),
                                           BinaryPredicate pred = BinaryPredicate());
   

   -1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.

   […]

   template<class RandomAccessIterator2>
     constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
       operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   

   -5- Mandates: RandomAccessIterator1 and RandomAccessIterator2 have the same value type.