STL中partition分区排序算法

用户9831583

发布于 2022-06-16 15:20:06

7820

1.partition()

使给定谓词返回 true 的元素会被放在所有使谓词返回 false 的元素的前面。

参数定义：前两个参数是被分区序列范围的正向迭代器，第三个参数是一个谓词。

   std::vector<double> temperatures {65, 75, 56, 48, 31, 28, 32, 29, 40, 41, 44, 50};
    std::copy(std::begin(temperatures), std::end(temperatures),
    std::ostream_iterator<double>{std::cout, " "});
    std::cout << std::endl;
    //计算平均值
    auto average = std::accumulate(std::begin(temperatures),std::end(temperatures), 0.0)/temperatures.size();
    std::cout << "Average temperature: "<< average << std::endl;
    std::partition(std::begin(temperatures), std::end(temperatures),[average](double t) { return t < average; });
    std::copy(std::begin(temperatures), std::end(temperatures),std::ostream_iterator<double>{std::cout, " "});
    std::cout << std::endl;

结果显示：

2.stable_partition()

partition() 算法并不保证维持这个序列原始元素的相对顺序。为了维持元素的相对顺序，使用 stable_partition() 算法。

std::stable_partition(std::begin(temperatures), std::end(temperatures),[average](double t) { return t < average; });

这个谓词可以不必是用来处理顺序关系的，可以是我们喜欢的任何样子。

     /2
     using gender = char;
    using first = string;
    using second= string;
    using Name = std::tuple<first, second, gender>;
    std:: vector<Name> names{std::make_tuple ("Dan", "old", 'm'),std::make_tuple("Ann", "old", 'f'),std::make_tuple ("Ed", "old",'m'),std::make_tuple ("Jan", "old", 'f'), std::make_tuple ("Edna", "old", 'f')};
    std::partition(std::begin(names), std::end(names),
                    [](const Name name) { return std::get<2>(name) == 'f'; });
    for(const auto& name : names)
        std:: cout << std::get<0> (name) << " "<< std::get<1> (name) << std::endl;

结果显示：

3.partition_copy()

partition_copy() 算法以和 stable_partition() 相同的方式对序列进行分区，但那些使谓词返回 true 的元素会被复制到一个单独的序列中，使谓词返回 false 的那些元素会被复制到第三个序列中。这个操作不会改变原始序列。

参数定义：原始序列由前两个参数指定，它们必须是输入迭代器。第 3 个参数用来确定目的序列的开始位置，它会保存那些使谓词返回 true 的元素。第 4 个参数用来确定另一个的序列的开始位置，它会保存那些使谓词返回 false 的元素。第 5 个参数是用来分区元素的谓词。

  #include <iostream>                            
    #include <vector>                                
    #include <algorithm>                            
    #include <numeric>                              
    #include <iterator>                              
    int main()
    {
        std::vector<double> temperatures {65, 75, 56, 48, 31, 28, 32, 29, 40, 41, 44, 50};
        std::vector<double> low_t;                      
        std::vector<double> high_t;                    
        auto average = std::accumulate(std::begin(temperatures), std::end(temperatures), 0.0) / temperatures.size();
        std::partition_copy(std::begin(temperatures), std::end(temperatures),
                 std::back_inserter(low_t), std::back_inserter(high_t),[average](double t) { return t < average; });
      
        std::copy(std::begin(low_t), std::end(low_t), std::ostream_iterator<double>{std::cout, " "});
        std::cout << std::endl;
      
        std::copy(std::begin(high_t), std::end(high_t), std::ostream_iterator<double>{std::cout, " "});
        std::cout << std::endl;
    }

结果显示：

4.partition_point()

partition_point() 算法来获取分区序列中第一个分区的结束迭代器，它的前两个参数定义检查范围的正向迭代器，最后一个参数是用来对序列进行分区的谓词。

5.is_partitioned()

使用 partition_point() 之前，需要确定序列是否已经被分区。如果对此不是很确定，在这种情况下可以使用 is_partitioned() 来判断。

参数定义：它的参数是用来指定序列的输入迭代器和用来对序列进行分区的谓词。如果这个序列已经被分区，这个算法就返回 true，否则返回 false。

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <iterator>
#include <deque>
#include <tuple>

int main()
{
     std::vector<double> temperatures {65, 75, 56, 48, 31, 28, 32, 29, 40, 41, 44, 50};
    auto average = std::accumulate(std::begin(temperatures),std::end(temperatures), 0.0)/ temperatures.size();
    auto predicate = [average](double t) { return t < average; };
    std::stable_partition(std::begin(temperatures), std::end(temperatures), predicate);
    //用 partition_point() 找到这个序列的分区点。这个分区点是第一个分区的结束迭代器，它被保存在 iter 中
  //  auto iter = std::partition_point(std::begin(temperatures),std::end(temperatures), predicate);
    //所以 [std::begin(temperatures)，iter) 对应的就是第一个分区中的元素，
    //[iter，std::end(temperatures)) 包含的是第二个分区中的元素
  
    if(std::is_partitioned(std::begin(temperatures), std::end(temperatures),
                        [average](double t) { return t < average; }))
    {
        auto iter = std::partition_point(std::begin(temperatures),std::end(temperatures), [average](double t) { return t < average; });
        std::cout << "Elements in the first partition: ";
        std::copy(std::begin(temperatures), iter,std::ostream_iterator<double>{std::cout, " " });
        std::cout << "\nElements in the second partition: ";
        std::copy(iter, std::end(temperatures),std::ostream_iterator<double>{std::cout," "});
        std::cout << std::endl;
    }
    else
        std::cout << "Range is not partitioned." << std::endl;
}

结果显示：