Отправлено: 05.11.18 16:05. Заголовок: Найти максимальную длину подпоследовательности, все элементы которой содержат заданное значение

Эта тема создана на основе данного вопроса на сайте Stackoverflow Sequence with largest size of subsequence having each element as same.

Автор вопроса пытается выполнить поставленную задачу для массива с помощью следующего объявления функции

 
 int large(int a[],int n):

Такой подход совершенно не годится. Во-первых, указатель на элемент массива должен иметь квалификатор const. Во-вторых,тип второго параметра,задающего число элементов в массиве, а также тип возвращаемого значения должен быть задан как size_t. И, в третьих, значение объекта, для которого ищется максимальная длина подпоследовательности, также должно быть задано в списке параметров функции, а не быть "зашито" в тело самой функции.

С учетом всего сказанного объявление функции должно выглядеть следующим образом

size_t large(const int *a, size_t n, int value );

Но эта функция определена, фактически, в стиле C-функции для массивов конкретного типа элементов int.

Если нужно использовать подобную функцию с массивами других типов, то функцию следует определить как шаблонную функцию. Например,

 
 template <typename T1, typename T2> 
 size_t max_subsequence_length( const T1 *a, size_t n, const T2 &value )  
 { 
     size_t max_length = 0; 
      
     for ( auto first = a, last = a + n; 
           ( first = std::find( first, last, value ) ) != last; ) 
     { 
         size_t n = 0; 
          
         for ( ; first != last && *first == value; ++first ) ++n; 
          
         if ( max_length < n ) max_length = n; 
     } 
      
     return max_length; 
 }

Функцию можно сделать еще более обобщенной, если ее написать в виде алгоритма, принимающего диапазон итераторов. Например,

 
 template <typename InputIterator, typename T> 
 typename std::iterator_traits<InputIterator>::difference_type  
 max_subsequence_length( InputIterator first, InputIterator last, const T &value )  
 { 
     typename std::iterator_traits<InputIterator>::difference_type max_length = 0; 
      
     while ( ( first = std::find( first, last, value ) ) != last ) 
     { 
         typename std::iterator_traits<InputIterator>::difference_type n = 0; 
          
         for ( ; first != last && *first == value; ++first ) ++n; 
          
         if ( max_length < n ) max_length = n; 
     } 
      
     return max_length; 
 } 
 

Но этот подход не учитывает такую возможность, как работа с ассоциативными упорядоченными контейнерами такими, как, например, std::multiset. В таких контейнерах имеется метод equal_range, который сразу же позволяет получить требуемое значение. Поэтому можно написать данную функцию, которая на вход получает константную ссылку на весь контейнер, и если контейнер имеет метод equal_range, то использовать именно его для решения поставленной задачи.

В связи с этим в общей список функций можно добавить еще две перегруженные функции.

 
 template <typename Container, typename T> 
 size_t max_subsequence_length( const Container &container, const T &value )  
     requires requires() { &Container::equal_range; } 
 { 
     auto p = container.equal_range( value ); 
     return std::distance( p.first, p.second ); 
 } 
  
 template <typename Container, typename T> 
 size_t max_subsequence_length( const Container &container, const T &value )  
 { 
     size_t max_length = 0; 
      
     for ( auto first = std::begin( container ), last = std::end( container ); 
           ( first = std::find( first, last, value ) ) != last; ) 
     { 
         size_t n = 0; 
          
         for ( ; first != last && *first == value; ++first ) ++n; 
          
         if ( max_length < n ) max_length = n; 
     } 
      
     return max_length; 
 } 
 

