使用std :: nth_element時，第n個元素的副本是否總是連續的？

Question

vector<int> data = {3, 1, 5, 3, 3, 8, 7, 3, 2}; 
std::nth_element(data.begin(), data.begin() + median, data.end()); 

請問這個總是導致：

data = {less, less, 3, 3, 3, 3, larger, larger, larger} ? 

或者將一個其他可能的結果是：

data = {3, less, less, 3, 3, 3, larger, larger, larger} ? 

我已經多次試圖在我的機器至極導致第n值始終連續。但這不是證明;）。

什麼它是：

我想建立一個獨特的Kdtree，但我有我的矢量重複。目前我正在使用nth_element來查找中值。問題是選擇一個獨特的/可重構的中位數，而不必再次遍歷向量。如果中間值是連續的，我可以選擇一個獨特的中位數，沒有太多的遍歷。

Answer 1

號的documentation沒有規定這樣的行爲，並與實驗幾分鐘，這是很容易找到一個測試情況下受騙者是不連續的ideone：

#include <iostream> 
#include <algorithm> 

int main() { 
    int a[] = {2, 1, 2, 3, 4}; 
    std::nth_element(a, a+2, a+5); 
    std::cout << a[1]; 
    return 0; 
} 

輸出：

1 

如果這些騙局是連續的，那麼輸出將是2。

Answer 2

我剛剛嘗試了幾個不那麼簡單的例子，並在第三個得到非連續的輸出。

計劃

#include <vector> 
#include <iostream> 
#include <algorithm> 

int main() { 
    std::vector<int> a = {1, 3, 3, 2, 1, 3, 5, 5, 5, 5}; 
    std::nth_element(a.begin(), a.begin() + 5, a.end()); 
    for(auto v: a) std::cout << v << " "; 
    std::cout << std::endl; 
} 

與Linux下GCC 4.8.1，與std=c++11，讓我輸出

3 1 1 2 3 3 5 5 5 5 

，而第n個元素爲3

因此，沒有中，元素並不總是連續的。

我也認爲即使是一個簡單的方法，沒有考慮好測試用例，只是生成具有許多重複元素的長隨機數組並檢查它是否成立。我認爲它會在第一次或第二次嘗試時破裂。