Какие могли бы быть подводные камни если бы методы с использованием key_type были объявлены примерно так? :

template<typename key_type_comparable> iterator find(const key_type_comparable& k) const

Ну или на крайний случай могли бы сделать для этого отдельный метод, например t_find.
Тогда можно было бы избавиться от конструирования временных объектов в случае если тип, используемый при поиске не совпадает с реальным типом ключа:

#include <string>
#include <set>

using namespace std;

struct string_less
{
    bool operator ()(const char* s1, const string& s2) const { return s2.compare(s1) > 0; }
    bool operator ()(const string& s1, const char* s2) const { return s1 < s2; }
    bool operator ()(const string& s1, const string& s2) const { return s1 < s2; }
};

int main(void)
{
    typedef set<string, string_less> set_type;

    set_type s;

    s.insert("xxx");
    s.insert("yyy");
    s.insert("zzz");

    // при поиске не создается временная переменная типа string, 
    // поскольку компаратор не требует идентичности типов
    set_type::iterator it = s/*<const char*>*/.t_find("xxx");

    return 0;
}

Или вот ещё вариант, std::set с упорядовачиванием по члену структуры и поиском по типу этого члена:

struct foo
{
    foo(int x, int y, int z) : x(x), y(y), z(z) {}
    int x,y,z;
};

template<class T,typename M, M T::*m_ptr>
struct member_less
{
    template<typename U> bool operator ()(const U& k, const T& v) const { return k < v.*m_ptr; }
    template<typename U> bool operator ()(const T& v, const U& k) const { return v.*m_ptr < k; }
    bool operator ()(const T& v1, const T& v2) const { return v1.*m_ptr < v2.*m_ptr; }
};

int main(void)
{
    // set<foo>, упорядоченный по x
    typedef set<foo, member_less<foo, int, &foo::x> > set_type;

    set_type s;

    s.insert(foo(1,2,3));
    s.insert(foo(2,3,4));
    s.insert(foo(4,5,6));

    // при поиске не требуется создавать переменную типа foo
    set_type::iterator it = s.find(2);

    return 0;
}

Здравствуйте, sokel, Вы писали:

S>Какие могли бы быть подводные камни если бы методы с использованием key_type были объявлены примерно так? :
S>

S>template<typename key_type_comparable> iterator find(const key_type_comparable& k) const

S>struct string_less
S>{
S>    bool operator ()(const char* s1, const string& s2) const { return s2.compare(s1) > 0; }
S>    bool operator ()(const string& s1, const char* s2) const { return s1 < s2; }
S>    bool operator ()(const string& s1, const string& s2) const { return s1 < s2; }
S>};
S>

Я думаю, что основная проблема в формализации, документировании и без того сложной библиотеки без особых выигрышей.
Надо описать, что же такое string_less — это уже не binary predicate, а чудо-юдо. Что такое сравнение двух _разных_ объектов? Каким свойством должен удовлетворять этот объект? Сейчас такие предикаты описываются как "The key comparison function, a Strict Weak Ordering ", с этим понятием знакомы студенты технических факультетов (из математики).
std::binary_search вполне подходит для твоей оптимизации поиска элемента, хотя я не уверен, что будет выигрыш, потому что std::set::begin() возвращает не RandomAccess Iterator, а лишь Forward Iterator