I currently have a functor that finds the closest entity (by calculated distance) to the current entity. (Vector3 is just a 3D coordinate class)

template<typename T>
class MinDistanceBGE
{
private:
    Vector3 v; // The location of the 'asking' entity.
public:
    MinDistanceBGE(Vector3 vInput):v(vInput) {}
    bool operator()(T t1, T t2) const
    {
        return v.squaredDistance(t1->GetPosition()) < v.squaredDistance(t2->GetPosition());
    }
};

// And used like this:
it = min_element(enemyArmy->begin(), enemyArmy->end(), MinDistanceBGE<BaseGameEntity*>(a->GetPosition()));

This works beautifully... BUT... I would like to attach a condition:-
- Return the nearest T that is also T->NotRetreating() // returns a bool

It seems wrong to change the return statement to:

return (t1->NotRetreating()) && (v.squaredDistance(t1->GetPosition()) < v.squaredDistance(t2->GetPosition()));

As this isn't technically a sort any longer. But is this in fact the right way to do it?

Edited 5 Years Ago by fandango: n/a

I don't think this will always work. If you look at the synopsis of min_element, you will see that it starts by using the first element as the lowest one. If the first element has really small distance but does not satisfy the predicate, you will be in trouble. You could probably find the first element that satisfies the predicate and start the min_element from there. But, in this case, I think it is easier to just make your own version of min_element that finds the min_distance or something like that. It will also be less wasteful in terms of distance computations.

Use boost::filter_iterator, perhaps.
http://www.boost.org/doc/libs/1_46_0/libs/iterator/doc/filter_iterator.html

A trivial example:

#include <vector>
#include <algorithm>
#include <boost/iterator/filter_iterator.hpp>
#include <iostream>

int main()
{
    std::vector<int> seq = { 36, 4, 63, 21, 41, 64, 0, 35, 4, 17, 8, 33 } ;
    auto is_odd = [] ( int i ) { return i%2 != 0 ; } ;
    auto odd_begin = boost::make_filter_iterator( is_odd, seq.begin(), seq.end() ) ;
    auto odd_end = boost::make_filter_iterator( is_odd, seq.end(), seq.end() ) ;
    std::cout << "min_odd_element: " << *std::min_element( odd_begin, odd_end ) << '\n' ;
}
Comments
Always good to learn something new!

Thanks for the comments!

mike_2000_17: Yep, it's not really performing a proper comparison any more. I was hoping the implementatin for min_element might be written in my copy of "The Standard C++ Library", but sadly it's not so I'll have to hunt around the VisualC++ STL code to see how it's implemented. I guess failing the Predicate before the distance check is good, as you say, and optimise things a bit. Shouldn't be too hard to mock up a custom version of min_element, thanks!

vijayan121: That's interesting! One of the 3rd-party SDKs I'm using requires boost, but I've never looked into it myself (I'm still learning the STL). I assume the performance is still good? (in fact, I guess performance, skipping elements, is the reason it was implemented!) I'll check that out, thank you. (and I'll have to look into lambda as well! ;-) )

Edited 5 Years Ago by fandango: n/a

This question has already been answered. Start a new discussion instead.