Question about iterating through array in c++

I have an array which is not necessarily full开发者_如何转开发.

It can be very sparse.

Is there a good way to iterate through this array without visiting all the possible indexes? (c++ array iterator?)

Or, even if I use array iterator, will it be nothing different from visiting every indexes and checking the value?

Yes, if you use an iterator, it's the same as visiting every index and checking the value, and there's no good way to skip logical holes. You could keep a list of good indices, but if you did that then why not just use a list to store the data in the first place?

If your data is very sparse, perhaps a better data structure would be a std::map, or even an std::unordered_map, depending on your application. These have decent lookup time while not wasting much space, like an array would have to.

Associate Array is what you are trying to build. I suggest you look for a library that does this for you!

If you need a key/value association that simulates an array, just use a std::map holding a std::pair. You can then retrieve your values with the index (key), and iterate quickly over only your set of actual values.

http://en.cppreference.com/w/cpp/container/map

std::map has syntax conveniences like operator[] that will act like an array.

Should you really need to stick with your array based solution boost::filter_iterator could be useful. Here is small example with integer arrays:

#include <algorithm>
#include <iostream>
#include <boost/iterator/filter_iterator.hpp>

struct is_not_null {
  bool operator()(int* t) {
    return t != NULL ? true : false;
  }
};

int main()
{
  int* a[] = {NULL, NULL, NULL, NULL, NULL, NULL };
  a[0] = new int[3];
  a[0][0] = 1; a[0][1] = 2; a[0][2] = 3;
  a[3] = new int[3];
  a[3][0] = 3; a[3][1] = 4; a[3][2] = 5;
  a[5] = new int[3];
  a[5][0] = 5; a[5][1] = 6; a[5][2] = 7;

  typedef int** base_iterator;
  typedef boost::filter_iterator<is_not_null, base_iterator>
    FilterIter;

  for(FilterIter it = boost::make_filter_iterator< is_not_null >(a, a + 6);
      it != boost::make_filter_iterator< is_not_null >(a + 6, a + 6);
      ++it) {
    std::cout << (*it)[0] << " " << (*it)[1] << " " << (*it)[2] << std::endl;
  }

  // nevermind the leaks
  return 0;
}