跳至內容

Erase–remove慣用法

維基百科,自由的百科全書

Erase–remove慣用法'C++程式語言常用的技術,用於在C++標準模板庫容器中刪除元素。[1][2][3]

動機

[編輯]

一個常見的編程任務是從集合(collection)中刪除等於某個值或滿足某個標準的所有元素。C++語言可以通過手寫循環完成這個任務。但更好的辦法是使用C++標準模板庫中的算法來實現。[1][2][3]

erase用於從一個集合中刪除一個元素,但是對於基於數組的容器,如vector,存儲在被刪除元素後的所有元素都需要向前移動以避免集合中有一個空位(gap)。在同一容器中多次調用產生了大量移動元素的開銷。

algorithm庫提供了removeremove_if算法。由於這些算法運行在兩個前向迭代器確定的元素範圍上,它們沒有底層容器或集合的具體知識。[1][4]這些算法並不從容器刪除元素,而是把不「符合」刪除標準的元素搬移到容器的前部,並保持這些元素的相對次序。該算法一次通過數據範圍即可實現該目標。

由於沒有元素被刪除,因此容器尺寸保持不變。容器尾部的元素都是需要被刪除的,但其狀態未指定(unspecified state)。remove返回一個迭代器指向尾部這些需要用erase刪除的元素的第一個。

同樣的事情(刪除多個元素),用容器的方法erase會導致多次遍歷這個容器,每一次遍歷時,在被刪除元素之後的所有元素都必須向前移動,其時間消耗遠大於單次通過。

局限

[編輯]

erase–remove慣用法不能用於返回const_iterator (例如:set[5]的容器。

std::removestd::remove_if不能保持被刪除的元素(不像std::partition, std::stable_partition)。因此,erase–remove只能用於容器的元素是全值語義不會招致資源泄露。[6]

例子

[編輯]
// Use g++ -std=c++11 or clang++ -std=c++11 to compile.

#include <algorithm>  // remove and remove_if
#include <iostream>
#include <vector>  // the general-purpose vector container

bool IsOdd(int i) { return i & 1; }

void Print(const std::vector<int>& vec) {
  for (const auto& i : vec) {
    std::cout << i << ' ';
  }
  std::cout << std::endl;
}

int main() {
  // Initializes a vector that holds numbers from 0-9.
  std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  Print(v);

  // Removes all elements with the value 5.
  v.erase(std::remove(v.begin(), v.end(), 5), v.end());
  Print(v);

  // Removes all odd numbers.
  v.erase(std::remove_if(v.begin(), v.end(), IsOdd), v.end());
  Print(v);
}

/*
Output:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 6 7 8 9
0 2 4 6 8
*/

參考文獻

[編輯]
  1. ^ 1.0 1.1 1.2 Meyers, Scott. Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley. 2001. 
  2. ^ 2.0 2.1 Sutter, Herb; Alexandrescu, Andrei. C++ Coding Standards: 101 Rules, Guidelines, and Best Practices. Addison-Wesley. 2004. 
  3. ^ 3.0 3.1 C/C++ Users Journal, October 2001. STL Algorithms vs. Hand-Written Loops頁面存檔備份,存於互聯網檔案館
  4. ^ Josuttis, Nicolai. C++ Standard Library – A Tutorial and Reference. Addison-Wesley. 1999. 
  5. ^ Erase–remove idiom with std::set. [14 April 2013]. 
  6. ^ Meyers, Scott. Effective STL : 50 specific ways to improve your use of the standard template library有限度免費查閱,超限則需付費訂閱. Boston: Addison-Wesley. 2001: 143–145. ISBN 0201749629. OCLC 46713127.