CODEWITHSUNDEEP
c++loopsstdvector
vinash85
vinash85

Reputation: 431

Find indices not in indices vector

How to find indices not in indices in an array? For eg. if indices vector is (2, 8, 6, 9). Then the result should be (1,3,4,5,7). R have a function (not) %in% for doing this. A naive way would be to create an array of flags. But creation of flag and iteration over the non-indices will be two different loops. Is there a way to do this in a single loop?

Upvotes: 1

Views: 136

Answers (3)

user2249683
user2249683

Reputation:

Without sorting:

#include <iostream>
#include <vector>

struct NaturalNumber {
    unsigned value;
    bool valid;

    NaturalNumber(unsigned value = 0)
    :   value(value), valid(true)
    {}
};

typedef std::vector<NaturalNumber> NaturalNumbers;

NaturalNumbers natural_number_range(unsigned n) {
    NaturalNumbers result;
    result.resize(n);
    for(unsigned i = 0; i < n; ++i) result[i] = i;
    return result;
}

int main(int argc, char* argv[]) {
    NaturalNumbers n0 = { 2, 8, 6, 9 };
    NaturalNumbers n1 = natural_number_range(10);
    for(NaturalNumbers::const_iterator pos = n0.begin(); pos != n0.end(); ++pos) {
        n1[pos->value].valid = false;
    }
    for(NaturalNumbers::const_iterator pos = n1.begin(); pos != n1.end(); ++pos) {
        if(pos->valid)
            std::cout << pos->value << std::endl;
    }
    return 0;
}

It just delegates the sorting to a flag in expense of storing invalid data. There is no single loop, also!

Upvotes: 0

ChronoTrigger
ChronoTrigger

Reputation: 8617

Sort first and check from first to last numbers in your "universe" later. Check this function. According to your example, the input would be A = [2, 8, 6, 9], first = 1, last = 9. You get the solution in out. Note that the function modifies A to sort it.

void getComplement(std::vector<unsigned int> &A, 
  size_t first, size_t last, std::vector<unsigned int> &out)
{
  out.clear();
  if(last < first) return;

  const size_t T = last - first + 1;
  if((int)T - (int)A.size() > 0) out.reserve(T - A.size());

  if(A.empty())
  {
    for(size_t k = first; k <= last; ++k) out.push_back(k);
  }
  else
  {
    std::sort(A.begin(), A.end());

    std::vector<unsigned int>::const_iterator ait = A.begin();

    // elements before the first element of A
    for(size_t k = first; k < *ait; ++k) out.push_back(k);

    // middle elements
    std::vector<unsigned int>::const_iterator bit = ait + 1;
    for(; bit != A.end() ; ++ait, ++bit)
    {
      for(size_t k = *ait + 1; k < *bit; ++k) out.push_back(k);
    }

    // elements after the last element of A
    for(size_t k = A.back() + 1; k <= last; ++k) out.push_back(k);
  }

}

Upvotes: 0

Sarien
Sarien

Reputation: 6992

This should work:

int j = 0;
for(int i = 0;; ++i) {
  if(oldvec[j] == i) {
    j++;
    if(j >= oldvec.length())
      break;
  } else {
    newvec.push_back[i];
  }
}

New answer:

  std::set<int> result;
  int max = -1;
  for(unsigned int i=0; i<oldvec.size(); ++i)
  {
    int cur = oldvec[i];
    while(max < cur) {
      max++;
      result.insert(max);
    }
    result.erase(cur);
  }

How about that? :) Wait, does the result have to be a std::vector?

Upvotes: 1

Related Questions