這篇文章將討論如何在 C++ 中從vector中刪除重複項。
1.使用 std::remove 功能
一個簡單的解決方案是迭代vector，對於每個元素，如果存在，我們從vector中刪除其所有重複項。我們可以為此編寫自己的例程或使用 std::remove 使我們的代碼優雅的算法。這種方法佔用恆定空間，但運行在 O(n2) 時間。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <vector> #include <algorithm> void remove(std::vector<int> &v) { auto end = v.end(); for (auto it = v.begin(); it != end; ++it) { end = std::remove(it + 1, end, *it); } v.erase(end, v.end()); } int main() { std::vector<int> v = { 5, 2, 1, 3, 4, 2, 2, 4, 5, 5, 6 }; remove(v); for (auto it = v.cbegin(); it != v.cend(); ++it) { std::cout << *it << ' '; } return 0; } |
輸出:
5 2 1 3 4
2.使用 std::unordered_set 功能
在這裡，想法是迭代vector並跟踪集合中的已訪問元素。如果之前沒有看到一個元素，我們將它再次插入到vector中從頭開始的下一個可用位置。
這種方法需要額外的存儲來存儲數據結構並運行在 O(n) 時間如果 std::unordered_set 用過 std::set.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void remove(std::vector<int> &v) { std::vector<int>::iterator itr = v.begin(); std::unordered_set<int> s; for (auto curr = v.begin(); curr != v.end(); ++curr) { if (s.insert(*curr).second) { *itr++ = *curr; } } v.erase(itr, v.end()); } |
這是另一個使用集合的解決方案。這個想法是在一個集合中插入所有vector元素並將集合的內容再次復制迴vector中。這是因為將元素插入集合中會刪除所有重複項，因為所有集合元素必須是不同的。請注意，這可能會改變vector中元素的原始順序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <vector> #include <unordered_set> int main() { std::vector<int> v = { 5, 2, 1, 3, 4, 2, 2, 4, 5, 5 }; std::unordered_set<int> s(v.begin(), v.end()); v.assign(s.begin(), s.end()); for (auto it = v.cbegin(); it != v.cend(); ++it) { std::cout << *it << ' '; } return 0; } |
輸出:
4 3 1 2 5
3.使用 std::remove_if 和 std::unordered_set 功能
另一個有效的解決方案是使用 std::remove_if 和 std::unordered_set.
最終邏輯與之前的解決方案相似，我們迭代vector並跟踪集合中的已訪問元素。如果之前沒有看到該元素，我們將它再次插入到vector中從頭開始的下一個可用位置。
請注意， std::remove_if 算法不知道底層容器。它實際上並沒有從容器中刪除元素，而是移動所有 安全的 元素到前面並返回一個指向結束位置的迭代器，因此可以使用一次調用將它們刪除 std::erase.這種技術通常被稱為 擦除刪除成語.
|
1 2 3 4 5 6 7 8 9 10 |
void remove(std::vector<int> &v) { std::unordered_set<int> s; auto end = std::remove_if(v.begin(), v.end(), [&s](int const &i) { return !s.insert(i).second; }); v.erase(end, v.end()); } |
4.使用 std::copy_if 和 std::unordered_set 功能
以下是我們如何通過使用 std::copy_if 算法。這將適用於 C++11 及更高版本。
|
1 2 3 4 5 6 7 8 9 10 |
void remove(std::vector<int> &v) { std::unordered_set<int> s; auto end = std::copy_if(v.begin(), v.end(), v.begin(), [&s](int const &i) { return s.insert(i).second; }); v.erase(end, v.end()); } |
輸出:
5 2 1 3 4
5.使用 std::remove_copy_if 和 std::unordered_set 功能
這 std::remove_copy_if 算法也將起作用，如下所示：
|
1 2 3 4 5 6 7 8 9 |
void remove(std::vector<int> &v) { std::unordered_set<int> s; auto end = std::remove_copy_if(v.begin(), v.end(), v.begin(), [&s](int const &i) { return !s.insert(i).second; }); v.erase(end, v.end()); } |
6.使用 std::sort 和 std::unique 功能
最後，我們還可以對vector進行排序並調用 std::unique，刪除重複的連續元素。這有效，但不保留元素的原始順序。這種方法佔用恆定空間，但運行在 O(n.log(n)) 時間。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> int main() { std::vector<int> v = { 5, 2, 1, 3, 4, 2, 2, 4, 5, 5 }; std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); for (auto it = v.cbegin(); it != v.cend(); ++it) { std::cout << *it << ' '; } return 0; } |
輸出:
1 2 3 4 5
這就是從 C++ 中的vector中刪除重複項的全部內容。