Saving a vector of data iterators

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 elements that satisfy the condition and return where they are in good_items.

which is better than std::vector<XXX> ?

• std::vector<size_t> , which contains all the good indexes.
• std::vector<T*> , which contain pointers to elements.
• std::vector<std::vector<T>::iterator> , which contains iterators for the elements.
• other

EDIT:

What should I do with good_items ? Many things ... one of them is to remove them from the vector and save them elsewhere. maybe something else later

EDIT 2:

One of the most important for me is how to quickly access elements in data depending on the good_items structure?

EDIT 3:

I just changed that my thought was wrong. Isn't it better to keep the original pointers (or smart ones) as elements of a vector so that I can keep the real values ​​of the vector (which are pointers), and I'm not afraid of a heavy copy, because they are just pointers?

Answer 1

If you remove elements from the original vector, each of the methods you listed will be a problem.

If you add elements to the original vector, the second and third will be problematic. The first issue will not be an issue if you use push_back to add items.

They will all be fine unless you change the original vector.

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

Answer 2

If you intend to remove elements that match the predicate, then removing the idiom is the easiest solution.

If you are going to copy such elements, then std::copy_if is the easiest solution.

If you intend to end with two sections of the container, that is, one container has good and the other bad, then std::partition_copy is a good choice.

In order to generally allow the iteration of such elements, an effective solution returns a number of iterators that will check the predicate during the iteration. I don’t think there are such iterators in the standard library, so you will need to implement them yourself. Fortunately, I already did this for you: http://www.boost.org/doc/libs/release/libs/iterator/doc/filter_iterator.html

Answer 3

I would go with std::vector<size_t> or std::vector<T*> because they are easier to type. Otherwise, these three vectors are largely equivalent, they all determine the positions of the elements.

std::vector<size_t> you can use a smaller type for indexes if you know the limitations.

If you expect a lot of elements in this vector, you might need to use boost::dynamic_bitset instead to save memory and increase CPU cache usage. Bit per element, bit position - index into the source vector.

Answer 4

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