STL列表-如何通过对象字段查找列表元素

Question

我有一个列表：

list<Unit *> UnitCollection;

包含 Unit 对象，它有一个访问器，例如：

bool Unit::isUnit(string uCode)
{
    if(this->unitCode == uCode)
        return true;
    else
        return false;
}

如何通过 uCode 搜索我的 UnitCollection 列表并返回相应的元素（最好是和迭代器）。

在伪代码中，它看起来像这样：

for every item in my UnitCollection:
  if the unit.isUnit(someUnitIpass)
    do something
  else
    next unit

我已经查看了 find() 方法，但我不确定您是否可以传递布尔方法而不是搜索到的项目参数（如果这有意义）。

Answer 1

首先，

您可以将访问器函数更改为更简单的形式。

return unitCode == uCode;

现在我们要为您提供的内容

您最好查找元素的位置，而不是其索引。从其索引获取元素是一个 O(n) 操作，而从其位置获取元素是一个 O(1) 操作。因此，借助 STL 以及 boost::bind() 的一点帮助：

#include <algorithm>
#include <boost/bind.hpp>

// ...
std::string uCode("uCode to search for");
std::list<Unit*>::iterator pos = std::find_if(unitCollection.begin(),
                                              unitCollection.end(),
                                              boost::bind(&Unit::isUnit,
                                                          _1, uCode));

STL 确实有 std::mem_fun()，它与 std 一起::bind2nd() 会给出相同的结果。问题是 mem_fun() 仅适用于不带参数的成员函数。另一方面，boost::bind() 功能更强大，并且确实很好地解决了这里的问题。你应该在下一个标准中期待它，它应该在弥赛亚到来后立即出现。

但如果你没有 Boost

如果你的项目中还没有 Boost 那么你真的真的应该安装它。如果说标准库是C++的妻子，那么Boost就是C++的年轻情人。他们应该都在那里，他们相处得很好。

话虽如此，您可以将函数提取到一个独立的函数对象中，正如 Peter 已经提到的：

struct has_uCode {
    has_uCode(cont std::string& uc) : uc(uc) { }
    bool operator()(Unit* u) const { return u->isUnit(uc); }
private:
    std::string uc;
};

然后，您可以像这样调用 std::find_if()：

std::list<Unit*>::iterator pos = std::find_if(unitCollection.begin(),
                                              unitCollection.end(),
                                              has_uCode("this and that"));

还有一点性能考虑

还有一件事：我不知道 uCode 是什么样子，但如果它们很大，那么您可以通过维护这些字符串的哈希值来加快速度，以便在搜索谓词中只比较哈希值。哈希值可能是常规整数：比较整数非常快。

还有一件事：如果您经常运行此搜索过程，您可能还会考虑更改容器类型，因为这确实是一个昂贵的过程：按照列表长度的顺序。

Answer 2

您可以按照 jpalecek 的建议查看 find_if ，然后使用 distance 查找 find_if 返回的迭代器与 UnitCollection.begin() 之间的距离，该距离应该是列表中元素的索引。

至于谓词，您可以编写一个像这样的函数对象：

struct predicate
{
    predicate( const std::string &uCode ) : uCode_(uCode) {}

    bool operator() ( Unit *u )
    {
        return u->isUnit( uCode_ )
    }
private:
    std::string uCode_;
};

然后像这样使用它：

predicate pred("uCode");
std::list<Unit*>::iterator i;
i = std::find_if( UnitCollection.begin(), UnitCollection.end(), pred );

或者至少我认为这是一种方法。

Answer 3

您的谓词可能类似于：

struct unit_predicate {
    unit_predicate(const string& s): str(s) {}
    bool operator()(const Unit* unit) const {
        return unit->isUnit(str);
    }
    const string& str;
};

UnitCollection::const_iterator unit = std::find_if(units.begin(), units.end(), unit_predicate("Some Unit"));

其他一些注释：

您的 isUnit 函数最好通过 (const) 引用获取字符串，以避免不必要的复制。

你说你想返回一个项目的索引；这对于链接列表通常是不明智的，因为您无法通过索引获取项目。如果您想通过索引处理它们，也许 std::vector 对您更有用。

Answer 4

看看find_if。

如果您可以使用 boost，则可以将其与 boost::lambda 一起使用。

namespace bl=boost::lambda;
std::find_if(...begin... , ...end... , bl::bind(&Unit::isUnit, *bl::_1, "code"))

或者你可以编写自己的函子。

struct isUnitor // : public std::unary_function<Unit*, bool> -- this is only needed for the negation below
{
  string arg;
  isUnitor(const string& s) : arg(s) {}
  bool operator()(Unit* u) const { return u->isUnit(arg); }
};

std::find_if(...begin... , ...end... , isUnitor("code"))

或者，如果您想要索引（对于否定，请查看 此处):

std::count_if(...begin... , ...end... , not1(isUnitor("code")))