| stl의 binary search를 잘못 사용 하고 있었다. lower_bound를 사용하면 되는데 binary_search 코드를 비비 꼬아서 잘못 사용했다. binary_search.html 에 나와 있는것은 사용하지 말자. 지울까 고민했지만 그냥 남겨 둔다. lower_bound 함수를 사용하기 위해서는 미리 소팅 되어 있어야 한다. 공통적으로 사용하는 헤더와 코드는 다음과 같다. #include <vector>
#include <algorithm> #include <iostream> using namespace std; lower_bound는 "algorithm" 헤더에 다음과 같이 정의 되어 있다. template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value ); template< class ForwardIt, class T, class Compare > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); 범위 [first, last]에서 value보다 크거나 같은 첫번째 요소를 가리키는 iterator를 리턴한다. 기본 데이터 타입을 사용하는 경우 비교함수를 만들 필요가 없다. 아래는 설명을 위해 비교 함수를 만들었다. 비교 함수 사용하기void PrintVec(vector<int> vec)
{ for(unsigned int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl; } bool comp(const int& lhs, const int& rhs) { return lhs < rhs; } void Print(const vector<int>& vec, int value) { vector<int>::const_iterator iter = lower_bound(vec.begin(), vec.end(), value, comp); if(iter == vec.end()) iter = vec.end() - 1; cout << value << "> index: " << iter - vec.begin() << ", value : " << *iter << endl; } void TestFunction() { const int arr[] = {3, 7, 9, 10, 20, 40, 100}; vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0])); Print(vec, 2); Print(vec, 10); Print(vec, 20); Print(vec, 15); Print(vec, 100); Print(vec, 110); } 결과) 2> index: 0, value : 3 10> index: 3, value : 10 20> index: 4, value : 20 15> index: 4, value : 20 100> index: 6, value : 100 110> index: 6, value : 100 구조체인 경우 비교 함수 사용struct PairInt
{ int key; int value; }; bool ComparePairInt(const PairInt& lhs, const int value) { return lhs.key < value; } void PrintPairInt(const vector<PairInt>& vec, int key) { vector<PairInt>::const_iterator iter = lower_bound(vec.begin(), vec.end(), key, ComparePairInt); if(iter == vec.end()) iter = vec.end() - 1; cout << key << "> key: " << iter->key << ", value : " << iter->value << endl; } void TestStructFunc() { const PairInt arr[] = {{3, 10}, {7, 30}, {9, 100}, {10, 0}}; vector<PairInt> vec (arr, arr + sizeof(arr) / sizeof(arr[0])); PrintPairInt(vec, 7); PrintPairInt(vec, 8); PrintPairInt(vec, 15); } 결과) 7> key: 7, value : 30 8> key: 9, value : 100 15> key: 10, value : 0 구조체인 경우 비교 클래스(구조체) 사용클래스(구조체)로 비교 할때는 operator 연산자를 사용해서 검색한다.struct CompreInt
{ bool operator () (const PairInt & lhs, int key) const { return lhs.key < key; } bool operator () (const PairInt lhs, const PairInt & rhs) const { return lhs.key < rhs.key; } }; void PrintClass(const vector<PairInt>& vec, int key) { vector<PairInt>::const_iterator iter = lower_bound(vec.begin(), vec.end(), key, CompreInt()); if(iter == vec.end()) iter = vec.end() - 1; cout << key << "> key: " << iter->key << ", value : " << iter->value << endl; } void TestStruct() { const PairInt arr[] = {{3, 10}, {7, 30}, {9, 100}, {10, 0}}; vector<PairInt> vec (arr, arr + sizeof(arr) / sizeof(arr[0])); PrintClass(vec, 7); PrintClass(vec, 8); PrintClass(vec, 15); PairInt tmp = {8, 0}; vector<PairInt>::const_iterator iter = lower_bound(vec.begin(), vec.end(), tmp, CompreInt()); cout << tmp.key << " " << iter->key << endl; tmp.key = 7; iter = lower_bound(vec.begin(), vec.end(), tmp, CompreInt()); cout << tmp.key << " " << iter->key << endl; } 결과) 7> key: 7, value : 30 8> key: 9, value : 100 15> key: 10, value : 0 8 9 7 7 실제 : Key에 따라 보정하기key에 따라 값을 보정한다. (key, value) 값이 다음과 같이 주어질때,(3, 10), (7, 30) , (10, 100) , (20, 0) 다음과 같이 key에 따라 값이 보정 되어야 한다. key가 2이면 값은 10, key가 인덱스 0보다 작으면 보간을 하지 않고 최초 값을 사용한다. key가 3이면 값은 10 key가 100이면 값은 0, key가 인덱스 마지막 보다 크면 보간을 하지 않고 마지막 값을 사용한다. key가 5이면 20, 10~30의 0.5는 20이다. key가 11이면 90, 100~0의 0.1은 90이다. NumberMid.h 파일 #ifndef _NUMBER_MID
#define _NUMBER_MID #include <vector> #include <algorithm> #include <iostream> //must be Ascending sorting before using Find function. template <class T1, class T2> class NumberMid { protected: struct Node { T1 key; T2 value; }; std::vector<Node> m_list; public: static bool Compare(const Node& lhs, const T1 key) { return lhs.key < key; } void Add(const T1 key, const T2 value) { Node node = {key, value}; m_list.push_back(node); } T2 Find(const T1 key) { vector<Node>::const_iterator iter = lower_bound(m_list.begin(), m_list.end(), key, NumberMid::Compare); if(iter == m_list.end()) iter = m_list.end() - 1; return iter->value; } T2 FindMid(const T1 key) { vector<Node>::const_iterator iter = lower_bound(m_list.begin(), m_list.end(), key, NumberMid::Compare); if(iter == m_list.end()) iter = m_list.end() - 1; if(iter == m_list.begin()) return iter->value; vector<Node>::const_iterator prev = iter-1; float diff = iter->key - prev->key; float alpha = (key - prev->key) / diff; T2 value = (1.0f - alpha)*prev->value + alpha*iter->value; return value; } }; #endif 테스트 소스 NumberMid<float, float> mid;
mid.Add(3, 10); mid.Add(7, 30); mid.Add(10, 100); mid.Add(20, 0); float ret1 = mid.Find(7); float ret2 = mid.Find(8); float ret3 = mid.Find(15); float ret4 = mid.FindMid(11); float ret5 = mid.FindMid(5); cout << "7: " << ret1 << endl; cout << "8: " << ret2 << endl; cout << "15: " << ret3 << endl; cout << "11: " << ret4 << endl; cout << "5: " << ret5 << endl; 결과) 7: 30 8: 100 15: 0 11: 90 5: 20 참조) http://blogginman.blogspot.com/2005/09/c-tip-lowerbound-and-functors.html?m=1 https://heisseswasser.hatenadiary.org/entry/20100308/1268043943 https://ohmist.tistory.com/m/2 |