0

Quick question (hopefully). I have a vector of strings and need to remove duplicates. Normally, I'd just use sort, erase and unique. However, I don't want to sort the data. My idea was to copy the vector to a set, then back to a vector. But every attempt just screws up the order. My last attempt involved copying the vector to a set, copying the set to another vector by using back_insert, and then reversing the vector. Doesn't work. I'd appreciate any ideas on how to solve this. Thanks. Here's the last attempt:

copy(v.begin(), v.end(), inserter(s, s.end()));
copy(s.begin(),s.end(), back_inserter(newV));
reverse(newV.begin(),newV.end());
4
Contributors
4
Replies
7
Views
8 Years
Discussion Span
Last Post by robotnixon
1

You can't copy it to a set and back again without breaking the order.
Sets store on a compiler defined manor but normally red-black trees.
Hence you will destroy the order.

The easiest way is to copy to another vector sort, unique
and then find the copies.

Another slightly more involved way is to copy to a map in which you have the positions in the vector as the second component. The remove the clashes. Depending on the vector type a hash map may work better.

Votes + Comments
thanks for the help
1

Here's a function that uses a set to remove duplicates from a vector without changing the order of elements:

void remove_dups (vector<string>& v) {
    set<string> s;
    pair<set<string>::iterator, bool> result;

    for (vector<string>::iterator i = v.begin(); i < v.end(); ++i) {

        result = s.insert(*i);

        if (!result.second) {
            v.erase(i);
            --i;  // adjust iterator
        }
    }
}

I'm not sure if the --i can blow up (although note that the first element will never be erased because it definitely will not be in the set).

Votes + Comments
thanks for the help
1

erase() invalidates the iterator passed, but it returns a valid iterator. Just change the code to:

i = v.erase(i);
Votes + Comments
thanks for the help
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.