How to compare all items in std::map?

Question

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?

Answer 1

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.

Answer 2

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