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.
std::map will have decent look up time. Does that mean O(1) like array? or O(n) like queue?
O(lg n) actually - between an array and queue, but closer to an array. For instance, if you had an array of 1 million elements, it would always take 1 unit of time to access any one. If you had a list or queue of 1 million elements, it could take 1 million units of time to access any one. But if you had a map of 1 million elements, the most it could take would be 19 units of time to access any one. So yeah, it's pretty bloody fast for not being an array. Note that unordered_map, because it's an hash table, will be faster usually (O(1) unless you have collisions).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;
}