Ниже представлена демонстрационная программа, показывающая использование всех перечисленных функций.

 
 #include <iostream> 
 #include <sstream> 
 #include <iterator> 
 #include <algorithm> 
 #include <forward_list> 
 #include <set> 
  
 template <typename Container, typename T> 
 size_t max_subsequence_length( const Container &container, const T &value )  
     requires requires() { &Container::equal_range; } 
 { 
     auto p = container.equal_range( value ); 
     return std::distance( p.first, p.second ); 
 } 
  
 template <typename Container, typename T> 
 size_t max_subsequence_length( const Container &container, const T &value )  
 { 
     size_t max_length = 0; 
      
     for ( auto first = std::begin( container ), last = std::end( container ); 
           ( first = std::find( first, last, value ) ) != last; ) 
     { 
         size_t n = 0; 
          
         for ( ; first != last && *first == value; ++first ) ++n; 
          
         if ( max_length < n ) max_length = n; 
     } 
      
     return max_length; 
 } 
  
 template <typename T1, typename T2> 
 size_t max_subsequence_length( const T1 *a, size_t n, const T2 &value )  
 { 
     size_t max_length = 0; 
      
     for ( auto first = a, last = a + n; 
           ( first = std::find( first, last, value ) ) != last; ) 
     { 
         size_t n = 0; 
          
         for ( ; first != last && *first == value; ++first ) ++n; 
          
         if ( max_length < n ) max_length = n; 
     } 
      
     return max_length; 
 } 
  
 template <typename InputIterator, typename T> 
 typename std::iterator_traits<InputIterator>::difference_type  
 max_subsequence_length( InputIterator first, InputIterator last, const T &value )  
 { 
     typename std::iterator_traits<InputIterator>::difference_type max_length = 0; 
      
     while ( ( first = std::find( first, last, value ) ) != last ) 
     { 
         typename std::iterator_traits<InputIterator>::difference_type n = 0; 
          
         for ( ; first != last && *first == value; ++first ) ++n; 
          
         if ( max_length < n ) max_length = n; 
     } 
      
     return max_length; 
 } 
  
 int main()  
 { 
     std::forward_list<int> lst = { 1, 2, 2, 3, 3, 3, 4 }; 
     std::multiset<int> m = { 1, 2, 2, 3, 3, 3, 4 }; 
     int a[] = { 1, 2, 2, 3, 3, 3, 4 }; 
     std::istringstream is( "1 2 2 3 3 3 4" );  
      
     std::cout << max_subsequence_length( lst, 3 ) << '\n'; 
     std::cout << max_subsequence_length( a, 3 ) << '\n'; 
     std::cout << max_subsequence_length( a, std::size( a ), 3 ) << '\n'; 
     std::cout << max_subsequence_length( m, 3 ) << '\n'; 
     std::cout << max_subsequence_length( std::istream_iterator<int>( is ), {}, 3 ) << '\n'; 
 } 
 

Вывод программы на консоль:

 
 3 
 3 
 3 
 3 
 3

Используя функцию, принимающую два итератора, можно реализацию других функций за исключением той, которая использует член класса equal_range, сделать унифицированной.

 
 #include <iostream>  
 #include <sstream>  
 #include <iterator> 
 #include <algorithm> 
 #include <forward_list>  
 #include <set>  
  
 template <typename InputIterator, typename T>  
 typename std::iterator_traits<InputIterator>::difference_type   
 max_subsequence_length( InputIterator first, InputIterator last, const T &value )   
 {  
     typename std::iterator_traits<InputIterator>::difference_type max_length = 0;  
        
     while ( ( first = std::find( first, last, value ) ) != last )  
     {  
         typename std::iterator_traits<InputIterator>::difference_type n = 0;  
            
         for ( ; first != last && *first == value; ++first ) ++n;  
            
         if ( max_length < n ) max_length = n;  
     }  
        
     return max_length;  
 }  
    
  
 template <typename Container, typename T>  
 size_t max_subsequence_length( const Container &container, const T &value )   
     requires requires() { &Container::equal_range; }  
 {  
     auto p = container.equal_range( value );  
     return std::distance( p.first, p.second );  
 }  
    
 template <typename Container, typename T>  
 size_t max_subsequence_length( const Container &container, const T &value )   
 { 
     return max_subsequence_length( std::begin( container ), std::end( container ), value );  
 }  
   
 template <typename T1, typename T2>  
 size_t max_subsequence_length( const T1 *a, size_t n, const T2 &value )   
 {  
     return max_subsequence_length( a, a + n, value );  
 }  
    
 int main()   
 {  
     std::forward_list<int> lst = { 1, 2, 2, 3, 3, 3, 4 };  
     std::multiset<int> m = { 1, 2, 2, 3, 3, 3, 4 };  
     int a[] = { 1, 2, 2, 3, 3, 3, 4 };  
     std::istringstream is( "1 2 2 3 3 3 4" );   
        
     std::cout << max_subsequence_length( lst, 3 ) << '\n';  
     std::cout << max_subsequence_length( a, 3 ) << '\n';  
     std::cout << max_subsequence_length( a, std::size( a ), 3 ) << '\n';  
     std::cout << max_subsequence_length( m, 3 ) << '\n';  
     std::cout << max_subsequence_length( std::istream_iterator<int>( is ), {}, 3 ) << '\n';  
 }  
 

