C++: Deduplicate names in first-seen order
A report may need each name once, in the order it first appeared. An unordered set can track membership, while a vector retains the report order. Iterating the set itself would lose that ordering contract.
Prepare a scratch directory
Tested on Linux with GCC 14.2.0 in C++20 mode. You need Bash, a C++20 compiler and standard library, a text editor, and the mktemp, rm, and rmdir utilities. Keep the same terminal open. Stop if setup fails, before saving the source:
start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1Run the example
Save as cpp-deduplicate-preserve-first-order.cpp:
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
std::vector<std::string> unique_names(const std::vector<std::string>& input) {
std::unordered_set<std::string> seen;
std::vector<std::string> result;
for (const auto& name : input) {
if (seen.insert(name).second) result.push_back(name);
}
return result;
}
int main() {
const std::vector<std::string> input{"beta", "alpha", "beta", "gamma", "alpha"};
const auto result = unique_names(input);
assert((result == std::vector<std::string>{"beta", "alpha", "gamma"}));
assert(unique_names({}).empty());
assert(unique_names({"A", "a"}).size() == 2);
assert(input.size() == 5);
for (const auto& name : result) std::cout << name << '\n';
std::cout << "input count: " << input.size() << '\n';
}Compile and run:
g++ -std=c++20 -Wall -Wextra -Werror -pedantic cpp-deduplicate-preserve-first-order.cpp -o cpp-deduplicate-preserve-first-order &&
./cpp-deduplicate-preserve-first-orderObserved output:
beta
alpha
gamma
input count: 5How it works
The boolean in the insertion result is true only when the set adds a new key. Appending on that result combines the membership test and insertion into one operation. Each first occurrence is appended as the input loop reaches it, so hash bucket order cannot affect the output.
Both containers own their strings. The input remains unchanged, and the returned vector stays valid after the input is destroyed. Avoid replacing these owned strings with views unless their storage lifetime is guaranteed.
Limits and choices
Default string equality distinguishes uppercase from lowercase and compares the stored character sequence; it does not normalize Unicode. Define any normalization policy before deduplication. Hash-table operations have average constant-time container lookup, but hashing strings still examines their characters and collision-heavy cases can be slower. The set and output both consume memory for unique names. This approach is appropriate when preserving first occurrence matters more than minimizing storage.
The C++ working draft specifies the library operation used here. The example uses the C++20 interface tested above; newer draft additions are outside its scope.
Clean up
rm -- cpp-deduplicate-preserve-first-order.cpp cpp-deduplicate-preserve-first-order
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directoryIf the directory is not empty, inspect the remaining files before removing anything else.
Acknowledgements
This post was created with assistance from AI.