CODEWITHSUNDEEP
c++algorithmvectorstlfilter
Pierre
Pierre

Reputation: 6172

How to filter vector elements relative to other ones?

I a vector of vectors, each representing a a set (in the mathematical sense). For example:

{{1, 3}, {4, 9, 14}, {1, 3}, {1, 4, 8, 9, 10, 14, 16}, {1, 3, 9}, {4, 9, 17, 22}}

I want to make the most efficient C++ possible function capable of filtering (in place, if possible) the vector in order to remove every item that contains another.

For example, here:

The resulting vector would then be:

{{1, 3}, {4, 9, 14}, {4, 9, 17, 22}}

As I'm beginning with C++ don't really have any clue of how to do this efficiently. I found, on other answers here, the erase / remove idiom, which doesn't seem to be very appropriate here, except by passing erase a closure as predicate. Which doesn't seem really idiomatic in C++.

Please note that keeping the original ordering doesn't matter, nor does the ordering of values inside each set.

Upvotes: 3

Views: 632

Answers (1)

Pierre
Pierre

Reputation: 6172

Given what I learnt so far, thanks to your very helpful comments, the solution I came up with is:

struct std::vector<size_t> colset;

bool less_colsets(const colset& a, const colset& b) {
  return a.size() < b.size();
}

void sort_colsets(std::list<colset>& l) {
  l.sort(less_colsets);
}

void strip_subsets(std::list<colset>& l) {
  sort_colsets(l);
  for (std::list<colset>::iterator i = l.begin(); i != l.end(); ++i) {
    std::list<colset>::iterator j = next(i, 1);
    while (j != l.end()) {
      if (includes((*j).begin(), (*j).end(), (*i).begin(), (*i).end())) {
        j = l.erase(j);
      }
      else {
        ++j;
      }
    }
  }
}

Note that I replaced the outermost std::vector by std::list which is much more optimised for element removal anywhere.

This seems to work as expected, though I'd need some more tests to prove this. The next step will be to use a more efficient comparison function than includes, which would take into account the fact that each vector is lexically ordered (which the program guarantees). I'll try this tomorrow.

Edit: Looks like std::includes already takes care of this fact. YAY!

Thanks everybody.

Upvotes: 2

Related Questions