Что еще можно добавить к семейству показанных перегруженных функций?

Например, можно оптимизировать поиск подпоследовательности элементов с равными значениями для итераторов произвольного доступа на основе условия, что если длина текущей последовательности уже меньше длины найденной максимальной подпоследовательности, то поиск следующей подпоследовательности уже можно прекратить.

Ниже представлена соответствующая демонстрационная программа с новой перегруженной функцией для итераторов произвольного доступа. Для наглядности в каждую из функций включен вывод диагностического сообщения.

 
 #include <iostream>  
 #include <sstream> 
 #include <type_traits> 
 #include <iterator> 
 #include <algorithm> 
 #include <forward_list>  
 #include <set>  
  
 template <typename InputIterator, typename T>  
 typename std::iterator_traits<InputIterator>::difference_type   
 max_subsequence_length( InputIterator first, InputIterator last, const T &value )   
 { 
     std::cout << "max_subsequence_length with iterators is called.\n"; 
     typename std::iterator_traits<InputIterator>::difference_type max_length = 0;  
        
     while ( ( first = std::find( first, last, value ) ) != last )  
     {  
         typename std::iterator_traits<InputIterator>::difference_type n = 0;  
            
         for ( ; first != last && *first == value; ++first ) ++n;  
            
         if ( max_length < n ) max_length = n;  
     }  
        
     return max_length;  
 }  
    
 template <typename InputIterator, typename T>  
 typename std::iterator_traits<InputIterator>::difference_type   
 max_subsequence_length( InputIterator first, InputIterator last, const T &value )   
     requires std::is_same_v<typename std::iterator_traits<InputIterator>::iterator_category, std::random_access_iterator_tag> 
 { 
     std::cout << "max_subsequence_length with random_access_iterators is called.\n"; 
     typename std::iterator_traits<InputIterator>::difference_type max_length = 0;  
        
     while ( max_length < std::distance( first, last ) && ( first = std::find( first, last, value ) ) != last )  
     {  
         typename std::iterator_traits<InputIterator>::difference_type n = 0;  
            
         for ( ; first != last && *first == value; ++first ) ++n;  
            
         if ( max_length < n ) max_length = n;  
     }  
        
     return max_length;  
 }  
    
 template <typename Container, typename T>  
 size_t max_subsequence_length( const Container &container, const T &value )   
     requires requires() { &Container::equal_range; }  
 {  
     std::cout << "max_subsequence_length with equal_range is called.\n"; 
     auto p = container.equal_range( value );  
     return std::distance( p.first, p.second );  
 }  
    
 template <typename Container, typename T>  
 size_t max_subsequence_length( const Container &container, const T &value )   
 { 
     std::cout << "max_subsequence_length with a container is called.\n"; 
     return max_subsequence_length( std::begin( container ), std::end( container ), value );  
 }  
   
 template <typename T1, typename T2>  
 size_t max_subsequence_length( const T1 *a, size_t n, const T2 &value )   
 {  
     std::cout << "max_subsequence_length with an array is called.\n"; 
     return max_subsequence_length( a, a + n, value );  
 }  
    
 int main()   
 {  
     std::forward_list<int> lst = { 1, 2, 2, 3, 3, 3, 4 };  
     std::multiset<int> m = { 1, 2, 2, 3, 3, 3, 4 };  
     int a[] = { 1, 2, 2, 3, 3, 3, 4 };  
     std::istringstream is( "1 2 2 3 3 3 4" );   
        
     std::cout << max_subsequence_length( lst, 3 ) << '\n';  
     std::cout << max_subsequence_length( a, 3 ) << '\n';  
     std::cout << max_subsequence_length( a, std::size( a ), 3 ) << '\n';  
     std::cout << max_subsequence_length( m, 3 ) << '\n';  
     std::cout << max_subsequence_length( std::istream_iterator<int>( is ), {}, 3 ) << '\n';  
 } 

