search part of an item in a set

Question

is there a way to search a part of an item in a set? I have a set of pairs std::set< std::pair<double, unsigned> > and want to search for an item via a given double. Is there any way I can do this convenient instead of manually creating a pair and searching for it?

Answer 1

Given that your set uses the standard comparison operator to define the ordering within the set, and given that the double element comes first in the pair, the sorting order inside the set is defined primarily by the double elements of the pair (and only for pairs that share the double element will the second element be taken into account for the ordering).

Therefore, the only thing you need to do is to define a comparison operator that compares pairs with single doubles in both directions (note I use C++11 syntax in several places):

using std::pair;
using std::set;

typedef pair<double,unsigned>  pair_t;
typedef set<pair_t>            set_t;
typedef set_t::iterator        it_t;

struct doublecmp
{
  /* Compare pair with double. */
  bool operator()(const pair_t &p, double d)
  { return (p.first < d); }

  /* Compare double with pair. */
  bool operator()(double d, const pair_t &p)
  { return (d < p.first); }
};

And with this in place, you can use the std::equal_range algorithm to find the range of all pairs in the set that have a given double d as first element:

std::equal_range(begin(s),end(s),d,doublecmp());

If this is compiled with optimization, the instantiation of doublecmp() is a no-op.

You'll find a fully working code example here.

Why does this work?
Given that your set is declared as set<pair<double,unsigned>>, you are using the default comparison operator less<pair<double,unsigned>>, which is the same as the standard operator< for pair. That is defined as the lexicographic ordering (20.3.3/2 in C++11, or 20.2.2/2 in C++03), therefore the first element of each pair is the primary sorting criterion.

Caveat 1 The solution will generally not work if you declare your set to use a different comparison operator than the default one. It also won't work if the part of the pair you use as searching criterion is the second, rather than the first element.

Caveat 2 The data type used in the search criterion is a floating point type. Equality checks (including the operator<-based indirect equality checking performed by std::equal_range) for floating point numbers are generally difficult. The double you are searching for may have been computed in a way that suggests it should be mathematically identical to certain values in the set, but std::equality_range might not find them (nor would std::find_if suggested in other answers). For equality checks it is generally a good idea to allow for a small ("up to some epsilon") difference between the value you are looking for and the values you consider as matches. You can accomplish this by replacing std::equal_range with explicit calls to std::lower_bound and std::upper_bound and taking into account a parameter epsilon:

pair<it_t,it_t> find_range(set_t &s, double d, double epsilon)
{
   return {std::lower_bound(begin(s),end(s),d - epsilon,doublecmp()),
           std::upper_bound(begin(s),end(s),d + epsilon,doublecmp())};
}

This leaves the question how to determine the right value for epsilon. This is generally difficult. It is usually computed as an integer multiple of std::numeric_limits<double>::epsilon, but choosing the right factor can be tricky. You'll find more information about this in How dangerous is it to compare floating point values.

Answer 2

Since the set isn't ordered according to your search criteria, you could use std::find_if with a predicate that checks only the pair's first element. This will return an iterator to the first matching element, with the usual caveats about comparing floating point numbers for equality.

double value = 42.;
auto it = std::find_if(the_set.begin(), the_set.end(), 
                       [&value](const std::pair<double, unsigned>& p) { return p.first==value; }); 

Answer 3

I'm not sure if this is what you're looking for or not:

#include <iostream>
#include <set>
#include <utility>
#include <algorithm>

using namespace std;


struct Finder{
    template<typename Value>
    bool operator()(const Value& first, const Value& v) const{
        return first == v;      
    }
};

template <typename Value>
struct FirstValueValue{
    FirstValueValue(const Value& value): value(value){};
    template<typename Pair>
    bool operator()(const Pair& p) const{
        return p.first == value;
    }
    Value value;
};

int main(int argc, char *argv[]) {
    typedef std::set<std::pair<double,unsigned int> > SetOfPairs;
    SetOfPairs myset;
    myset.insert(std::make_pair(2.0,1));
    myset.insert(std::make_pair(5.7,2));


    Finder finder;
    double v = 2.0;
    for(SetOfPairs::iterator it = myset.begin(); it != myset.end(); it++){

        if( finder(it->first,v) ){
            cout << "found value " << v << std::endl;
        }
    }

    FirstValueValue<double> find_double_two(2.0);

    myset.insert(std::make_pair(2.0,100));
    unsigned int count =    std::count_if(myset.begin(),myset.end(),find_double_two);
    cout << "found " << count << " occurances of " << find_double_two.value;

}

Which prints out:

found value 2
found 2 occurances of 2

I don't know what your needs are or if boost libraries are allowed but you could look into Boost Multi Index if you have to index off one part of the pair a lot.

Hope this helps. Good luck.