CODEWITHSUNDEEP
c++c++11containers
waas1919
waas1919

Reputation: 2635

How to find object in container by value, not key

I have a map with <int, int*>

I want to search the map for a specific value (not key) and retrieve the iterator that points to the correct int* (value of the map)

Can I use the std::find_if() ?

auto it = std::find_if(map.begin(), map.end(), compare);

where the compare should be something like:

bool compare(int* v1, int* v2)
{
 return (v1==v2);
}

What is the best way to acomplish this?

Upvotes: 0

Views: 194

Answers (2)

VP.
VP.

Reputation: 16765

You can do it like this:

#include <string>                                                                                                                                                                                                                           
#include <iostream>
#include <algorithm>
#include <map>

int main()
{
    std::map<int, std::string> m = {{1, "a"}, {2, "b"}};
    std::string value_to_find = "b";
    auto it = std::find_if(m.begin(), m.end(), [&](decltype(m)::value_type &v) {
        return v.second == value_to_find;
    });

    if (it != m.end()) {
        std::cout << it->first << std::endl;
    }
    return 0;
}

Instead of decltype() you may directly use template instance:

[&](std::map<int, std::string>::value_type &v)

Upvotes: 3

Daniel
Daniel

Reputation: 8451

std::find_if will do the job for any 'map-like' type, e.g. std::map or std::unordered_map. Note the collection does not need to be ordered; anything that defines an InputIterator (i.e. is 'iterable') will do.

Here is a function that will work for anything 'map-like' (but not 'multimap-like')

template <typename MapType>
typename MapType::const_iterator find_value(const MapType& map, const typename MapType::mapped_type& value)
{
    return std::find_if(std::cbegin(map), std::cend(map), [&value] (const auto& p) { return p.second == value; });
}

int main(int argc, const char **argv)
{
    std::unordered_map<int, char> map {{0, 'A'}, {1, 'B'}, {2, 'C'}};
    char val {'B'};
    auto it = find_value(map, val);
    if (it != std::cend(map)) std::cout << it->first << std::endl;
    return 0;
}

You should be aware that this is a linear-time algorithm (regardless of whether the map is ordered or not), and thus if this is an operation you will be using a lot, you should consider if it would be better to just store the inverse mappings too.

Upvotes: 2

Related Questions