STL list - как найти элемент списка по его полям объекта

Question

У меня есть список:

list<Unit *> UnitCollection;

содержит объекты юнитов, которые имеют такой метод доступа, как:

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

Как мне выполнить поиск в моем списке UnitCollection по uCode и вернуть соответствующий элемент (желательно и итератор).

В псевдокоде это будет выглядеть примерно так:

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(), с другой стороны, гораздо мощнее и решает проблему здесь очень хорошо. Вы должны ожидать этого в следующем стандарте, который должен быть здесь сразу после прибытия Мессии.

Но если у вас нет поддержки

Если у вас еще нет поддержки в вашем проекте, тогда вы действительно должны установить его. Если стандартная библиотека - жена C ++, то Boost - молодой любитель C ++. Они оба должны быть там, они прекрасно ладят.

Сказав это, вы можете извлечь функцию в отдельный объект функции, как уже упоминал Питер:

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

Ваш предикат может выглядеть примерно так:

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 3

Вы можете взглянуть на 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 );

Или, по крайней мере, я думаю, что это был бы способ сделать это.

Answer 4

Посмотрите на find_if.

Если вы можете использовать повышение, вы можете использовать его с 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")))