Find the lowest key pair for the first element in the pair using STL Map

Question 1

I would go for the most straightforward solution:

auto previous_first = 0;
auto is_first_iteration = true;
for (const auto& key_value : myMap) {
  const auto& key = key_value.first;
  const auto& value = key_value.second;
  if (is_first_iteration || key.first != previous_first) {
    is_first_iteration = false;
    previous_first = key.first;
    // do something here!
  }
}

Here you just simply iterate over each element (and we rely on the property of std::map that elements are sorted. And pairs are sorted themselves by the first and then by the second element). On each step we remember the previous first element - if on this step it's the same we just skip this step.

@AndrewDurward points out that this problem can be solved in logarithmic time. This is true only partially. First, this problem can be solved in logarithmic time only in the best case. What if you have N elements and each of them has different first ? You have N elements in the answer and obviously, you cannot output N elements in logarithmic time.

Question 2

You can use a custom comparator

struct comp {
bool operator()(const std::pair<int, int>&x, const std::pair<int, int>& y ) const
{
    return x.second < y.second;
}
};

std::map<std::pair<int, int>, struct A,comp > myMap;

And then find then use find_if with first element of pair.

In your case by std::less<T> by default sorts as expected.

So following will work without custom comparator i.e. with just

std::map<std::pair<int, int>, struct A > myMap;

int search_id=1; //First Element of pair, you can use entire pair too, 
//but that will defeat the purpose of "lowest pair"
auto it=std::find_if(myMap.begin() , myMap.end() , 
                [search_id](const std::pair<std::pair<int, int>, A>& x)
                { return x.first.first == search_id; } 
                );

if(it != myMap.end())
{
std::cout<<it->first.first<<" "<<it->first.second;
}

Edit : You can use it as a function to loop through all elements

Question 3

With a tiny overload helper, you can just use std::lower_bound: Live on Coliru

The first match listed will be the one you looked for (std::pair<> is already order by (first,right), ascending).

The helper, in this case, is:

struct ByKeyFirst final { int value; };
inline bool operator<(Map::value_type const& v, ByKeyFirst target) { 
    return v.first.first < target.value; 
}

As you can see, the only 'added complexity' is in checking that a match was found at all, but efficiency should be fine. And you can always hide the complexity in a (unit-testable) helper:

Map::const_iterator byKeyFirst(Map const& map, int target)
{
    auto const e = end(map);
    auto lbound = lower_bound(begin(map), e, ByKeyFirst { target });
    if (lbound != e && lbound->first.first == target)
        return lbound;
    return e;
}

Now the lookup code becomes merely:

int main()
{
    const Map myMap { 
        { { 1, 200 }, {} },
        { { 1, 202 }, {} },
        { { 2, 198 }, {} },
        { { 2, 207 }, {} },
    };

    auto match = byKeyFirst(myMap, 2);

    if (end(myMap) != match)
        std::cout << "Matching key: (" << match->first.first << "," << match->first.second << ")\n";
}

Full demo

#include <map>
#include <tuple>
#include <limits>

using namespace std;

struct A {};

using Pair = pair<int,int>;
using Map  = map<Pair, A>;

namespace /*anon*/
{
    struct ByKeyFirst final { int value; };
    inline bool operator<(Map::value_type const& v, ByKeyFirst target) { return v.first.first < target.value; }

    Map::const_iterator byKeyFirst(Map const& map, int target)
    {
        // you can just find the first match, Pair is already sorted by `first`, then `second`:
        auto const e = end(map);
        auto lbound = lower_bound(begin(map), e, ByKeyFirst { target });
        if (lbound != e && lbound->first.first == target)
            return lbound;
        return e;
    }
}

#include <iostream>

int main()
{
    const Map myMap { 
        { { 1, 200 }, {} },
        { { 1, 202 }, {} },
        { { 2, 198 }, {} },
        { { 2, 207 }, {} },
    };

    auto match = byKeyFirst(myMap, 2);

    if (end(myMap) != match)
        std::cout << "Matching key: (" << match->first.first << "," << match->first.second << ")\n";
}

Question 4

Since the map keys are sorted lexicographically, then they can also be viewed as being sorted by their first element (albeit with some duplicates). This means we can leverage any of the standard algorithms that operate on sorted ranges so long as we provide an appropriate predicate. In this case, the predicate that compares the first element of the key can be written as follows:

    typedef std::map<std::pair<int, int>, struct A> myMap_t;

    auto compare_first = [](
        myMap_t::value_type const & p1,
        myMap_t::value_type const & p2 )
    {
        return p1.first.first < p2.first.first;
    };

With that done, we just need to select the correct algorithm to iterate over the desired map elements. We want the first element in the map, then the first element which is not "equivalent" to that one as defined by our predicate. This is exactly what std::upper_bound does.

auto e1 = myMap.begin();
auto e2 = std::upper_bound( e1, myMap.end(), *e1, compare_first );

Or we can loop over them:

for( auto it = myMap.begin(); it != myMap.end(); it = std::upper_bound( it, myMap.end(), *it, compare_first ) )
        std::cout << it->first.first << " " << it->first.second << "\n";

Full code is here.