STL 风格的算法：通过 OutputIterator 返回

Question

我正在尝试实现一种算法，如果它们满足 BinaryPredicate，则将元素合并到有序容器中。

template <typename ForwardIt, 
          typename OutputIt, 
          typename BinaryPredicate, 
          typename Merge>
void merge_adjacent(ForwardIt first, 
                    ForwardIt last, 
                    OutputIt out, 
                    BinaryPredicate pred, 
                    Merge merge)
{
    if(first != last)
        *out = *(first++);
    while(first != last)
    {
        if(pred(*first, *out))
            *out = merge(*out, *(first++));
        else
            *(++out) = *(first++);
    }
}

当我传递一个空容器以将结果放入（通过 OutputIterator）时，我得到一个分段错误 - 我也明白为什么，因为容器没有任何 space 保留...当我在通过 OutputIterator 之前保留足够的 space，容器保持为空...

我有点困惑，因为我正在关注 cppreference 上 std::transform 函数的示例实现：

template< class InputIt,
          class OutputIt,
          class UnaryOperation >
OutputIt transform( InputIt first1,
                    InputIt last1,
                    OutputIt d_first, 
                    UnaryOperation unary_op )
{
    while (first1 != last1) {
        *d_first++ = unary_op(*first1++);
    }
    return d_first;
}

我做错了什么？

我的 main.cpp 完整性：

#include "merge_adjacent.hpp"
#include <vector>
#include <iostream>
#include <stdexcept>

class Sale
{
public:
    Sale(int date, double amount)
     : date(date),
       amount(amount)
    {}
    Sale()
     : date(0),
       amount(0)
    {}
    int getDate() const
    {
        return date;
    }
    double getAmount() const
    {
        return amount;
    }
private:
    int date;
    double amount;
};

bool sameDate(Sale const& sale1, Sale const& sale2)
{
    return sale1.getDate() == sale2.getDate();
}

Sale mergeSales(Sale const& sale1, Sale const& sale2)
{
    if (sale1.getDate() != sale2.getDate()) throw ;
    
    return Sale(sale1.getDate(), sale1.getAmount() + sale2.getAmount());
}

int main()
{
    std::vector<Sale> sales = {Sale{1,2.9}, Sale(1,2.2),Sale(1,4.7),Sale(2,1.9),Sale(3,3.8),Sale(3,1.1),Sale(5,2.9),Sale(6,2.9),Sale(6,2.9)};
    std::vector<Sale> merged;
    merged.reserve(20);
    merge_adjacent(sales.begin(), sales.end(), merged.begin()/*std::back_inserter(merged)*/, sameDate, mergeSales);
    std::cout << "size of merged must be 5: " << merged.size() << std::endl;
    return 0;
}

Answer 1

您可能正在寻找这样的东西：

template <typename InputIt, 
          typename OutputIt, 
          typename BinaryPredicate, 
          typename Merge>
void merge_adjacent(InputIt first, 
                    InputIt last, 
                    OutputIt out, 
                    BinaryPredicate pred, 
                    Merge merge)
{
    if (first == last) return;
    auto accum = *first++;
    while (first != last) {
        auto cur = *first++;
        if (pred(cur, accum)) {
            accum = merge(accum, cur);
        } else {
            *out++ = accum;
            accum = cur;
        }
    }
    *out++ = accum;
}

Demo。没有经过非常彻底的测试，我只是确认它适用于您的示例。我认为我在 InputIterator 和 OutputIterator 的能力范围内，但我也没有测试过。

STL 风格的算法：通过 OutputIterator 返回

STL-style algorithm: returning via OutputIterator

c++

algorithm

stl

iterator