How to select a subset from stl :: vector or list?

Question

C ++ Guru:

There are quite useful C ++ stl algorithms such as search or search. However, it seems that they return only one of them.

What if I want to make a SQL "select" style for an STL container? let's say a vector (can be expanded to a list or map). something like

std::pair<vector::iterator, vector::iterator> select(std::vector::iterator begin, std::vector::iterator end, Comparor equal_to) 

the output should be a range similar to std :: pair, which is similar to the return value of methods in boost :: multi-index

Is there anything similar in stl? or are some solid librarians alike?

Answer 1

You have basically two approaches:

1) What you say in the comment above, write (iterators pointing to) the results to the iterator container. It will look something like this:

 template <typename ForwardIterator, typename OutputIterator, typename UnaryPredicate> void select_iterators(ForwardIterator first, ForwardIterator last, OutputIterator out, UnaryPredicate pred) { while (first != last) { if pred(*first) *out++ = first; ++first; } } 

Then you call it like this:

 vector<Foo> myfoos; vector<vector<Foo>::iterator> results; select_iterators(myfoos.begin(), myfoos.end(), std::back_inserter(results), some_comparator); 

In fact, you define select_iterators in terms of other algorithms using copy_if and boost::counting_iterator , but I don't think it's worth it when the direct implementation is so simple. It will look like this:

 template <typename ForwardIterator, typename OutputIterator, typename UnaryPredicate> void select_iterators(ForwardIterator first, ForwardIterator last, OutputIterator out, UnaryPredicate pred) { std::copy_if( boost::make_counting_iterator(first), boost::make_counting_iterator(last), out, [&](ForwardIterator it) { return pred(*it); } ); } 

2) Instead of testing all the values ​​in the front and writing the results somewhere, define an iterator that moves along the original range each time it increases until it finds the next match. Boost provides two ways to do this: boost::filter_iterator and boost::adaptors::filter . Therefore, you can write:

 auto results = boost::adaptors::filter(myfoos, some_comparator); 

Then, whatever you do with your results, you can iterate from results.begin() to results.end() , as if it were a container. This is not a container; it does not satisfy the entire interface of the container. It satisfies the interface defined by Boost, named Range, which is "can be repeated." This is actually just a filtered view of myfoos , so the Foo object is not copied or even moved.

Answer 2

If you can change your std :: partition vector, it will be a choice. Here is what you would call it:

 std::vector<int>::iterator p = std::partition(v.begin(), v.end(), you_predicate); 

The answer lies between v.begin() and p .

Answer 3

Perhaps you are looking for boost::range

A boost::range is actually a pair of iterators that limit the range of container elements. The library includes various algorithms that return a range from a range (for example, a range of equivalent values ​​in a container with a user-provided equivalence functor).

Answer 4

 template<typename ForwardIterator, typename OutputIterator, typename UnaryPredicate> void find_elements(ForwardIterator first, ForwardIterator last, OutputIterator out, UnaryPredicate pred) { while(first != last) { if(pred(*first)) *out++ = first; ++first; } } 

What you need to remember:

1.) You said you want your container to have an iterator , not a const_iterator . The type will be the same as the start and end ranges that you pass to the function. For example, the type will be const_iterator for const containers, it will also be const_iterator if you use vector::cbegin and vector::cend , and it won’t compile if you use different iterators like vector::begin and vector::cend .

2.) Vectors often lose their iterability, so be careful using these iterators. If you add to the vector, for example, each iterator returned by this function may be invalid. To prevent this, use either another container (such as a list) or use vector::reserve .

3.) The first iterator should be what ++ supports, and when dereferencing, it has the same type as InputIterator (for example, vector<int>::iterator ). It should also remain a valid iterator after increasing it, otherwise the function will be meaningless. The output iterator should go to a place with enough space to store all the iterators found for satsify pred . If you don't know in advance, you can use std::back_inserter from <iterator> with a container that has container::push_back , and it will grow as needed.

Here is a function test so you can understand how it works.

 int main() { vector<string> ss = {"hi", "yog", "engils", "pog"}; // Define a predicate auto isSizeThree = [](string const &s) { return s.size() == 3; }; // example one: Somehow I know how many satisfy the predicate. I just don't know where they are. vector<vector<string>::iterator> answer(2); find_elements(begin(ss), end(ss), begin(answer), isSizeThree); // Check answer cout << "Test 1" << endl; for(auto entry : answer) cout << *entry << endl; // Example two: I don't know how many there will be (more typical). If I use a continer with stuff in it - it will stack right on the back of it! find_elements(begin(ss), end(ss), back_inserter(answer), isSizeThree); // Check answer (has the answer from test 1 still in it) cout << "Test 2" << endl; for(auto entry : answer) cout << *entry << endl; // Example Three: Same as test 2 but clear the ansewr vector first. answer.clear(); find_elements(begin(ss), end(ss), back_inserter(answer), isSizeThree); // Check answer cout << "Test 3" << endl; for(auto entry : answer) cout << *entry << endl; }