Поиск в массиве по компоненту значения (сложный тип)

typedef std::pair<int, int> data_pr;
typedef std::vector<data_pr> data_t;

data_t mydata;
data_t::iterator it = std::find(mydata.begin(), mydata.end(), value);

if (element.first == value)

Если вектор не отсортирован, то вряд ли получится найти нужный элемент быстрее, чем за O(n) с помощью линейного поиска.

Поскольку проверку выполняет некий алгоритм, а не обычное сравнение, то стоит использовать std::find_if:

Лямбда

data_t mydata;
int value = 0;
data_t::iterator it = 
    std::find_if(
        mydata.begin(),
        mydata.end(),
        [value](const data_pr& elem) { return elem.first == value; }
    );

Функциональный объект

class data_pr_Comparer {
private:
    int _value;
public:
    data_pr_Comparer(int value) : _value(value) {}
    bool operator()(const data_pr& elem) const {
        return elem.first == _value;
    }
};
void foobar() {
    data_t mydata;
    int value = 0;
    data_t::iterator it = 
        std::find_if(
            mydata.begin(),
            mydata.end(),
            data_pr_Comparer(value)
        );
}

В целом оба этих подхода имеют право на жизнь, но функциональные объекты предоставляют дополнительные возможности - сохранение состояния между вызовами, например. Но, поскольку ваш пример не требует каких-то особых условий - используйте лямбду.

В дополнении к предыдущему ответу:

Если задача позволяет, то я бы сохранил std::unordered_map<int, int> вместо того, чтобы хранить вектор пар. Тогда проще получать результат, и время выполнения короче.

std::unordered_map<int, int>::const_iterator
check_1(const  std::unordered_map<int, int>& m, const int value)
{
    return m.find(value);
}

Ну а для варианта вектора пар(как у вас), существуют масса способов(не только варианты с предыдущим ответом). Например, можно определить шаблонные функции(как вы и просили, определяем возвращающие итератор функции)

using data_pr = std::pair<int, int>;
using data_t = std::vector<data_pr>;
// предикат для проверки
template <int value>
bool
Pred(const data_pr& pr)
{
    return pr.first == value;
}
//сама проверка
template<int value>
data_t::const_iterator
check_2(const data_t& v)
{
    return std::find_if(v.begin(), v.end(), Pred<value>);
}

Может иметь место и вариант без использования альгоритмов:

vector<std::pair<int, int> >::const_iterator
check_3(const vector<std::pair<int, int> > &v, const int value)
{
    auto It = v.begin();
    while (It->first != value)
            ++It;
    return It;
}

И т.д.

поскольку у меня в задаче сжиралась вся память (16ГБ), то нашел более оптимальный способ (опять же для моей задачи):

делал 2 прохода по всем данным, создав таблицу, где data_pr.first служило как индекс в таблицу на 8ГБ - таблица для значений в диапазоне 0x00000000 - 0x7FFFFFFF и затем таблица в диапазоне 0x80000000 - 0xFFFFFFFF

если требуется для такой таблицы больше памяти (хранится не 32 битное число, а выше), то диапазон сужается

В итоге работало быстро и памяти хватило