algorithm: partition_point と *_bound に実装例を追加

kariya-mitsuru · kariya-mitsuru · commit 0007299071c8 · 2015-02-05T01:42:14.000+09:00
また、*bound が partition_point と本質的に同一であることを記載。
diff --git a/reference/algorithm/lower_bound.md b/reference/algorithm/lower_bound.md
@@ -27,6 +27,11 @@ namespace std {
 最大で log2(`last - first`) + O(1) 回の比較を行う
 
 
+##備考
+本関数は、本質的に C++11 で追加された [`partition_point`](partition_point.md) と同一である。  
+具体的には、[`partition_point`](partition_point.md)`(first, last, [value](const T& e) { return e < value; })`、あるいは、[`partition_point`](partition_point.md)`(first, last, [value, comp](const T& e) { return comp(e, value); })` とすることで同一の結果が得られる。
+
+
 ##例
 ```cpp
 #include <iostream>
@@ -46,10 +51,62 @@ int main()
 }
 ```
 * lower_bound[color ff0000]
+* iostream[link ../iostream.md]
+* vector[link ../vector.md]
+* algorithm[link ../algorithm.md]
+* sort[link sort.md]
+* begin[link ../vector/begin.md]
+* end[link ../vector/end.md]
+* cout[link ../iostream/cout.md]
+* endl[link ../ostream/endl.md]
+
 
 ###出力
 ```
 3
 ```
 
 
+##実装例
+```cpp
+template<class ForwardIterator, class T>
+ForwardIterator
+lower_bound(ForwardIterator first, ForwardIterator last, const T& value)
+{
+    typedef typename std::iterator_traits<ForwardIterator>::difference_type diff;
+    for (diff len = std::distance(first, last); len != 0; ) {
+        diff half = len / 2;
+        ForwardIterator mid = first;
+        std::advance(mid, half);
+        if (*mid < value) {
+            len -= half + 1;
+            first = ++mid;
+        } else {
+            len = half;
+        }
+    }
+    return first;
+}
+
+template<class ForwardIterator, class T, class Compare>
+ForwardIterator
+lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
+{
+    typedef typename std::iterator_traits<ForwardIterator>::difference_type diff;
+    for (diff len = std::distance(first, last); len != 0; ) {
+        diff half = len / 2;
+        ForwardIterator mid = first;
+        std::advance(mid, half);
+        if (comp(*mid, value)) {
+            len -= half + 1;
+            first = ++mid;
+        } else {
+            len = half;
+        }
+    }
+    return first;
+}
+```
+* distance[link ../iterator/distance.md]
+* advance[link ../iterator/advance.md]
+* iterator_traits[link ../iterator/iterator_traits.md]
diff --git a/reference/algorithm/partition_point.md b/reference/algorithm/partition_point.md
@@ -30,9 +30,8 @@ O(log(`last - first`)) のオーダーで `pred` が適用される。
 #include <iostream>
 #include <vector>
 #include <algorithm>
-#include <string>
 
-void print(const std::string& name, const std::vector<int>& v)
+void print(const char* name, const std::vector<int>& v)
 {
   std::cout << name << " : ";
   std::for_each(v.begin(), v.end(), [](int x) {
@@ -57,6 +56,15 @@ int main()
 }
 ```
 * partition_point[color ff0000]
+* vector[link ../vector.md]
+* iostream[link ../iostream.md]
+* algorithm[link ../algorithm.md]
+* for_each[link for_each.md]
+* begin[link ../vector/begin.md]
+* end[link ../vector/end.md]
+* partition[link partition.md]
+* cout[link ../iostream/cout.md]
+* endl[link ../ostream/endl.md]
 
 
 ###出力
@@ -65,6 +73,29 @@ v : 4,2,3,1,5,
 3
 ```
 
+##実装例
+```cpp
+template<class ForwardIterator, class Predicate>
+ForwardIterator
+partition_point(ForwardIterator first, ForwardIterator last, Predicate pred)
+{
+    for (auto len = std::distance(first, last); len != 0; ) {
+        auto half = len / 2;
+        auto mid = std::next(first, half);
+        if (pred(*mid)) {
+            len -= half + 1;
+            first = std::next(mid);
+        } else {
+            len = half;
+        }
+    }
+    return first;
+}
+```
+* distance[link ../iterator/distance.md]
+* next[link ../iterator/next.md]
+
+
 ##バージョン
 ###言語
 - C++11
@@ -76,6 +107,3 @@ v : 4,2,3,1,5,
 - [GCC, C++0x mode](/implementation.md#gcc): 4.7.0
 - [ICC](/implementation.md#icc): ??
 - [Visual C++](/implementation.md#visual_cpp) ??
-
-
-
diff --git a/reference/algorithm/upper_bound.md b/reference/algorithm/upper_bound.md
@@ -27,6 +27,11 @@ namespace std {
 最大で log2(`last - first`) + O(1) 回の比較を行う
 
 
+##備考
+本関数は、本質的に C++11 で追加された [`partition_point`](partition_point.md) と同一である。  
+具体的には、[`partition_point`](partition_point.md)`(first, last, [value](const T& e) { return !bool(value < e); })`、あるいは、[`partition_point`](partition_point.md)`(first, last, [value, comp](const T& e) { return !bool(comp(value, e)); })` とすることで同一の結果が得られる。
+
+
 ##例
 ```cpp
 #include <iostream>
@@ -46,6 +51,14 @@ int main()
 }
 ```
 * upper_bound[color ff0000]
+* iostream[link ../iostream.md]
+* vector[link ../vector.md]
+* algorithm[link ../algorithm.md]
+* sort[link sort.md]
+* begin[link ../vector/begin.md]
+* end[link ../vector/end.md]
+* cout[link ../iostream/cout.md]
+* endl[link ../ostream/endl.md]
 
 
 ###出力
@@ -54,3 +67,46 @@ int main()
 ```
 
 
+##実装例
+```cpp
+template<class ForwardIterator, class T>
+ForwardIterator
+upper_bound(ForwardIterator first, ForwardIterator last, const T& value)
+{
+    typedef typename std::iterator_traits<ForwardIterator>::difference_type diff;
+    for (diff len = std::distance(first, last); len != 0; ) {
+        diff half = len / 2;
+        ForwardIterator mid = first;
+        std::advance(mid, half);
+        if (!bool(value < *mid)) {
+            len -= half + 1;
+            first = ++mid;
+        } else {
+            len = half;
+        }
+    }
+    return first;
+}
+
+template<class ForwardIterator, class T, class Compare>
+ForwardIterator
+upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
+{
+    typedef typename std::iterator_traits<ForwardIterator>::difference_type diff;
+    for (diff len = std::distance(first, last); len != 0; ) {
+        diff half = len / 2;
+        ForwardIterator mid = first;
+        std::advance(mid, half);
+        if (!bool(comp(value, *mid))) {
+            len -= half + 1;
+            first = ++mid;
+        } else {
+            len = half;
+        }
+    }
+    return first;
+}
+```
+* distance[link ../iterator/distance.md]
+* advance[link ../iterator/advance.md]
+* iterator_traits[link ../iterator/iterator_traits.md]
