Keeping vector of iterators of the data

Question

I have a function :

void get_good_items(const std::vector<T>& data,std::vector<XXX>& good_items);

This function should check all data and find items that satisfies a condition and return where they are in good_items.

what is best instead of std::vector<XXX>?

1. std::vector<size_t> that contains all good indices.
2. std::vector<T*> that contain a pointers to the items.
3. std::vector<std::vector<T>::iterator> that contains iterators to the items.
4. other ??

EDIT:

What will I do with the good_items? Many things... one of them is to delete them from the vector and save them in other place. maybe something else later

EDIT 2:

One of the most important for me is how will accessing the items in data will be fast depending on the struct of good_items?

EDIT 3:

I have just relized that my thought was wrong. Is not better to keep raw pointers(or smart) as items of the vector so I can keep the real values of the vector (which are pointers) and I do not afraid of heavy copy because they are just pointers?

Answer 1

The problem you are solving, from my understanding, is the intersection of two sets, and I would go for the solution from standard library: std::set_intersection

Answer 2

I would go with std::vector<size_t> or std::vector<T*> because they are easier to type. Otherwise, those three vectors are pretty much equivalent, they all identify positions of elements.

std::vector<size_t> can be made to use a smaller type for indexes if you know the limits.

If you expect that there are going to be many elements in this vector, you may like to consider using boost::dynamic_bitset instead to save memory and increase CPU cache utilization. A bit per element, bit position being the index into the original vector.

Answer 3

If you intend to remove the elements that statisfy the predicate, then erase-remove idiom is the simplest solution.

If you intend to copy such elements, then std::copy_if is the simplest solution.

If you intend to end up with two partitions of the container i.e. one container has the good ones and another the bad ones, then std::partition_copy is a good choice.

For generally allowing the iteration of such elements, an efficient solution is returning a range of such iterators that will check the predicate while iterating. I don't think there are such iterators in the standard library, so you'll need to implement them yourself. Luckily boost already has done that for you: http://www.boost.org/doc/libs/release/libs/iterator/doc/filter_iterator.html

Answer 4

If you remove items from the original vector, every one of the methods you listed will be a problem.

If you add items to the original vector, the second and third will be problematic. The first one won't be a problem if you use push_back to add items.

All of them will be fine if you don't modify the original vector.

Given that, I would recommend using std::vector<size_t>.