partition

悠悠 2022-07-16 08:52 140阅读 0赞

出处：http://blog.csdn.net/justme0/article/details/24496767

STL 中的划分[算法][Link 1] partition 的函数原型如下

**\[cpp\]** [ view plain][view plain] [ copy][view plain] [ print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  template <class ForwardIterator, class Predicate>  
2.  ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred);

四点说明：

1、功能：将 \[first, last) 中所有满足 pred 的元素置于不满足 pred 的元素前面。

2、返回值：设返回的迭代器为 i，则对 \[first, i) 中的任意迭代器 j，pred(\*j) 为真，对 \[i, last) 中的任意迭代器 k，pred(\*k) 为假。

3、要求：ForwardIterator 必须满足 ValueSwappable。

4、复杂度：如果 ForwardIterator 符合 BidirectionalIterator 的要求，则最多进行 (last - first) / 2 次交换；否则最多 last - first 次交换。且执行 last - first 次的 pred 操作。

源码如下：

1.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
2.  created:    2014/04/25 15:37 
3.  filename:   partition.cpp 
4.  author:     Justme0 (http://blog.csdn.net/justme0) 
5.   
6.  purpose:    partition 
7.  \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
8.    
9.  \#include <cstdio>  
10. \#include <cstdlib>  
11.   
12. typedef int T;  
13.   
14. template <class ForwardIterator1, class ForwardIterator2>  
15. inline void iter\_swap(ForwardIterator1 a, ForwardIterator2 b) \{  
16.     T tmp = \*a;     // 源码中的 T 由迭代器的 traits 得来，这里简化了  
17.     \*a = \*b;  
18.     \*b = tmp;  
19. \}  
20.   
21. template <class Type>  
22. inline void swap(Type &a, Type &b) \{  
23.     Type tmp = a;  
24.     a = b;  
25.     b = tmp;  
26. \}  
27.   
28. /\* 
29. \*\* 设返回值为 mid，则\[first, mid)中迭代器指向的值满足 pred; 
30. \*\* \[mid, last)中迭代器指向的值不满足 pred 
31. \*\* 为双向迭代器设计的算法 
32. \*\* 迭代器用到了自减操作 
33. \*/  
34. template <class BidirectionalIterator, class Predicate>  
35. BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred) \{  
36.     while(true) \{  
37.         while(true) \{  
38.             if (first == last) \{  
39.                 return first;  
40.             \} else if (pred(\*first)) \{  
41.                 ++first;  
42.             \} else \{  
43.                 break;  
44.             \}  
45.         \}  
46.         --last;  
47.         while(true) \{  
48.             if (first == last) \{  
49.                 return first;  
50.             \} else if (!pred(\*last)) \{  
51.                 --last;  
52.             \} else \{  
53.                 break;  
54.             \}  
55.         \}  
56.         iter\_swap(first, last);  
57.         ++first;  
58.     \}  
59. \}  
60.   
61. /\* 
62. \*\* 为前向迭代器设计的算法 
63. \*\* 这里为了不与为双向迭代器设计的 partition 同名，加了后缀以区别 
64. \*\* 源码中由 traits 得到不同类型的迭代器标记形成重载 
65. \*/  
66. template <class ForwardIterator, class Predicate>  
67. ForwardIterator partition2(ForwardIterator first, ForwardIterator last, Predicate pred) \{  
68.     if (first == last) \{  
69.         return first;  
70.     \}  
71.   
72.     while (pred(\*first)) \{  
73.         if (++first == last) \{  
74.             return first;  
75.         \}  
76.     \}  
77.     ForwardIterator next = first;  
78.     while (++next != last) \{  
79.         if (pred(\*next)) \{  
80.             swap(\*first, \*next);  
81.             ++first;  
82.         \}  
83.     \}  
84.   
85.     return first;  
86. \}  
87.   
88. /\* 
89. \*\* 设返回值为 mid，则\[first, mid)中迭代器指向的值小于等于 pivot; 
90. \*\* \[mid, last)中迭代器指向的值大于等于 pivot 
91. \*\* 这是 STL 内置的算法，会用于 nth\_element, sort 中 
92. \*\* 笔者很困惑为什么不用 partition 
93. \*/  
94. template <class RandomAccessIterator, class Type>  
95. RandomAccessIterator unguarded\_partition(RandomAccessIterator first, RandomAccessIterator last, Type pivot) \{  
96.     while(true) \{  
97.         while (\*first < pivot) \{  
98.             ++first;  
99.         \}  
100.         --last;  
101.         while (pivot < \*last) \{  // 若 std::partition 的 pred 是 IsLess(pivot)，这里将是小于等于  
102.             --last;  
103.         \}  
104.         if (!(first < last)) \{   // 小于操作只适用于 random access iterator  
105.             return first;  
106.         \}  
107.         iter\_swap(first, last);  
108.         ++first;  
109.     \}  
110. \}  
111.   
112. template <class Type>  
113. struct IsLess \{  
114.     IsLess(const Type &pivot) : m\_pivot(pivot) \{\}  
115.   
116.     bool operator()(const Type &other) const \{  
117.         return other < m\_pivot;  
118.     \}  
119.   
120. private:  
121.     Type m\_pivot;  
122. \};  
123.   
124. void print(int \*array, int len) \{  
125.     for (int i = 0; i < len; ++i) \{  
126.         printf("%d ", array\[i\]);  
127.     \}  
128.     printf("\\n");  
129. \}  
130.   
131. int main(void) \{  
132.     \{  
133.         int arr\[\] = \{2, 30, 30, 17, 33, 40, 17, 23, 22, 12, 20\};  
134.         int size = sizeof arr / sizeof \*arr;  
135.   
136.         int \*mid = partition(arr, arr + size, IsLess<int>(22));  
137.         print(arr, size);                                       // 2 20 12 17 17 40 33 23 22 30 30  
138.         printf("partition return %d\\n", mid - arr);             // partition return 5  
139.     \}  
140.   
141.     \{  
142.         int arr\[\] = \{2, 30, 30, 17, 33, 40, 17, 23, 22, 12, 20\};  
143.         int size = sizeof arr / sizeof \*arr;  
144.   
145.         int \*mid = partition2(arr, arr + size, IsLess<int>(22));  
146.         print(arr, size);                                       // 2 17 17 12 20 40 30 23 22 30 33  
147.         printf("partition2 return %d\\n", mid - arr);            // partition2 return 5  
148.     \}  
149.   
150.     \{  
151.         int arr\[\] = \{2, 30, 30, 17, 33, 40, 17, 23, 22, 12, 20\};  
152.         int size = sizeof arr / sizeof \*arr;  
153.   
154.         int \*mid = unguarded\_partition(arr, arr + size, 22);  
155.         print(arr, size);                                       // 2 20 12 17 22 17 40 23 33 30 30  
156.         printf("unguarded\_partition return %d\\n", mid - arr);   // unguarded\_partition return 6  
157.     \}  
158.   
159.     system("PAUSE");  
160.     return 0;  
161. \}

如果大家对程序有任何疑问可以在下面回复，因为当中省略了很多 STL 的设计技巧以突出算法。

[Link 1]: http://lib.csdn.net/base/datastructure
[view plain]: http://blog.csdn.net/justme0/article/details/24496767#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/312555
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/312555/fork