代码之家 › 专栏 › 技术社区 › Dominic Bou-Samra

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

stl list c++

Dominic Bou-Samra · 技术社区 · 15 年前

我有一个清单:

list<Unit *> UnitCollection;

包含单元对象,其具有如下访问器:

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()方法,但我不确定是否可以将布尔方法而不是搜索项参数传入,如果这样做有意义的话。

4 回复 | 直到 15 年前

Jacob 15 年前

你可以看看 find_if 正如jpalecek建议的,然后使用 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 );

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

wilhelmtell 15 年前

不重要的评论

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

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(:) 另一方面,它的功能更强大,并且很好地解决了这个问题。你应该期待它在下一个标准中出现,在弥赛亚到来之后马上出现。

但如果你没有动力

如果您的项目中还没有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是什么样子的,但是如果它们很大,那么你可以通过维护这些字符串的散列来加快速度,这样在你的搜索谓词中,你只比较散列。散列可以是规则整数:比较整数非常快。

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

Peter 15 年前

您的谓词可能看起来像:

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函数最好采用字符串by(const)引用,以避免不必要的复制。

你说你想返回一个项目的索引;对于链接列表来说,这通常是不明智的,因为你不能按索引返回项目。如果你想通过索引来处理它们,也许 std::vector 对你更有用。

Community CDub 8 年前

看一看 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"))

或者,如果你想要索引(如果是否定的,请看 here ):

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