Вывод программы на консоль:

 
 max_subsequence_length with a container is called. 
 max_subsequence_length with iterators is called. 
 3 
 max_subsequence_length with a container is called. 
 max_subsequence_length with random_access_iterators is called. 
 3 
 max_subsequence_length with an array is called. 
 max_subsequence_length with random_access_iterators is called. 
 3 
 max_subsequence_length with equal_range is called. 
 3 
 max_subsequence_length with iterators is called. 
 3

 Отправлено: 07.11.18 17:07. Заголовок: -#include <iostr..

Предыдущая реализация перегруженных функций не учитывала то, что, например, массив может быть отсортированным, а потому для поиска максимальной длины подпоследовательности элементов, содержащих равные значения, было бы эффективнее применить стандартный алгоритм std::equal_range вместо последовательного поиска с помощью стандартного алгоритма std::find.
Поэтому для большинства реализованных функций следует добавить еще один параметр типа bool, который сообщает, является ли последовательность отсортированной или нет.

Ниже приведена демонстрационная программа, показывающая, как можно реализовать такой подход. В реализацию перегруженных функций для наглядности включена тестовая печать на консоль, которую, естественно, при желании можно убрать.

 
 #include <iostream>   
 #include <sstream>  
 #include <type_traits>  
 #include <iterator>  
 #include <algorithm>  
 #include <forward_list>   
 #include <set>   
    
 template <typename InputIterator, typename T>   
 typename std::iterator_traits<InputIterator>::difference_type    
 max_subsequence_length( InputIterator first, InputIterator last, const T &value )    
 {  
     std::cout << "max_subsequence_length with input iterators is called.\n";  
     using difference_type = typename std::iterator_traits<InputIterator>::difference_type; 
       
     difference_type max_length = 0;   
          
     while ( ( first = std::find( first, last, value ) ) != last )   
     {   
         difference_type n = 0;   
              
         for ( ; first != last && *first == value; ++first ) ++n;   
              
         if ( max_length < n ) max_length = n;   
     }   
          
     return max_length;   
 }   
      
 template <typename RandomAccessIterator, typename T>   
 typename std::iterator_traits<RandomAccessIterator>::difference_type    
 max_subsequence_length( RandomAccessIterator first, RandomAccessIterator last, const T &value, bool sorted = false )    
     requires std::is_same_v<typename std::iterator_traits<RandomAccessIterator>::iterator_category, std::random_access_iterator_tag>  
 {  
     using difference_type = typename std::iterator_traits<RandomAccessIterator>::difference_type; 
       
     difference_type max_length = 0;   
  
     if ( sorted ) 
     { 
         std::cout << "max_subsequence_length with random access iterators for a sorted sequence is called.\n";  
         auto p = std::equal_range( first, last, value ); 
          
         max_length = std::distance( p.first, p.second ); 
     } 
     else 
     { 
         std::cout << "max_subsequence_length with random access iterators is called.\n";  
         while ( max_length < std::distance( first, last ) && ( first = std::find( first, last, value ) ) != last )   
         {   
             difference_type n = 0;   
              
             for ( ; first != last && *first == value; ++first ) ++n;   
              
             if ( max_length < n ) max_length = n;   
         } 
     }         
          
     return max_length;   
 }   
  
 template <typename ForwardIterator, typename T>   
 typename std::iterator_traits<ForwardIterator>::difference_type    
 max_subsequence_length( ForwardIterator first, ForwardIterator last, const T &value, bool sorted = false )    
     requires std::is_same_v<typename std::iterator_traits<ForwardIterator>::iterator_category, std::forward_iterator_tag> || 
              std::is_same_v<typename std::iterator_traits<ForwardIterator>::iterator_category, std::bidirectional_iterator_tag> 
 {  
     using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; 
       
     difference_type max_length = 0;   
  
     if ( sorted ) 
     { 
         std::cout << "max_subsequence_length with forward_iterators for a sorted sequence is called.\n";  
         first = std::lower_bound( first, last, value ); 
          
         for ( ; first != last && *first == value; ++first ) ++max_length; 
     } 
     else 
     { 
         std::cout << "max_subsequence_length with forward_iterators is called.\n";  
         while ( ( first = std::find( first, last, value ) ) != last )   
         {   
             difference_type n = 0;   
              
             for ( ; first != last && *first == value; ++first ) ++n;   
              
             if ( max_length < n ) max_length = n;   
         }   
     }         
          
     return max_length;   
 }   
  
 template <typename Container, typename T>   
 size_t max_subsequence_length( const Container &container, const T &value )    
     requires requires() { &Container::equal_range; }   
 {   
     std::cout << "max_subsequence_length with equal_range is called.\n";  
  
     auto p = container.equal_range( value );   
     return std::distance( p.first, p.second );   
 }   
      
 template <typename Container, typename T>   
 size_t max_subsequence_length( const Container &container, const T &value, bool sorted = false )    
 {  
     std::cout << "max_subsequence_length with a container is called.\n";  
     return max_subsequence_length( std::begin( container ), std::end( container ), value, sorted );   
 }   
     
 template <typename T1, typename T2>   
 size_t max_subsequence_length( const T1 *a, size_t n, const T2 &value, bool sorted ) 
 {   
     std::cout << "max_subsequence_length with an array is called.\n";  
     return max_subsequence_length( a, a + n, value, sorted );   
 }   
      
 int main()    
 {   
     std::forward_list<int> lst = { 1, 2, 2, 3, 3, 3, 4 };   
     std::multiset<int> m = { 1, 2, 2, 3, 3, 3, 4 };   
     int a[] = { 1, 2, 2, 3, 3, 3, 4 };   
     std::istringstream is( "1 2 2 3 3 3 4" );    
          
     std::cout << "std::forward_list<int>:\n"; 
     std::cout << max_subsequence_length( lst, 3 ) << '\n';   
  
     std::cout << "sorted std::forward_list<int>:\n"; 
     std::cout << max_subsequence_length( lst, 3, true ) << '\n';   
  
     std::cout << '\n'; 
  
     std::cout << "int a[] as a container:\n"; 
     std::cout << max_subsequence_length( a, 3 ) << '\n';   
     std::cout << "sorted int a[] as a container:\n"; 
     std::cout << max_subsequence_length( a, 3, true ) << '\n';   
     std::cout << "int a[] as an array:\n"; 
     std::cout << max_subsequence_length( a, std::size( a ), 3, false ) << '\n';   
     std::cout << "int a[] as a sorted array:\n"; 
     std::cout << max_subsequence_length( a, std::size( a ), 3, true ) << '\n';   
     std::cout << '\n'; 
  
     std::cout << "std::multiset<int>:\n"; 
     std::cout << max_subsequence_length( m, 3 ) << '\n';   
     std::cout << '\n'; 
      
     std::cout << "string stream iterators:\n"; 
     std::cout << max_subsequence_length( std::istream_iterator<int>( is ), {}, 3 ) << '\n';   
     std::cout << '\n'; 
 }

-
Вывод программы на консоль:

 
 std::forward_list<int>: 
 max_subsequence_length with a container is called. 
 max_subsequence_length with forward_iterators is called. 
 3 
 sorted std::forward_list<int>: 
 max_subsequence_length with a container is called. 
 max_subsequence_length with forward_iterators for a sorted sequence is called. 
 3 
  
 int a[] as a container: 
 max_subsequence_length with a container is called. 
 max_subsequence_length with random access iterators is called. 
 3 
 sorted int a[] as a container: 
 max_subsequence_length with a container is called. 
 max_subsequence_length with random access iterators for a sorted sequence is called. 
 3 
 int a[] as an array: 
 max_subsequence_length with an array is called. 
 max_subsequence_length with random access iterators is called. 
 3 
 int a[] as a sorted array: 
 max_subsequence_length with an array is called. 
 max_subsequence_length with random access iterators for a sorted sequence is called. 
 3 
  
 std::multiset<int>: 
 max_subsequence_length with equal_range is called. 
 3 
  
 string stream iterators: 
 max_subsequence_length with input iterators is called. 
 3