Хочется чего-то вот такого

class A;

template<typename iter_type>
void print(const iter_type& it)
{
    std::cout << "key one: " << it->key->first << "key two: " << it->key->second << it->value.to_string();
}

int main()
{
    map< std::string, std::string, A> my_map; // key1, key2, value
    my_map.insert("first_key", "second_key", A());
    auto it1 = my_map.find1st("key1");
    if (it1 != my_map.end())
        print(it1);

    auto it2 = my_map.find2d("key2");
    if (it2 != my_map.end())
        print(it2);
}

т.е. чтобы искать было можно по любому ключу. Чтобы с итераторами и чтобы оба ключа и волью в итераторе было. Сами ключи и их сочетание уникальны.