Functions to keep a vector of pair<Key,Value> sorted by Key. Can replace a std::map for performance or space saving, depending on use case

sorted_vector.h

// sorted vector functions

template<typename Key, typename T>
typename std::vector<std::pair<Key, T>>::iterator
lookup(std::vector<std::pair<Key, T>> &vec, Key key)
{
    auto const end = vec.end();
    auto it = lower_bound(vec.begin(), end, key, [](std::vector<std::pair<Key, T>>::value_type const &elem, Key key) {
        return elem.first < key;
    });

    if (it !=end  &&  !(key < it->first))
        return it;
    return end;
}

template<typename Key, typename T>
typename std::vector<std::pair<Key, T>>::const_iterator
lookup(std::vector<std::pair<Key, T>> const &vec, Key key)
{
    auto const end = vec.cend();
    auto it = lower_bound(vec.cbegin(), end, key, [](std::vector<std::pair<Key, T>>::value_type const &elem, Key key) {
        return elem.first < key;
    });

    if (it !=end  &&  !(key < it->first))
        return it;
    return end;
}

template<typename Key, typename T>
typename std::vector<std::pair<Key, T>>::iterator
insert(std::vector<std::pair<Key, T>> &vec, Key key)
{
    auto const end = vec.end();
    auto it = lower_bound(vec.begin(), end, key, [](std::vector<std::pair<Key, T>>::value_type const &elem, Key key) {
        return elem.first < key;
    });

    // already exists
    if (it !=end  &&  !(key < it->first))
        return it;

    it = vec.insert(it, std::pair<Key, T>(key, T()));

    // entries must be sorted
    assert(std::is_sorted(vec.cbegin(), vec.cend(), [](std::vector<std::pair<Key, T>>::value_type const &a, std::vector<std::pair<Key, T>>::value_type const &b){
        return a.first < b.first;
    }));

    // entries must be unique
    assert(vec.cend() == std::adjacent_find(vec.begin(), vec.end(), [](std::vector<std::pair<Key, T>>::value_type const &a, std::vector<std::pair<Key, T>>::value_type const &b){
        return a.first == b.first;
    }));

    return it;
}

template<typename Key, typename T>
T &at(std::vector<std::pair<Key, T>> &vec, Key key)
{
    return insert(vec, key)->second;
}