How to compare all items in std::map?

c++ map compare value
c++ map example
std find map c
c++ map sort by value
std::map::key_comp
map::find
map iterator c
c++ pointer to map element

I'd like to compare all values in my std::map with each other.

I'm stuck with: for linear containers, like vector, I'd loop over indices i=1; v[i].isUniform(v[i-1]). But I can't do this with maps. I'm looking forward to hear clever ideas.

Here is some pseudocode of what I want to accomplish:

class MyData
{
public:
    bool isUniform(const MyData& other) const
    {
        return this->speed == other.speed && this->ban == other.ban;
    }

private:
    bool ban;
    int  speed;
}

std::map<int, MyData> myMap;

bool allUniform = true;
for(item_1, item_2 : myMap) // how to implement this?
{
    if(!item_1.isUniform(item_2))
    {
        allUniform = false;
    }
}

What is the most elegant (readable and efficient) way to do that?

for(item_1, item_2 : myMap) // how to implement this?

But if they're all equal to each other (assuming isUniform is transitive and symmetric), that's the same as saying they're all equal to the first element. So, you can just compare each element to the first.

Naively, we get:

bool allUniform(std::map<int, MyData> const &m)
{
    if (m.empty()) return true; // or whatever makes sense for you

    auto first = m.begin();
    for (auto current = m.begin(); ++current != m.end(); )
    {
        if (!first->second.isUniform(current->second))
        {
            return false;
        }
    }
    return true;
}

You can simplify this if you don't mind comparing the first element to itself, because really most of the complexity is just avoiding that.

It'd probably be even better to use std::adjacent_find as below, or the std::all_of solution in the other answer.

bool allUniform(std::map<int, MyData> const &m)
{
    auto first_non_uniform =
        std::adjacent_find(
            m.begin(), m.end(),
            [](auto left, auto right)
            {
                return !(left->second.isUniform(right->second));
            }
           );

    return first_non_uniform == m.end();
}

