std::list 和 std::map 的通用算法？

Question

我有一个感兴趣的类别（称之为 X）。
我有一个 std::list（称之为L）。
我有一个函数（称之为F）。

F(L) 根据检查列表中每个 X 的内部状态的算法返回 L 的子集（std::list）。

我正在向我的应用程序添加 std::map; （称之为 M），并且我需要定义 F(M) 以与 F(L) 相同的方式操作 - 也就是说，F(M) 必须返回 std::list；同样，通过检查图中每个 X 的内部状态来确定。

作为一个自称懒惰的程序员，我立即发现该算法在逻辑上是相同的，并且每种数据类型（std::list 和 std::map）都是可迭代模板。我不想两次维护相同的算法，但我不知道如何继续前进。

一种方法是从 F(M) 中获取 X*（即键值映射中的“值”），将它们放入 std::list中，然后进行处理传递给 F(std::list)，传递 return std::list;回来通过。我不明白这怎么会是唯一的方法。

我的问题：如何在一个地方维护核心算法，但保留迭代序​​列或一对关联容器的值的能力？

谢谢！

Answer 1

首先，除了两者的条件之外的所有内容都可以使用 std::remove_copy_if 来完成。尽管名称为 remove_copy_if，但它不会从原始集合中删除任何内容。我认为如果将其称为 filtered_copy 之类的名称，人们会更容易理解它。它将元素从一个集合复制到另一个集合。对于每个元素，它调用一个谓词，当且仅当该元素的谓词返回 false 时，才会复制该项目。

这让您只剩下一个责任：实现查看每个 X * 的测试函数，并说明是否应该将其排除在您正在制作的副本之外。由于您想以两种不同的方式应用一段逻辑，因此我将该逻辑封装在类的私有函数中。然后可以通过两种方式将其作为类的 operator() 的重载版本提供给外界：

class F { 
    bool do_test(X const *x) const { return x.internal_stuff; }
public:
    bool operator()(X const *x) const { return do_test(x); }

    bool operator()(std::pair<int, X const *> const &p) const { 
        return do_test(p.second);
    }
};

因为 operator()(X const *) 是一个纯粹的 thunk对于do_test()，您可能想摆脱它，但在我看来，这可能弊大于利。

无论如何，这都会将您的逻辑完全留在一个地方（F::do_test）。它还提供了一个简单、一致的语法，用于创建 list 或 std::map 的过滤副本：

std::list<X *> result;   
std::remove_copy_if(coll.begin(), coll.end(), std:back_inserter(result), F());

最后一点：std::list 可能是现有的最过度使用的集合。虽然它确实有其用途，但它们确实非常罕见。 std::vector 和 std::deque 通常非常更好。

Answer 2

编写一个接受两个前向迭代器作为参数（开始和结束）的函数，然后该函数仅测试迭代器的值，如果通过测试，则将其添加到列表中，递增迭代器，并测试它是否未达到end（如果是则中断。）

然后您只需调用该函数并向其传递集合的 begin() 和 end() 迭代器。

Answer 3

怎么样：

template<typename T>
struct func {
    std::list<T>& r;
    func(std::list<T>& r_) : r(r_) {}

    bool algorithm(const T& t) {
        return t<5; // obviously meant to be replaced :)
    }

    void operator()(const T& t) {
        if (algorithm(t)) r.push_back(t);
    }

    void operator()(const std::pair<int, T>& t) {
        if (algorithm(t.second)) r.push_back(t.second);
    }

};

template<typename T, typename ForwardIterator>
std::list<T> subset(ForwardIterator begin, ForwardIterator end) {
    std::list<T> r;
    std::for_each(begin, end, func<T>(r));
    return r;
}

Answer 4

一种解决方案是将算法从两个函数中移出，这些函数只需迭代其容器，然后调用 algo 函数来确定特定项是否属于返回列表。

Answer 5

您可能是对的，您建议的方法不是唯一的解决方案，但它可能是最容易正确编写和理解的。如果您正在编写生产代码，我肯定会从那里开始。仅在需要时分析代码并变得更高级。

在探索其他选项时，您可以看看 boost::bind。我收到这个答案 当我不久前尝试做类似的事情时。而且我认为 std::tr1::bind 基本上是相同的，所以如果你没有 Boost，你应该能够替换 TR1 版本。