2015-12-10 11 views
0

Предположим, что мы получили std::vector<Obj> гдеФунктор найти минимальный объект, который удовлетворяет условию

struct Obj { 
    int size; 
    bool valid; 
} 

Как я могу написать функтор использовать с std::min_element() найти наименьший действительныйObj.

+0

Недействительный объект будет больше, чем все действительные объекты –

+0

Что произойдет, если ничего недействительно? –

+0

Неопределенный. Он никогда не будет вызываться без действительных объектов. – cbothner

ответ

0

Я думаю, что это работает, но я не мог испытывать достаточно хорошо ...

auto ObjComp = [](Obj &a, Obj &b) { 
    return !b.valid || (a.valid && a.size < b.size); 
}; 
+0

Вам не нужно проверять, действительны ли как a, так и b? –

+0

В некотором роде, я полагаю, вы правы. Эта итерация не проходит тест 'vector v = {{2, false}, {8, true}, {1, false}, {10, false}};' (он возвращает 2) – cbothner

+0

Для min вам нужно убедитесь, что недопустимые объекты всегда сравниваются выше. –

0

Вы могли бы сделать std::partition прежде, чем найти std::min_element.

auto validity = [](const Obj& x) { 
    return x.valid; 
}; 
auto by_size = [](const Obj& lhs, const Obj& rhs) { 
    return lhs.size < rhs.size; 
}; 
auto pivot = std::partition(v.begin(), v.end(), validity); 
auto valid_minimum = std::min_element(v.begin(), pivot, by_size); 
if (valid_minimum == pivot) { 
    std::cout << "No *active* minimum found!\n"; 
} 

Там также std::stable_partition если упорядочение в вопросах контейнера так или иначе.

+0

Это очень умное решение! Но он изменит контейнер. –

+0

Этот функтор будет называться O (n!) Раз, и вектор должен оставаться упорядоченным. Я хотел бы сделать это в одном линейном поиске. – cbothner

+0

Как изменится «активность» каждого объекта? Вы можете разбить его таким образом, что вам только нужно будет сделать это один раз, прежде чем вызовы начнутся. Кроме того, O (n!) Будет медленным, независимо от того, что делает ваш функтор, поэтому вы должны искать вместо этого _that_. –

Смежные вопросы