map::value_comp - C++ Reference, Returns a comparison object that can be used to compare two elements to get last element std::map< char , int >::iterator it = mymap.begin(); do { std::cout� Compare A binary predicate that takes two element keys as arguments and returns a bool . The expression comp(a,b) , where comp is an object of this type and a and b are key values, shall return true if a is considered to go before b in the strict weak ordering the function defines.

You can use std::all_of for this with a lambda. That would look like

bool allUniform = std::all_of(std::next(myMap.begin()), 
                              myMap.end(), 
                              [&myMap](const auto& pair)
                              { return myMap.begin()->second.isUniform(pair.second); });

This goes from [1, N) and calls isUniform againt each of those elements against the first. all_of also short circuts so as soon as you have a non-uniform result it will end.

map::key_comp - C++ Reference, Returns a copy of the comparison object used by the container to compare keys. map::key_comp #include <iostream> #include <map> int main () { std::map< char , int > mymap key value of last element std::map< char , int >::iterator it = mymap.begin(); do { std::cout cplusplus.com, 2000-2020 - All rights reserved - v3.2 std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare.Search, removal, and insertion operations have logarithmic complexity.

Is isUniform() transitive? That is, does it follow this rule for any 3 MyData objects:

 isUniform(A, B) && isUniform(B, C) == isUniform(A, C)

If so, then you only need O(n) comparisons. Here is my test code:

#include <iostream>
#include <map>

using namespace std;

class MyData {
public:
    int value;
    MyData(int _value) : value(_value) {}

    bool isUniform(const MyData &obj) const { return value == obj.value; }

    static void checkMap(map<int, MyData> myMap) {
         bool allUniform = true;
         MyData * firstItem = nullptr;

         for (auto it = myMap.begin(); allUniform && it != myMap.end(); ++it) {
             if (firstItem == nullptr) {
                  firstItem = &it->second;
             }
             else {
                  allUniform = firstItem->isUniform(it->second);
             }
         }

         cout << "All Uniform: " << (allUniform ? "Yes" : "No") << endl;
    }
};

int main(int, char **) {
    map<int, MyData> map1;
    map<int, MyData> map2;
    MyData a1(1);
    MyData b1(1);
    MyData b2(2);
    MyData c1(1);

    // Should be uniform
    map1.insert(std::pair<int, MyData>(1, a1));
    map1.insert(std::pair<int, MyData>(2, b1));
    map1.insert(std::pair<int, MyData>(3, c1));
    MyData::checkMap(map1);

    // Should not be uniform
    map2.insert(std::pair<int, MyData>(1, a1));
    map2.insert(std::pair<int, MyData>(2, b2));
    map2.insert(std::pair<int, MyData>(3, c1));
    MyData::checkMap(map2);

    return 0;
}

With this output:

$ g++ -std=c++0x Foo.cpp -o Foo && Foo
All Uniform: Yes
All Uniform: No

map::key_comp, Returns a copy of the comparison object used by the container to compare keys. map::key_comp #include <iostream> #include <map> int main () { std::map< char , int > mymap key value of last element std::map< char , int >::iterator it = mymap.begin(); do { std::cout cplusplus.com, 2000-2013 - All rights reserved - v3.1 std::map<std::string, int>::iterator it = mapOfWordCount.begin(); Now, let’s iterate over the map by incrementing the iterator until it reaches the end of map. Also, map internally stores element in a std::pair format, therefore each iterator object points to an address of pair.

You can use the standard algorithm std::adjacent_find.

For example

#include <iostream>
#include <iomanip>
#include <map>
#include <iterator>
#include<algorithm>

class MyData
{
public:
    MyData( bool ban, int speed ) : ban( ban ), speed( speed )
    {
    }

    bool isUniform(const MyData& other) const
    {
        return this->speed == other.speed && this->ban == other.ban;
    }

private:
    bool ban;
    int  speed;
};



int main() 
{
    std::map<int, MyData> myMap =
    {
        { 1, { true, 100 } }, { 2, { true, 100 } }, { 3, { true, 100 } }    
    };

    auto it = std::adjacent_find( std::begin( myMap ), std::end( myMap ),
                                  []( const auto &p1, const auto &p2 ) 
                                  {
                                    return not p1.second.isUniform( p2.second );
                                  } );

    bool allUniform = it == std::end( myMap );

    std::cout << std::boolalpha << allUniform << '\n';

    return 0;
}

The program output is

true

std::map, bool operator==( const std::map<Key,T,Compare,Alloc>& lhs, number of elements and each element in lhs compares equal with the element� Erases all elements that satisfy the predicate pred from the container. Equivalent to

Compare all elements in a collection to the first one:

template<class M, class F>
bool allEqual( M const& m, F&& f ) {
  using std::begin; using std::end;
  auto b = begin(m);
  auto e = end(m);
  if (b == e) return true;
  for (auto it = std::next(b); it != e; ++it)
    if (!f( *b, *it))
      return false;
  return true;
}

compare all elements pairwise:

template<class M, class F>
bool pairwiseCompare( M const& m, F&& f ) {
  for (auto&& a:m)
    for (auto&& b:m)
    {
      if (std::addressof(a) == std::addressof(b))
        continue;
      if (!f(a,b))
        return false;
    }
  return true;
}

this won't work on pseudo-containers like std::vector<bool>; well, it sort of will, but it will wastefully self-compare elements.

operator==,!=,<,<=,>,>=,<=>(std::map , If no comparison operator is provided, keys are compared with operator< for the key type. map indexed by doubles containing strings std::map<double, std:: string, In a multimap, the erasure removes all elements with the associated key. Comparing std::map objects with different external key sorting criteria. We can compare two std::map objects using operator ==, < , > etc but with same type of key

map and multimap Operations, This stored object is a comparison function that is accessed by calling map, Constructs a list of a specific size or with elements of a specific value or using namespace std; map <int, int> m1; map <int, int> :: iterator m1_Iter;� List of all functions of Map: map insert() in C++ STL– Insert elements with a particular key in the map container. . map count() function in C++ STL– Returns the number of matches to element with key value ‘g’ in the map. map equal_range() in C++ STL– Returns an iterator of pairs. The pair refers to the bounds of a range that includes

map Class, The map::key_comp() is a function in STL in C++ that returns a copy of comparison object used by container that compare keys. using namespace std; key value of last element Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry� Key = Word (std::string) Value = Word’s frequency count (int) std::map<std::string, int> mapOfWords; As no external sorting criteria for key(std::string) is specified in above std::map, therefore it will use default key sorting criteria i.e operator < and all elements will be arranged inside std::map in alphabetical sorted order of keys.

map key_comp() function in C++ STL, In order to use any object as a key in std::map , we have to tell the map how to compare the two objects using a comparison function in the third parameter of� In this article will discuss how to search for all the elements in map with given value. Map internally store elements in Key-Value pair. In which keys are unique but values can be duplicate. There are member functions to search pairs by key i.e. std::map::find(). But there is no direct function to search for all the elements with given value.

Comments
  • What does isUniform actually do? There may be a clever way to check the whole map without making O(n^2) comparisons like you're thinking.
  • What do you mean by "compare all values with each other"? Check if all values are the same? Pairwise compare each value with each other value (N*N)? Or something else?
  • Have you considered two for loops? for(item_1 : myMap) {for(item_2 : myMap) {...}}
  • Added more details about isUniform(). It essentially only checks some (not all) members on equality.
  • if you only want to compare some items, first take out those items and put them in a separate map. Then use std::all_of or any of the excellent solutions given below on that map.
  • Yes, or just use std::all_of.
  • The need for transitivity of isUniform is a very good point.