fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. namespace
  8. {
  9. 	class SomeBigObj
  10. 	{
  11. 	private:
  12. 		double m_fVal;
  13. 	public:
  14. 		SomeBigObj() : m_fVal(0.0) { }
  15. 		SomeBigObj(const double x) : m_fVal(x) { }
  16. 		bool operator<(const SomeBigObj& rhs) const { return (m_fVal < rhs.m_fVal); }
  17. 		double get() const { return m_fVal; }
  18. 	};
  19.  
  20. }   // namespace
  21.  
  22. const SomeBigObj srcArr[] = {
  23. 	3.1, 4.1, 5.9, 2.6, 5.3, 5.8, 9.7, 9.3, 2.3, 8.4, 4.6, 2.6, 4.3, 3.8, 3.2, 7.9, 5.0, 2.8, 8.4, 1.9
  24. };
  25.  
  26. /// 配列内容表示
  27. void printarr(const std::vector<SomeBigObj>& arr, std::vector<int>& indices)
  28. {
  29. 	assert(arr.size() == indices.size());
  30.  
  31. 	const size_t arrsz = arr.size();
  32.  
  33. 	printf("arr[] : (");
  34. 	for (size_t i = 0; i < arrsz; i++) {
  35. 		printf(" %3.1f", arr[indices[i]].get());
  36. 	}
  37. 	printf(" )\n");
  38.  
  39. 	printf("idx[] : (");
  40. 	for (size_t i = 0; i < arrsz; i++) {
  41. 		printf(" %3d", indices[i]);
  42. 	}
  43. 	printf(" )\n");
  44. }
  45.  
  46. /// lower_bound結果検証
  47. bool chk_lb(const std::vector<SomeBigObj>& arr, std::vector<int>& indices, const SomeBigObj& x, const int lb)
  48. {
  49. 	assert(arr.size() == indices.size());
  50.  
  51. 	const size_t arrsz = arr.size();
  52.  
  53. 	assert(0 <= lb && (size_t)lb < arrsz);
  54.  
  55. 	for (size_t i = 0; i < (size_t)lb; i++) {
  56. 		if (!(arr[indices[i]] < x)) {
  57. 			printf("ERROR: Illegal LB (1) (i=%zu)\n", i);
  58. 			return false;
  59. 		}
  60. 	}
  61. 	for (size_t i = (size_t)lb; i < arrsz; i++) {
  62. 		if (arr[indices[i]] < x) {
  63. 			printf("ERROR: Illegal LB (2) (i=%zu)\n", i);
  64. 			return false;
  65. 		}
  66. 	}
  67.  
  68. 	return true;
  69. }
  70.  
  71. /// 間接ソート版lower_bound
  72. int custom_lower_bound(const std::vector<SomeBigObj>& arr, std::vector<int>& indices, const SomeBigObj& x)
  73. {
  74. 	// SomeBigObjの間接ソート用比較関数
  75. 	// xのコピーを避けるため[&](a, b)とする。
  76. 	auto cmpFunc = [&](const int idx, const SomeBigObj& xx)->bool {
  77. 		return arr[idx] < xx;
  78.  
  79. 	};
  80. 	auto found_it = std::lower_bound(indices.begin(), indices.end(), x, cmpFunc);
  81. 	// Indexに変換
  82. 	return (int)std::distance(indices.begin(), found_it);
  83. }
  84.  
  85. int main()
  86. {
  87. 	// 間接ソート対象データ作成
  88. 	std::vector<SomeBigObj> arr;
  89. 	{
  90. 		const size_t sz = sizeof(srcArr) / sizeof(srcArr[0]);
  91. 		for (size_t i = 0; i < sz; i++) {
  92. 			arr.push_back(srcArr[i]);
  93. 		}
  94. 	}
  95. 	const size_t arrsz = arr.size();
  96.  
  97. 	// 間接ソート用配列作成
  98. 	std::vector<int> indices(arrsz);
  99. 	for (size_t i = 0; i < arrsz; i++) {
  100. 		indices[i] = i;
  101. 	}
  102.  
  103. 	// 間接ソート
  104. 	auto cmpFunc = [=](const int a, const int b)->bool { return (arr[a] < arr[b]); };
  105. 	std::sort(indices.begin(), indices.end(), cmpFunc);
  106.  
  107. 	// 配列内容ダンプ
  108. 	printarr(arr, indices);
  109.  
  110. 	// lower_boundテスト
  111. 	bool bFailed = false;
  112. 	for (double val = 0.0; val < 10.0; val += 1.0) {
  113. 		// Lower bound取得
  114. 		const SomeBigObj x(val);
  115. 		const int lb = custom_lower_bound(arr, indices, x);
  116. 		// 表示
  117. 		printf("x=%.2f: lb=%d\n", x.get(), lb);
  118. 		// チェック
  119. 		if (!chk_lb(arr, indices, x, lb)) {
  120. 			bFailed = true;
  121. 		}
  122. 	}
  123. 	if (!bFailed) {
  124. 		printf("OK\n");
  125. 	}
  126. 	else {
  127. 		printf("NG\n");
  128. 	}
  129. }
  130.  
Success #stdin #stdout 0s 5424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
arr[] : ( 1.9 2.3 2.6 2.6 2.8 3.1 3.2 3.8 4.1 4.3 4.6 5.0 5.3 5.8 5.9 7.9 8.4 8.4 9.3 9.7 )
idx[] : (  19   8   3  11  17   0  14  13   1  12  10  16   4   5   2  15   9  18   7   6 )
x=0.00: lb=0
x=1.00: lb=0
x=2.00: lb=1
x=3.00: lb=5
x=4.00: lb=8
x=5.00: lb=11
x=6.00: lb=15
x=7.00: lb=15
x=8.00: lb=16
x=9.00: lb=18
OK
https://ideone.com/v9R75s
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!