Using C++ adapters and library function objects in container arrangement

Question

So, I was wondering if it is possible to combine C++ adapters with library function objects in order to do some manipulation on containers defined in C++ standard library.

For example, if I were to define a vector with some elements

vector<int> vi={1,2,3,4,5,6,7,8,9,0};

and I want to count only the values contained in that vector that are greater than, for example, 4, I am interested in possibility of using an adapter:

priority_queue<int, vector<int>, greater<int> > pq(vi.begin(),vi.end());

However, it seems to me that previous line will just make a entire copy of vi into pq, while taking into account that the elements order is ascending. Is there a way to condition an adapter via greater<int> to take into account only the specific values from the input vector?

This looks to me like a solution in search of a problem. Despite the highly sophisticated optimizations implemented by modern C++ compilers, I somehow doubt that any modern compiler will be able to perform meaningful optimizations of this approach, and will likely produce a pile of code that does a lot of work with very little to show for it. If you want to count values greater than 4, then write a single `for` loop. — Sam Varshavchik, Jun 04 '18 at 10:41

einpoklum · Accepted Answer · 2018-06-04T10:52:30.110

Eric Niebler's ranges library has many facilities for adapted ranges, particularly filter ranges. However, the standard library containers themselves do not admit such adapters. If you're ok with iterator pairs rather than ranges, and want to avoid requiring Concept support, the Boost library has a lot of iterator utility code: The Boost Iterator Library, including boost::filter_iterator.

Having said that, you can easily initialize a new container from an old container using filtering, using standard library facilities such as std::copy_if:

template< class InputIt, class OutputIt, class UnaryPredicate >
constexpr OutputIt copy_if( InputIt first, InputIt last,
                            OutputIt d_first,
                            UnaryPredicate pred );

In your case, it would be something like:

std::priority_queue<int, std::vector<int>, std::greater<int> > pq;
auto greater_than_four = [](int x) { return x > 4; };
std::copy_if(vi.begin(), vi.end(), push_insert_iterator(pq), greater_than_four);

where push_insert_iterator is defined here. (Code is untested.)

Thanks for the comment. However, even though this provides a solution for a problem of filtering values, I am interested only in particular approach I specified in my question - can we use standard library adapters, such as `priority_queue` in combination with library function objects in order to manipulate container elements. — Akhaim, Jun 04 '18 at 10:54
Sorry, I just now noticed that you also edited your comment with extra info. — Akhaim, Jun 04 '18 at 10:55

Maxim Egorushkin · Answer 2 · 2018-06-04T11:31:02.337

You can filter the elements of your input container using boost::filter_iterator:

#include <boost/iterator/filter_iterator.hpp>
#include <queue>
#include <vector>

int main() {
    using namespace std;
    vector<int> vi={1,2,3,4,5,6,7,8,9,0};
    auto filter = [](int a) { return a > 5; };
    priority_queue<int, vector<int>, greater<int>> pq(
        boost::make_filter_iterator(filter, vi.begin(), vi.end()),
        boost::make_filter_iterator(filter, vi.end(), vi.end())
        );
}

Alternatively, use boost::range library with less verbose syntax:

#include <boost/range/algorithm/copy.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <queue>
#include <vector>

int main() {
    using namespace std;
    vector<int> vi={1,2,3,4,5,6,7,8,9,0};
    auto filter = [](int a) { return a > 4; };
    using C = priority_queue<int, vector<int>, greater<int>>;
    C pq = boost::copy_range<C>(vi | boost::adaptors::filtered(filter));
}

Under the hood boost::copy_range<Sequence>(...) does return Sequence(begin, end) to construct the return value from the two range iterators. Calling this constructor is more efficient then solutions involving push/insert iterators.

Using C++ adapters and library function objects in container arrangement

2 Answers2