こんなんでどうかな？std::setで順位もつけてテストしてみた。

typedef std::pair<int, int> PII;

struct Cmp : public std::binary_function<PII, PII, bool> {
bool operator()(PII i, PII j) {
return i.first <= j.first && i.second < j.second;
}
};

int main()
{
std::set<PII, Cmp> s;

s.insert(std::make_pair(1, 1));
s.insert(std::make_pair(1, 2));
s.insert(std::make_pair(2, 3));
s.insert(std::make_pair(3, 4));
s.insert(std::make_pair(3, 5));

std::set<PII, Cmp>::iterator pos;
pos = s.upper_bound(std::make_pair(3, 1));
pos--;

std::cout << "key = " << pos->first << ", value = " << pos->second << std::endl;
}