C++ 算法 partial_sort_copy()

2024年8月30日 | 5分钟阅读

C++ 算法 partial_sort_copy() 函数类似于 partial_sort() 函数，用于重新排列范围 [first, last) 中的元素，使得 first 和 middle 之间的元素已排序，而 middle 和 last 之间的元素保持未指定顺序。但 partial_sort_copy() 函数将结果放入新的范围 [result_first, result_last) 中。

第一个版本使用运算符 < 比较元素，第二个版本使用 comp 比较元素。

语法

default (1)      template <class InputIterator, class RandomAccessIterator>
                         RandomAccessIterator
                           partial_sort_copy (InputIterator first,InputIterator last,
                            RandomAccessIterator result_first,
                             RandomAccessIterator result_last);

custom (2)      template <class InputIterator, class RandomAccessIterator, class Compare>
  		RandomAccessIterator
   		 partial_sort_copy (InputIterator first,InputIterator last,
                            RandomAccessIterator result_first,
                              RandomAccessIterator result_last, Compare comp);

参数

first：一个输入迭代器，指向要部分排序的源范围中的第一个元素。

last：一个随机访问迭代器，指向要部分排序的源范围中最后一个元素的后一个位置。

result_first：一个随机访问迭代器，指向已排序目标范围中的第一个元素。

result_last：一个随机访问迭代器，指向已排序目标范围中最后一个元素的后一个位置。

comp：一个用户定义的二元谓词函数，接受两个参数，如果这两个参数有序则返回true，否则返回false。它遵循严格的弱排序来对元素进行排序。

返回值

它返回一个迭代器，指向结果序列中写入的最后一个元素之后的元素。

复杂度

平均复杂度小于 first 和 last 之间距离的对数线性。执行多达 N*log (min (N, M)) 次元素比较，其中 N = last - first，M = middle - first。

数据竞争

范围 [first, last) 中的对象会被更改。

异常

如果任何元素比较、元素交换（或移动）或迭代器操作抛出异常，此函数将抛出异常。

请注意，无效参数会导致未定义行为。

示例 1

让我们看一个简单的例子来演示 partial_sort_copy() 的用法

#include <iostream>     // std::cout
#include <algorithm>    // std::partial_sort_copy
#include <vector>       // std::vector

using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (5);

  // using default comparison (operator <):
  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());

  // using function as comp
  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end(), myfunction);

  // print out content:
  cout << "myvector contains:";
  for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  return 0;
}

输出

myvector contains: 1 2 3 4 5

示例 2

让我们看另一个默认版本的简单示例

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std ;

int main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of int
    typedef vector<int> IntVector ;

    //Define an iterator for template class vector of strings
    typedef IntVector::iterator IntVectorIt ;

    IntVector Numbers(VECTOR_SIZE) ;
    IntVector Result(4) ;

    IntVectorIt start, end, it ;

    // Initialize vector Numbers
    Numbers[0] = 4 ;
    Numbers[1] = 10;
    Numbers[2] = 70 ;
    Numbers[3] = 30 ;
    Numbers[4] = 10;
    Numbers[5] = 69 ;
    Numbers[6] = 96 ;
    Numbers[7] = 7;

    start = Numbers.begin() ;   // location of first
                                // element of Numbers

    end = Numbers.end() ;       // one past the location
                                // last element of Numbers

    cout << "Before calling partial_sort_copy\n" << endl ;

    // print content of Numbers
    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // sort the smallest 4 elements in the Numbers
    // and copy the results in Result
    partial_sort_copy(start, end, Result.begin(), Result.end()) ;

    cout << "After calling partial_sort_copy\n" << endl ;

    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    cout << "Result { " ;
    for(it = Result.begin(); it != Result.end(); it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;
    
    return 0;
}

输出

Before calling partial_sort_copy

Numbers { 4 10 70 30 10 69 96 7  }

After calling partial_sort_copy

Numbers { 4 10 70 30 10 69 96 7  }

Result { 4 7 10 10  }

示例 3

让我们看一个自定义（谓词）版本的简单示例

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std ;

int main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of int
    typedef vector<int> IntVector ;

    //Define an iterator for template class vector of strings
    typedef IntVector::iterator IntVectorIt ;

    IntVector Numbers(VECTOR_SIZE) ;
    IntVector Result(4) ;

    IntVectorIt start, end, it ;

    // Initialize vector Numbers
    Numbers[0] = 4 ;
    Numbers[1] = 10;
    Numbers[2] = 70 ;
    Numbers[3] = 30 ;
    Numbers[4] = 10;
    Numbers[5] = 69 ;
    Numbers[6] = 96 ;
    Numbers[7] = 7;

    start = Numbers.begin() ;   // location of first
                                // element of Numbers

    end = Numbers.end() ;       // one past the location
                                // last element of Numbers

    cout << "Before calling partial_sort_copy\n" << endl ;

    // print content of Numbers
    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // sort the smallest 4 elements in the Numbers
    // and copy the results in Result
    partial_sort_copy(start, end, Result.begin(),Result.end(),less<int>());

    cout << "After calling partial_sort_copy\n" << endl ;

    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    cout << "Result { " ;
    for(it = Result.begin(); it != Result.end(); it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;
    
    return 0;
}

输出

Before calling partial_sort_copy

Numbers { 4 10 70 30 10 69 96 7  }

After calling partial_sort_copy

Numbers { 4 10 70 30 10 69 96 7  }

Result { 4 7 10 10  }

示例 4

让我们看另一个例子

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
using namespace std; 
 
vector<int>::iterator it;

void print(vector<int> & v)
{ 
    for (it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << '\n';
}
 
int main()
{
    vector<int> v0{4, 2, 5, 1, 3};
    vector<int> v1{10, 11, 12};
    vector<int> v2{10, 11, 12, 13, 14, 15, 16};
 
    cout << "v0 : ";
    print(v0);
 
    cout << "v1 : ";
    print(v1);
 
    cout << "v2 : ";
    print(v2);
 
    it = partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
 
    cout << "Writing v0 to v1 in ascending order gives: ";
    print(v1);
 
    it = partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(), 
                                std::greater<int>());
 
    cout << "Writing v0 to v2 in descending order gives: ";
    print(v2);
    
    return 0;
} 

输出

v0 : 4 2 5 1 3 
v1 : 10 11 12 
v2 : 10 11 12 13 14 15 16 
Writing v0 to v1 in ascending order gives: 1 2 3 
Writing v0 to v2 in descending order gives: 5 4 3 2 1 15 16

下一主题C++ 算法

C++ 算法 partial_sort_copy()

语法

参数

返回值

复杂度

数据竞争

异常

请注意，无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 算法 partial_sort_copy()

语法

参数

返回值

复杂度

数据竞争

异常

请注意，无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm count_if() 函数

algorithm is_sorted() 函数

algorithm find_first_of() 函数

algorithm is_partitioned() 函数

algorithm generate() 函数

algorithm copy_n() 函数

algorithm transform() 函数

algorithm replace_copy() 函数

algorithm remove_copy_if() 函数