Find array element by member value - what are "for" loop/std::map/Compare/for_each alternatives?

Question

Example routine:

const Armature* SceneFile::findArmature(const Str& name){
    for (int i = 0; i < (int)armatures.size(); i++)
        if (name == armatures[i].name)
            return &armatures[i];
    return 0;
}

Routine's purpose is (obviously) to find a value within an array of elements, based on element's member variable, where comparing member variable with external "key" is search criteria.

One way to do it is to iterate through array in loop. Another is to use some kind of "map" class (std::map, some kind of vector sorted values + binarySearch, etc, etc). It is also possible to make a class for std::find or for std::for_each and use it to "wrap" the iteration loop.

What are other ways to do that?

I'm looking for alternative ways/techniques to extract the required element. Ideally - I'm looking for a language construct, or a template "combo", or a programming pattern I don't know of that would collapse entire loop or entire function into one statement. Preferably using standard C++/STL features (no C++0x, until it becomes a new standard) AND without having to write additional helper classes (i.e. if helper classes exist, they should be generated from existing templates).

I.e. something like std::find where comparison is based on class member variable, and a variable is extracted using standard template function, or if variable (the one compared against "key"("name")) in example can be selected as parameter.

The purpose of the question is to discover/find language feature/programming technique I don't know yet. I suspect that there may be an applicable construct/tempalte/function/technique similar to for_each, and knowing this technique may be useful. Which is the main reason for asking.

Ideas?

Answer 1

Sure looks like a case for std::find_if -- as the predicate, you could use e.g. a suitable bind1st. I'm reluctant to say more as this smacks of homework a lot...;-).

Answer 2

You would probably need to use STL map. It gives you possibility to get the element using keys. Your key would be the name of armature.

http://www.cplusplus.com/reference/stl/map/

EDIT: :D

one liner B-)

const Armature* SceneFile::findArmature(const Str& name){for (int i = 0; i < (int)armatures.size(); i++) if(name == armatures[i].name) return &armatures[i]; return 0;}

Answer 3

Holy shiz, you're using _stricmp? FAIL. Also, you didn't actually tell us the type of the vectors or any of the variables involved, so this is just guesswork.

const Armature* SceneFile::findArmature(const std::string& lols) {
    for(auto it = armatures.begin(); it != armatures.end(); it++) {
        if (boost::iequals(lols, (*it).name))
            return &(*it);
    return NULL;
}

Ultimately, if you need this, you should put the armatures or pointers to them in a std::map. A vector is the wrong container if you're searching into it, they're best for when the collection is what's important rather than any finding behaviour.

Edited to use a std::string reference.

Answer 4

Why 5 lines? Clean doesn't have a number attached to it. In fact, clean code might take more lines in the utility classes, which can then be reused over and over. Don't restrict yourself unnecessarily.

class by_name
{
public:
    by_name(const std::string& pName) :
    mName(pName)
    {}

    template <typename T>
    bool operator()(const T& pX)
    {
        return pX.name == pName;
    }

private:
    std::string mName;
};

Then:

const Armature* SceneFile::findArmature(const char* name)
{
    // whatever the iterator type name is
    auto iter = std::find_if(armatures.begin(), armatures.end(), by_name(name));
    return iter == armatures.end() ? 0 : &(*iter);
}

---

Within restriction:

class by_name { public: by_name(const std::string& pName) : mName(pName) {} template <typename T> bool operator()(const T& pX) { return pX.name == pName; } private: std::string mName; };

Then:

const Armature* SceneFile::findArmature(const char* name)
{
    // whatever the iterator type name is
    auto iter = std::find_if(armatures.begin(), armatures.end(), by_name(name));
    return iter == armatures.end() ? 0 : &(*iter);
}

:)

---

C++0x has ranged-based for-loops, which I think would make the most elegant solution:

const Armature* SceneFile::findArmature(const std::string& pName) const
{
    for (auto a : armatures)
    {
        if (a.name = pName) return &a;
    }

    return 0;
}

Answer 5

If you have access to Boost or another tr1 implementation, you can use bind to do this:

const Armature * SceneFile::findArmature(const char * name) {
  find_if(armatures.begin(), armatures.end(),
    bind(_stricmp, name, bind(&string::c_str, bind(&Armature::name, _1))) == 0);
}

Caveat: I suspect many would admit that this is shorter, but claim it fails on the more elegant/simpler criteria.