1
\$\begingroup\$

I recently posted a question on Stack Overflow asking how I could go about implementing a context-based partition copy. I actually came up with my own solution, but I would like to see if it could be improved. For this question, I've generalised the solution that I posted on SO.

The goal is to implement a std::partition_copy-like algorithm that instead of just passing the current value to the predicate, also passes the range of values already evaluated to true. The idea here is that the predicate may depend on what we've already seen.

The main difficulty to this problem is that the user may pass either a normal iterator (e.g. using std::begin), or an inserter-iterator (e.g. using std::back_inserter). The solution needs to be able to handle both scenarios.

My solution requires a new inserter-iterator that allows access to the range methods of the container class (just the const ones):

#include <iterator>
#include <memory>

template <typename Container>
class ContextBackInsertIterator :
public std::iterator<std::output_iterator_tag, void, void, void, void>
{
protected:
    Container* container;

public:
    using container_type = Container;
    explicit ContextBackInsertIterator (Container& x) : container(std::addressof(x)) {}
    ContextBackInsertIterator<Container>& operator= (const typename Container::value_type& value)
    { container->push_back(value); return *this; }
    ContextBackInsertIterator<Container>& operator= (typename Container::value_type&& value)
    { container->push_back(std::move(value)); return *this; }
    ContextBackInsertIterator<Container>& operator* ()
    { return *this; }
    ContextBackInsertIterator<Container>& operator++ ()
    { return *this; }
    ContextBackInsertIterator<Container> operator++ (int)
    { return *this; }

    typename container_type::const_iterator begin() const { return container->begin(); }
    typename container_type::const_iterator end() const { return container->end(); }
    typename container_type::const_iterator cbegin() const { return container->cbegin(); }
    typename container_type::const_iterator cend() const { return container->cend(); }
};

Next I use TMP to statically determine whether to call the begin and end methods of the underlying container.

template <class Container>
inline
ContextBackInsertIterator<Container> ContextBackInserter(Container& x)
{
    return ContextBackInsertIterator<Container>(x);
}

template <typename T>
inline
typename std::enable_if<std::is_void<typename T::value_type>::value,
    typename T::container_type::const_iterator>::type
get_first(T first, T last)
{
    return last.begin();
}

template <typename T>
inline
typename std::enable_if<!std::is_void<typename T::value_type>::value, T>::type
get_first(T first, T last)
{
    return first;
}

template <typename T>
inline
typename std::enable_if<std::is_void<typename T::value_type>::value,
    typename T::container_type::const_iterator>::type
get_last(T first, T last)
{
    return (last.begin() != last.end()) ? std::prev(last.end()) : last.begin();
}

The trick is that because the ++ operator doesn't do anything for inserter-iterators, we can keep a copy of the passed in output iterator, increment it every time the predicate is true, and then call the above methods to get the actual range of the already true-values.

#include <algorithm>
#include <tuple>

template <typename InputIterator, typename OutputIterator1, typename OutputIterator2, 
        typename TernaryPredicate>
std::pair<OutputIterator1, OutputIterator2>
context_partition_copy(InputIterator first, InputIterator last,
                        OutputIterator1 result_true, OutputIterator2 result_false, 
                        TernaryPredicate pred)
{
    auto result_true_last = result_true;
    return std::partition_copy(first, last, result_true, result_false,
        [pred, result_true, &result_true_last] (const auto& x) {
        if (pred(x, get_first(result_true, result_true_last),
                get_last(result_true, result_true_last))) {
            ++result_true_last;
            return true;
        }
        return false;
    });
}

Here is a small example:

#include <iostream>
#include <vector>
#include <string>

using Iterator = std::vector<std::string>::const_iterator;

inline bool foo(const std::string& str, Iterator first_true, Iterator previous_true)
{
    return std::all_of(first_true, previous_true, [&str] (const auto& s) { return s != str; });
}

int main()
{
    std::vector<std::string> v {"hello", "world", "hello", "worlds"};

    std::vector<std::string> result_true {}, result_false {};

    context_partition_copy(v.begin(), v.end(), 
                            ContextBackInserter(result_true), 
                            ContextBackInserter(result_false), 
                            foo);

    std::cout << result_true.size() << std::endl;
    std::cout << result_false.size() << std::endl;

    return 0;
}

I'm looking for any general improvements, in particular anything that might improve performance.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.