漸進複雜度std :: remove_if

Question

我正在研究數據結構的擦除方法，該數據結構具有硬編碼的最大元素數N，它依賴於std::array來避免堆內存。雖然std::array包含N個元素只有一些數目M，都是「相關的」元素，其中M小於或等於N.作爲一個例子，如果N是10和陣列看起來像這樣：

std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 }; 

...如果M是7，則只有前7個元素是「相關」，而其他元素被認爲是垃圾（結尾{ -1, -1, -9 }是垃圾）。我在這裏使用int來舉例，但真正的程序存儲實現operator==的對象。下面是一個工作的例子，刪除所有-1和更新瑪：

#include <algorithm> 
#include <array> 
#include <iostream> 

constexpr unsigned N = 10; 
unsigned   M = 7; 
std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 }; 

int main() { 
     for (unsigned i = 0; i < M; ++i) 
       std::cout << elements[i] << ' '; 
     std::cout << '\n'; 

     auto newEnd = std::remove_if(
       std::begin(elements), std::begin(elements) + M, 
       [](const auto& element) { 
         return -1 == element; 
       } 
     ); 

     unsigned numDeleted = M - std::distance(std::begin(elements), newEnd); 
     M -= numDeleted; 
     std::cout << "Num deleted: " << numDeleted << '\n'; 

     for (unsigned i = 0; i < M; ++i) 
       std::cout << elements[i] << ' '; 
     std::cout << '\n'; 

     return 0; 
} 

我的問題是什麼是std::remove_if的漸近複雜性？我會想象在std::remove_if和std::distance之間，總體上是O（2M）或O（M），其中std::remove_if是更昂貴的操作。但是我不知道如果std::remove_if是O（N * M）由於每缺失移元件

編輯：爲了清楚起見，我明白，這應該被應用謂詞M次但如果N位移是想知道被每次謂詞是真

Answer 1

編輯

這個答案，現在回想起來，解決了超過一個更復雜的問題是什麼被問 - 在線性時間內如何實現「推回到終止」功能？關於被問到的具體問題 - 有關remove_if - @ millenimumbug的答案更好地解決了這個問題。

---

我能明白你爲什麼會覺得複雜性將是Θ（M n）爲，因爲每個米刪除的項目可能需要轉移Θ（N）距離。

它實際上是有可能做到這一點的時候Θ（N）和附加O（1）空間（只需幾個迭代器）。

考慮下圖，顯示算法的可能實現的迭代。

紅色的物品是認可項目的一組連續的被刪除到結束，在這一點上（你只需要兩個點來記錄這一點）。綠色項目是正在考慮的項目（另一個指針）。

如果綠色項目將被刪除，紅色組通過包含它而變得更大。下圖顯示了紅色組的擴展。在下一次迭代中，綠色項目將成爲它的右側。

如果不是，則所有紅色組都需要移過它。有些想法可以說服你，這可以在紅組中以線性時間完成（即使迭代器保證只是前向迭代器）。

爲什麼複雜度是線性的？因爲你可以想象這相當於綠色元素相對於左側組左移。其基本原理與攤銷分析類似。

下圖顯示了第二種情況。在下一次迭代中，綠色元素（正在考慮）將再次位於紅色組的右側。

Answer 2

施加通過cppreference：

複雜：謂詞 究竟std::distance(first, last)應用程序。

上有刪除的元素無移位操作，因爲他們可以有通話結束後未指定值std::remove_if