使用unordered_set为vector去重丢失原序，求简洁STL解决方案

Hey there! I totally get your frustration—unordered_set is great for stripping out duplicates, but since it’s built on a hash table, it doesn’t care about the original insertion order at all. That’s exactly why your "z" ended up out of place instead of staying at the end like you wanted.

Let’s ditch those three manual loops and use STL algorithms to solve this more cleanly. Here are two concise, efficient approaches:

1. Create a New Deduplicated Vector (Preserving Order) #

We can pair std::copy_if with an unordered_set to track elements we’ve already seen. Only the first occurrence of each element gets copied to the new vector, keeping your original order intact:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
    vector<string> terminals = { "e", "d", "a", "b", "c", "a", "a", "a", "a", "b","b", "b", "b", "c", "z" };
    
    // Print original vector
    cout << "Original: ";
    for (const auto& s : terminals) cout << s << " ";
    cout << endl;

    vector<string> deduplicated;
    unordered_set<string> seen;

    // Filter duplicates while preserving order
    copy_if(terminals.begin(), terminals.end(), back_inserter(deduplicated),
        [&seen](const string& s) {
            // insert() returns a pair: the second value is true only if the element was new
            return seen.insert(s).second;
        });

    // Print the result
    cout << "Deduplicated (order preserved): ";
    for (const auto& s : deduplicated) cout << s << " ";
    cout << endl; // Output: e d a b c z

    return 0;
}

2. In-Place Deduplication (Memory Efficient) #

If you don’t need to keep the original vector, you can modify it directly using the erase-remove_if idiom. This avoids creating a separate vector and saves memory:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
    vector<string> terminals = { "e", "d", "a", "b", "c", "a", "a", "a", "a", "b","b", "b", "b", "c", "z" };
    
    // Print original vector
    cout << "Original: ";
    for (const auto& s : terminals) cout << s << " ";
    cout << endl;

    unordered_set<string> seen;
    // Erase duplicates in place
    terminals.erase(
        remove_if(terminals.begin(), terminals.end(),
            [&seen](const string& s) {
                // Return true if we've already seen this element (mark for removal)
                return !seen.insert(s).second;
            }),
        terminals.end());

    // Print the modified vector
    cout << "Deduplicated (in-place, order preserved): ";
    for (const auto& s : terminals) cout << s << " ";
    cout << endl; // Output: e d a b c z

    return 0;
}

How It Works #

The magic here is unordered_set::insert(), which returns a pair. The second value in this pair is a boolean: true if the element was successfully inserted (meaning it hadn’t been seen before), false otherwise. We use this boolean to decide whether to keep the element (in the copy_if case) or mark it for removal (in the erase-remove_if case).

Both approaches are way more concise than manual loops, and they leverage STL’s built-in algorithms to keep your code clean and readable.

内容的提问来源于stack exchange，提问作者Jared