Posted at

std::sortとstd::uniqueでstd::vectorの重複要素を削除する

More than 3 years have passed since last update.

std::setに変換せずにstd::vector内の重複要素を削除する方法を紹介する。

#include <iostream>   // std::cout, std::endl;

#include <algorithm> // std::unique
#include <vector> // std::vector

void printVec(std::vector<int> &vec) {
std::cout << "";
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
}

int main() {
std::vector<int> vec = {10,40,40,20,20,30,20,20,40};
std::unique(vec.begin(), vec.end());
printVec(vec); // 10 40 20 30 20 40 ? ? ?
}

std::uniqueは隣接する重複要素を削除するが、

vectorの長さなどには変更を加えないため、末尾にはゴミが残ることになる。

そこで、あらかじめstd::sortを使ってvectorの要素をソートしておき、std::uniqueを適用する。

#include <iostream>   // std::cout, std::endl;

#include <algorithm> // std::sort, std::unique
#include <vector> // std::vector

void printVec(std::vector<int> &vec) {
std::cout << "";
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
}

int main() {
std::vector<int> vec = {10,40,40,20,20,30,20,20,40};
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
printVec(vec); // 10 20 30 40
}

std::uniqueはゴミの手前のポインタを返すので、vector::eraseで後ろのゴミを削除する。

これで重複要素のないvectorが得られる。