Searching a container

[Peteris Krumins]

Hello!

I would like to ask how to search for a container element which
matches some criteria.
Here is what I mean.

Suppose I have a structure:
struct my_struct {
my_struct(const std::string &lname, const std::string &lvalue,
const std::string &lothername, const bool lsomething,
const bool lanotherone, const unsigned lunsignedValue)
: name(lname), value(lvalue), othername(lothername),
something(lsomething), anotherone(lanotherone),
unsignedValue(lunsignedValue) {}

my_struct() {}

std::string name;
std::string value;
std::string othername;
bool something;
bool anotherone;
unsigned unsignedValue;
};

And I have a vector (or other container) which holds elements of
type my_struct:
std::vector<my_struct>

I want to search for an element in the container which for example
has name "hello" and an unsignedValue less than 83333.
Or search for an element
which has name "world", value "world", any othername, true for
something
and false for anotherone and any value of unsignedValue. etc.

I have come up with two solutions, both are basically the same, they
use std::find_if using a specially for this purpose written predicate.
They differ only by method how search parameters are passed to the
predicate.

Solution 1:
The constructor of class my_struct_searcher can take all parameters to
be
searched. The ones which do not matter are left default initialized.
To search my_struct::unsignedValue a unary predicate can be specified
to my_struct_searcher. If none is specified the default
"DefaultFunctor"
is used which just returns true.

struct DefaultFunctor : public std::unary_function<unsigned, bool>
{
bool operator()(const unsigned c) const { return true; }
};

template <typename CmpFunctor = DefaultFunctor>
class my_struct_searcher {
private:
CmpFunctor CompareFunction;
boost::logic::tribool b_something;
boost::logic::tribool b_anotherone;
protected:
my_struct local;
public:
my_struct_searcher(
const std::string &name = std::string(),
const std::string &value = std::string(),
const std::string &othername = std::string(),
const boost::logic::tribool &something =
boost::logic::indeterminate,
const boost::logic::tribool &anotherone =
boost::logic::indeterminate,
const CmpFunctor &f = DefaultFunctor())
: local(name, value, othername, true, true, 0),
b_something(something), b_anotherone(anotherone),
CompareFunction(f) {}

bool operator()(const my_struct &ms) {
bool found = true;
found = found && (local.name.empty() ||
(ms.name.find(local.name) != std::string::npos));
if (found == false) return false;
found = found && (local.value.empty() ||
(ms.value.find(local.value) != std::string::npos));
if (found == false) return false;
found = found && (local.othername.empty() ||
(ms.othername.find(local.othername) != std::string::npos));

return found && baseCompare(ms);
}
bool baseCompare(const my_struct &ms) {
bool found = true;
found = found && (boost::logic::indeterminate(b_something) ||
(ms.something == b_something));
if (found == false) return false;
found = found && (boost::logic::indeterminate(b_anotherone) ||
(ms.anotherone == b_anotherone));
if (found == false) return false;

return found && CompareFunction(ms.unsignedValue);
}
};

Example of usage:
// find an element in a container which has part of
// name "hell" and unsignedValue < 280
iter = std::find_if(container.begin(), container.end(),
my_struct_searcher<std::binder2nd<std::less<unsigned> > >("hell",
"", "", boost::logic::indeterminate,
boost::logic::indeterminate, bind2nd(std::less<unsigned>(),
280)));


What I dont like in this solution is that to search using only a
single
criteria which happens to be at the end of constructor (can be
specified
as one of the last parameters of ctor) all the other parameters must
be specified as default. Like: my_struct_searcher<>("", "", "", true),
to search just for my_struct::something being true.


Solution 2:
Use the same mechanism as in solution 1, just make specifying search
criteria easier by "chaining up" search parameters by having a
structure (struct nice_params) with member functions which set the
search parameter and return reference to *this.

template <typename CmpFunctor = DefaultFunctor>
class other_searcher {
public:
struct nice_params {
my_struct local;
boost::logic::tribool b_something;
boost::logic::tribool b_anotherone;
CmpFunctor CompareFunction;

nice_params(const CmpFunctor &f = DefaultFunctor()) :
CompareFunction(f),
b_something(boost::logic::indeterminate),
b_anotherone(boost::logic::indeterminate) {}
nice_params &name(const std::string &name) { local.name = name;
return *this; }
nice_params &value(const std::string &value) { local.value =
value; return *this; }
nice_params &othername(const std::string &othername) {
local.othername = othername; return *this; }
nice_params &something(const boost::logic::tribool &something)
{ b_something = something; return *this; }
nice_params &anotherone(const boost::logic::tribool
&anotherone) { b_anotherone = anotherone; return *this; }
};
protected:
nice_params params;
public:
other_searcher(const nice_params &p) : params(p) {}

bool operator()(const my_struct &ms) {
bool found = true;
found = found && (params.local.name.empty() ||
(ms.name.find(params.local.name) != std::string::npos));
if (found == false) return false;
found = found && (params.local.value.empty() ||
(ms.value.find(params.local.value) != std::string::npos));
if (found == false) return false;
found = found && (params.local.othername.empty() ||
(ms.othername.find(params.local.othername) != std::string::npos));

return found && baseCompare(ms);
}
bool baseCompare(const my_struct &ms) {
bool found = true;
found = found &&
(boost::logic::indeterminate(params.b_something) || (ms.something ==
params.b_something));
if (found == false) return false;
found = found &&
(boost::logic::indeterminate(params.b_anotherone) || (ms.anotherone ==
params.b_anotherone));
if (found == false) return false;

return found && params.CompareFunction(ms.unsignedValue);
}
};

Example of usage:
// search for an element in a container which
// value member contains "is a"
//
iter = std::find_if(vms.begin(), vms.end(),
other_searcher_exact<>(other_searcher<>::nice_params().value("is
a")));


I like this solution better because search criteria can be
specified nicer.

Could you suggest other ideas/methods how to search such data
structure?


Here is a compilable code of both versions with more usage examples.
http://www.catonmat.net/tmp/cpp.searching.container.txt


Thanks!

 

[tjsparkle]

Why not use another parameter to determine which criterias should be
searched?
I think it is more efficient than your way.

 

[Peteris Krumins]

Why not use another parameter to determine which criterias should be
searched?
I think it is more efficient than your way.

What do you mean by "another parameter"? Can you give an example?


Thanks,
P.Krumins

 

[tjsparkle]

On second thoughts, my method was the same as your second one.
I made a mistake.