double을 임의의 bin으로 분류합니다.

Question

부동 소수점 숫자를 임의의 bin으로 분류하는 클래스를 찾고 있습니다. 쓰레기통. 원하는 구문은 무언가 같은 : 나는 높이고 STL로 제한 해요 이동성 요구 사항으로 인해 불행하게도

std::vector<double> bin_vector; 

// ..... fill the vector with 1, 1.4, 5, etc not evenly spaced values 

Binner bins(bin_vector); 

for (std::vector<double>::const_iterator d_itr = some_vector.begin(); 
    d_itr != some_vector.end(); d_itr++) { 
    int bin = bins.categorize(*d_itr); 

    // bin would be 0 for x < 1, 1 for 1 < x < 1.4, etc 
    // do something with bin 
} 

. 지도를 사용하여 자신의 O (log n) 솔루션을 굴려 사용자 정의 범위 객체에 <을 오버로드했지만 그 해결책은 버그가 발생하기 쉬운 것처럼 보였습니다.

여기에 몇 가지 간단한 stl 또는 boost 객체 솔루션이 있습니까?

Answer 1

bin 번호에 간격 경계를 매핑하는 std :: map을 사용하십시오. 그런 다음 .upper_bound()를 사용하여 휴지통을 찾으십시오.

Answer 2

임의의 길이 M의 입력 벡터와 N-1 bin 경계의 정렬 된 벡터를 취하고 N 개의 빈 수의 벡터를 반환하는 테스트되지 않은 일반 알고리즘입니다. Bin은 간격 [나누기 [i-1], 나누기 [i])의 값을 계산합니다. 유형 T1과 T2는 서로 비교 가능해야합니다. 복잡도는 O (M * log (N))와 같습니다.

#include<algorithm>  // std::is_sorted, std::lower_bound 
#include<cassert>  // assert 
#include<iterator>  // std::distance 
#include<vector>  // std::vector 

template<typename T1, typename T2> 
std::vector<std::size_t> bin_count(const std::vector<T1>& input, const std::vector<T2>& breaks) 
{ 
    // breaks is a sorted vector -INF < a0 < a1 < ... < aN-2 < +INF 
    assert(std::is_sorted(breaks.begin(), breaks.end())); 
    auto N = breaks.size() + 1; 

    std::vector<std::size_t> output(N, 0); 

    if (N == 1) { 
     // everything is inside [-INF, INF) 
     output[0] = input.size(); 
     return output; 
    } 

    for(auto it = input.begin(), it != input.end(); ++it) { 
     if (*it < breaks.front()) { 
      // first bin counts values in [-INF, a0) 
      ++output[0]; 
      break; 
     } 
     if (*it >= breaks.back()) { 
      // last bin counts values in [aN-1, +INF) 
      ++output[N-1]; 
      break; 
     } 

     const auto break_it = std::lower_bound(breaks.begin(), breaks.end(), *it); 
     bin_index = std::distance(breaks.begin(), break_it) + 1; 
     ++output[bin_index]; 
    } 

    return output; 
}