二维vector去重

### C++ 二维 `vector` 去重方法 在处理二维 `vector` 的去重时，可以采用多种方式来实现。以下是几种常见的方法： #### 方法一：利用自定义比较器与 `std::set` 通过将二维 `vector` 中的每一行转换为某种可哈希的数据结构（如字符串或元组），并将其存储到 `std::set` 或 `std::unordered_set` 中以去除重复项。 ```cpp #include <iostream> #include <vector> #include <set> using namespace std; int main() { vector<vector<int>> vec = {{1, 2}, {3, 4}, {1, 2}, {5, 6}}; set<vector<int>> uniqueSet; for (const auto& row : vec) { uniqueSet.insert(row); } vector<vector<int>> result(uniqueSet.begin(), uniqueSet.end()); for (const auto& row : result) { for (int val : row) { cout << val << " "; } cout << endl; } return 0; } ``` 这种方法的核心在于使用 `std::set` 来自动过滤掉重复的向量[^1]。 --- #### 方法二：基于排序和 `std::unique` 如果允许修改原始数据，则可以通过先对二维 `vector` 进行排序，再调用 `std::unique` 函数完成去重。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; bool cmp(const vector<int>& a, const vector<int>& b) { return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); } int main() { vector<vector<int>> vec = {{1, 2}, {3, 4}, {1, 2}, {5, 6}}; sort(vec.begin(), vec.end(), cmp); auto last = unique(vec.begin(), vec.end(), [](const vector<int>& a, const vector<int>& b) -> bool { return a == b; }); vec.erase(last, vec.end()); for (const auto& row : vec) { for (int val : row) { cout << val << " "; } cout << endl; } return 0; } ``` 此方法的关键是对整个二维 `vector` 排序后再应用 `std::unique` 函数，从而移除相邻的重复项[^3]。 --- #### 方法三：手动遍历检测重复 如果不希望依赖 STL 容器或者算法库中的功能，也可以通过嵌套循环的方式手动检查每一对子向量是否相等，并保留唯一的子向量。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { vector<vector<int>> vec = {{1, 2}, {3, 4}, {1, 2}, {5, 6}}; vector<vector<int>> result; for (size_t i = 0; i < vec.size(); ++i) { bool isUnique = true; for (size_t j = 0; j < result.size(); ++j) { if (vec[i] == result[j]) { isUnique = false; break; } } if (isUnique) { result.push_back(vec[i]); } } for (const auto& row : result) { for (int val : row) { cout << val << " "; } cout << endl; } return 0; } ``` 这种方式虽然简单易懂，但在大数据集上效率较低，因为它的时间复杂度接近 O(n²)[^2]。 --- ### 性能对比分析 | **方法** | **优点** | **缺点** | |-----------------------------|------------------------------------------------------------------------------------------|--------------------------------------------| | 使用 `std::set` | 自动化程度高，易于理解 | 需要额外空间保存临时集合 | | 排序加 `std::unique` | 不需要额外分配大量内存 | 修改原容器顺序 | | 手动遍历 | 对于小型数据集可能更直观 | 时间复杂度过高，在大规模输入下表现较差 | 以上三种方案各有优劣，具体选择取决于实际应用场景以及性能需求。 ---