erasing duplicate element on even index in STL vector

Question

I know how to erase duplicate element(s) on a vector.

data.erase(std::unique(data.begin(), data.end()), data.end());

How do I erase duplicate elements on index 0, 2, 4, 6, 8, ...?

Example:

 index : 0 1 2 3 4 5 6 7 8 9
 data  : a b a d b f a h b k
         ^   ^   ^   ^   ^
         ^   ^   ^   ^
                 ^--same-^
         ^   ^       ^
         ^   ^       ^ 
         ^-----same--^  
after erasing
data  :  a b   d b f   h   k

after concatenatiom
data :   a b d b f h

Do you want to erase all duplicates (as your example seems to suggest), or just the **adjacent** ones (which is what `std::unique` does)? — Branko Dimitrijevic, Nov 13 '11 at 18:52
either your example is wrong, or your approach using `erase` and `std::unique` doesn't solve this problem. Please clarify this. — moooeeeep, Nov 13 '11 at 18:53

Benjamin Lindley · Answer 1 · 2011-11-13T18:59:35.197

There's no library function for this. What you're asking to do isn't even analogous to using std::unique as you did in your example, since that only removes adjacent duplicates. You'll have to do most of the work here yourself.

Create a set. Loop through the vector, skipping the odd indexes. As you loop, check if that element is in the set. If it is, mark that index for removal, otherwise, add the element to the set. Remove all marked indexes from the vector. You can't use std::remove or std::remove_if, since those work on element values, not indexes. You'll have to use a plain old for loop.

Although, if you designate a certain value as illegal, then instead of keeping track of indexes, you can actually change the element to that illegal value. Then you can use std::remove.

score 2 · Answer 2 · answered Nov 13 '11 at 19:10

This is not a particularly elegant code, but it should work as long as default hashing and comparison is sufficient, and should be reasonably efficient:

template <typename T>
void RemoveEvenDuplicates(std::vector<T>& v) {

    std::unordered_set<T> s;
    std::vector<T>::size_type i = 0;

    auto last = std::remove_if(
        v.begin(),
        v.end(),
        [&s, &i] (const T& element) -> bool {
            if (i++ % 2 == 0) {
                auto pair = s.insert(element);
                return !pair.second;
            }
            return false;
        }
    );

    v.erase(last, v.end());

}

void main() {

    std::vector<std::string> v;
    v.push_back("a");
    v.push_back("b");
    v.push_back("a");
    v.push_back("d");
    v.push_back("b");
    v.push_back("f");
    v.push_back("a");
    v.push_back("h");
    v.push_back("b");
    v.push_back("k");

    RemoveEvenDuplicates(v);

}

After the call to RemoveEvenDuplicates, the vector becomes:

[7]("a","b","d","b","f","h","k")

score 0 · Answer 3 · edited May 23 '17 at 10:34

You could take (one of) the suggestion(s) given in this very good post by Fred Nurk to a very similar question. You will need an additional ++x; to touch only the even (or odd) indexed elements.

Example:

set<string> found;
for (list<string>::iterator x = the_list.begin(); x != the_list.end();) {
  if (!found.insert(*x).second) {
    x = the_list.erase(x);
  }
  else {
    ++x;
  }
  ++x; // <-- one increment added to skip the odd-indexed elements
}

erasing duplicate element on even index in STL vector

3 Answers3