斷言向量由值x

Question

代碼段分配

std::vector<int> v{ 3, 8, 2, 5, 1, 4, 7, 6}; 
Partition(v.begin(), v.end(), v.begin()); 

應該重新排列矢量v，使得第一n個元素是小於或等於3，並且在下列因素大於3。將所得載體應該是這樣的：

1,2,3,5,8,4,7,6

如何測試，如果分區中產生的斷言語句的正確結果口頭斷言以下：

斷言矢量的第一部分僅包含元素 是小於或等於x 並且該秒部分僅包含元素 是大於x

更大

？

Answer 1

感謝委員會中的真棒人士，您對矢量進行分區的要求可以表示爲「矢量分區？」，它很好地映射到標準的std::is_partitioned算法。生活不美麗嗎？

assert(std::is_partitioned(v.begin(), v.end(), [](int e) { return e <= 3; })); 

Answer 2

您要檢查的斷言可能會被重新表述爲「嚴格大於3的最右邊的元素位於小於或等於3的最左邊的元素之前」。

因此，您可以找到這兩個元素的位置（請參見std::find_if documentation，它可能用於普通和反向迭代器），然後在assert語句中比較它們。檢查將在線性時間內工作，並需要不斷的記憶。

Answer 3

斷言的矢量的第一n個元素是小於值x

1,2,3,5,8,4,7,6 

你的結果的初始分區似乎進行排序小。如果得到保證，則最簡單的測試是：

v[n - 1] <= x 

如果排序不能保證，則可以使用std::all_of單獨測試每個所述第一n元件。

---

斷言矢量的第一部分只包含小於或等於x的元素和該秒部分僅包含大於X

此描述了的元件分割序列。這可以用std::is_partitioned進行測試。