Re: [Boost-users] Finding the n smallest items in a list

Subject: Re: [Boost-users] Finding the n smallest items in a list
From: Ruediger Berlich (ruediger.berlich_at_[hidden])
Date: 2009-02-04 11:20:19

Marshall, all,
thanks a lot for this hint. Works nicely (see below).
Best, Ruediger

/*************************************************/

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

using namespace std;

main() {
  std::vector<int> p;

  p.push_back(7);
  p.push_back(0);
  p.push_back(3);
  p.push_back(2);
  p.push_back(9);
  p.push_back(8);
  p.push_back(5);
  p.push_back(1);
  p.push_back(4);
  p.push_back(6);

  std::vector<int>::iterator first = p.begin();
  std::vector<int>::iterator middle = first + 3;
  std::vector<int>::iterator last = p.end();

  std::partial_sort(first, middle, last);

  for(std::size_t i=0; i<10; i++) {
    std::cout << p[i] << std::endl;
  }
}

/*************************************************/

Marshall Clow wrote:
>>Hi there,
>>
>>I'm searching for a method to find the n smallest numbers in a list of m
>>>> n numbers. The n numbers need to be sorted. m will usually be in the
>>range of 100-1000, n will be 5 or less. So far I'm simply sorting the
>>entire vector, which I assume is not very efficient, as the other m-n
>>items in the container can remain unsorted. Is there a function in Boost
>>that can help me in this situation ?
> 
> This sounds like a job for std::partial_sort.