Why is std::partition specialized for random access iterators?

[Vlad from Moscow]

Consider the following demonstrative program (I used gcc)

#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <forward_list>
#include <list>


int main()
{
    std::forward_list<int> lst1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
   
    std::partition( std::begin( lst1 ), std::end( lst1 ),
                    std::bind( std::modulus<>(), std::placeholders::_1, 2 ) );
                   
    for ( const auto &item : lst1 ) std::cout << item << ' ';
    std::cout << '\n';


    std::list<int> lst2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
   
    std::partition( std::begin( lst2 ), std::end( lst2 ),
                    std::bind( std::modulus<>(), std::placeholders::_1, 2 ) );
                   
    for ( const auto &item : lst1 ) std::cout << item << ' ';
    std::cout << '\n';
   
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
   
    std::partition( std::begin( a ), std::end( a ),
                    std::bind( std::modulus<>(), std::placeholders::_1, 2 ) );
                   
    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';
}

Its output is

1 3 5 7 9 2 6 0 8 4 
1 3 5 7 9 2 6 0 8 4 
9 1 7 3 5 4 6 2 8 0 

As it can be seen the result of calling std::partition for the array is different from the results obtained for std::forward_list and std::list.

It looks like that std;:partition used for arrays applies the algorithm that is the same as the algorithm that can be written for bidirectional iterators.

However std::list that also has bidirectional iterators uses the specialization of std::partition for forward iterators.

Why is std::partition is specialized for random access iterators?

And why does not std;:list uses the specialization of std::partition for bidirectional iterators?

Should there be only one specialization of std::partition only for forward iterators?
 

[Vlad from Moscow]

Oh, I made a typo in this loop

    for ( const auto &item : lst1 ) std::cout << item << ' ';
    std::cout << '\n';

while trying to output lst2.

Now the question is do we need a specialization of std::partition for bidirectional iterators? Should it be only one specialization for forward iterators? What is the purpose of keeping two specializations?

пятница, 28 июня 2019 г., 17:13:12 UTC+3 пользователь Vlad from Moscow написал: