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

Question

我有一类兴趣(称之为X).
我有一个std :: list <X*>(称之为L).
我有一个功能(称之为F).

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

我在我的应用程序中添加了一个std :: map <int,X*>(称之为M),我需要定义F(M)以与F(L)相同的方式运行 - 也就是说, F(M)也必须返回一个std :: list <X*>,通过检查地图中每个X的内部状态来确定.

作为一个自我描述的懒惰程序员,我立即看到该算法将[逻辑]相同,并且每个数据类型(std :: list和std :: map)都是可迭代的模板.我不想两次保持相同的算法,但我不确定如何继续前进.

一种方法是从F(M)中取出X*(即键值映射中的'值'),将它们放入std :: list <X*>中,并将处理过去到F(std :: list <X*>),传递返回std :: list <X*>; 回过头来.我看不出这是唯一的方法.

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

谢谢!

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 *)是纯粹的笨蛋do_test(),你可能想要摆脱它,但IMO可能弊大于利.

无论如何,这将你的逻辑完全放在一个地方(F::do_test).它还提供了一种简单,一致的语法,用于创建a list<X *>或a 的过滤副本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是非常频繁越好.