Seaching through STL containers

Recently I discovered that I often search through STL containers(mostly vector) using the following syntax(pseudo code):

for(iterator it=begin(); it!=end(); ++it){
  if( it->key()==key ){
    // do something.
  }
}

I know there is std::find but it uses operator== so if I have one for my class I would have to create a temporary object to compare to or overload the operator for the given type. The first approach is useless in most cases, and the second one is more or less also useless since i can have 2 getters returning the same type and the operator== would work only for one of them.

On the other hand, there is std::find_if function which takes a predicate as a last argument and returns the object that satisfies predicate(obj)==true. This allows for a per vector/object customization of the search. The downside is that I would have to write a predicate for each vector type. I can have multiple predicates per class for different search conditions.

I found the solution to be quite simple. I implemented a predicate class for use with std::find_if that takes the getter address and the desired value and uses this getter for comparison. This way I have a little piece of code that allows me to search through every container using specific criterion(the given getter).

Here is the example usage:

// Sample structure
struct TT{
  TT(int _key, const std::string &_value) :key(_key), value(_value){}
  int id() const                          { return key;             }

  int           key;
  std::string   value;
};
typedef std::vector<TT>  Vector;

// And the searching(for an element with id()==10)
Vector::iterator it=std::find_if( v.begin(),
                                  v.end(),
                                  nstd::make_cmp(&TT::id, 10) );
if( it!=v.end() ) std::cout << "found: " << it->value << std::endl;
else              std::cout << "not found\n";

and here’s the predicate along with make_cmp() function for easier usage(without the copy constructor and assignment operator for clarity):

namespace nstd{
  template<class Owner, class KeyType, class RetType>
  struct CmpGetter{
      typedef RetType (Owner::*Getter)() const;

      CmpGetter(Getter getter, KeyType key)
      :m_getter(getter), m_key(key){
      }
      bool operator()(const Owner &obj){
        if( (obj.*m_getter)() == m_key )
          return true;
        return
          false;
      }

    private:
      Getter    m_getter;
      KeyType   m_key;
  };

  template<class Owner, class KeyType, class RetType>
  CmpGetter<Owner, KeyType, RetType>
  make_cmp( RetType (Owner::*getter)() const, KeyType key ){
    return CmpGetter<Owner, KeyType, RetType>(getter, key);
  }
}

This approach can be easily converted so it uses member value instead of accessor, but in my code 99% of the time all of the members are private/protected and access to them is wrapped in accessors so I don’t need the code to compare members.

Advertisement

Tags: C++, containers, stl, templates