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

我有一个兴趣班（称之为X）。
我有一个标准::清单< X * >（称之为L）。
我有一个函数（称之为F）。根据检查列表中每个X的内部状态的算法，F（L）返回L的一个子集（std :: list < X * >）。我要添加到我的应用程序std :: map < int，X * >（称之为M），我需要定义F（M）以与F（L）相同的方式运行 - 也就是说，F（M）必须返回std :: list < X * >，通过检查映射中每个X的内部状态来确定。std :: list和std :: map的常用算法？

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

一个办法是采取X *的从F（M）（也就是‘从键 - 值映射值’），扔进一个std ::名单< X * >，和将处理转到F（std :: list < X * >），传递返回std ::列表< X * >;通过。我看不出这是唯一的方法。

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

谢谢！

来源

2009-12-14 Chris Tonkinson

首先，所有，但条件都可以用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()，你可能想摆脱它，但IMO那会可能会造成更多的伤害而非好处

无论如何，这会将您的逻辑完全留在一个地方（F::do_test）。它还提供了一个简单，一致的语法创建的或者是list<X *>过滤副本或std::map<int, X *>：

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

最后一点：std::list可能是最过度使用集合存在。尽管它有其用途，但它们确实非常罕见。 std::vector和std::deque都是非常好经常更好。

来源

2009-12-14 04:46:47

我喜欢这个，因为函子真的很简洁。和Mic和Anon一样的想法。但我觉得最优雅。谢谢！ – 2009-12-14 07:07:43

@Chris - 我同意，我不知道remove_copy_if的行为就像我自己（奇怪的命名），一定会将它添加到我自己的阿森纳:)。 – Mic 2009-12-14 18:57:46

一种解决方案是将算法从两个函数中移出，并且这些函数只是对它们的容器进行迭代，然后调用算法函数来确定某个特定项是否属于返回列表中。

来源

2009-12-14 03:25:52

编写一个接受两个前向迭代器的函数，因为它的参数（开始和结束），然后该函数只是测试迭代器的值，如果它通过了测试，将它添加到列表中，并增加迭代器并测试它没有到达最后（如果是，就中断）

然后您只需调用该函数并将集合的begin（）和end（）迭代器传递给它。

来源

2009-12-14 03:37:56

但std :: list的前向迭代器直接取消引用X *，而std :: map迭代器取消引用std :: pair – 2009-12-14 03:47:49

@Chris True，但有些方法只是遍历键或地图的值而不是成对的值。见http://stackoverflow.com/questions/1443793/iterate-keys-in-ac-map和http://stackoverflow.com/questions/259240/iterator-adapter-to-iterate-just-the-values-in -a-map – csj 2009-12-14 05:19:40

你可能是正确的，你建议的方法不是唯一的解决方案，但它可能是最容易正确编写和理解。如果你正在写产品代码，我肯定会从那里开始。对代码进行简档，只有在需要时才能获得更多发现。

在探索其他选项时，您可以查看boost::bind。当我尝试做类似的事情时，我收到了this answer。我认为std::tr1::bind基本上是一样的，所以如果你没有升压，你应该可以替代TR1版本。

来源

2009-12-14 03:46:00

如何像：

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; 
}

来源

2009-12-14 03:51:04 Mic

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

回答

相关问题