Partial matching of a key using a std::map

Question

Partial matching of a key using a std::map

1.1k Views Asked by Otto Nahmee At 18 April 2025 at 09:10

I have a question regarding how to do a partial match of a struct key using a std::map object when you are matching across two different members of that struct.

Let's start with a simple scenario. Let's say I want to do a partial match for a key, only involving one member of the struct. I have the following map and key:

std::map<SimpleIdentifier, Contents>

The SimpleIdentifier is described below.

/**
 * \class SimpleIdentifier
 * \brief Used to identify and sort data in the map
 */
class SimpleIdentifier
{
public:
    SimpleIdentifier():
        idA(-1),
        idB(-1),
        partialMatch1(false) {}

    SimpleIdentifier(const long long int& a, const long long int& b):
        idA(a),
        idB(b),
        partialMatch1(false) {}

    void setPartialMatch1() { partialMatch1 = true; }

    bool operator==(const Identifier& rhs) const
    {
        return (idA == rhs.idA) && (idB == rhs.idB);
    }

    bool operator<(const Identifier& rhs) const
    {
        if (partialMatch1 || rhs.partialMatch1)
        {
            // Match A to A
            if(rhs.partialMatch1)
            {
                if(idA < rhs.idA)
                {
                    return true;
                }
            }
            else if(partialMatch1)
            {
                if(idA < rhs.idA)
                {
                    return true;
                }
            }

            return false;
        }
        else
        {
            if(idA < rhs.idA)
            {
                return true;
            }
            else if (idA == rhs.idA)
            {
                if(idB < rhs.idB)
                {
                    return true;
                }
            }

        }

        return false;
    }

private:
    long long int idA;
    long long int idB;

    bool partialMatch1;
};

This lets me sort on A, and if A is equal, then sorts on B. Thus if I have the following data

dataMap:

Key: [ 0, 0 ] Value: []
Key: [ 0, 1 ] Value: []
Key: [ 0, 2 ] Value: []
Key: [ 3, 1 ] Value: []
Key: [ 3, 2 ] Value: []
Key: [ 3, 3 ] Value: []
Key: [ 5, 3 ] Value: []
Key: [ 5, 7 ] Value: []

I can find the key-value pair corresponding to [ 3, 2 ]

Identifier perfectMatchID(3, 2);
std::map<SimpleIdentifier, Contents>::iterator it = dataMap.begin();
it = dataMap.find(perfectMatchID);

I can also find a partial match corresponding to [ 3, * ]

Identifier partialMatchID(3, 2);
partialMatchID.setPartialMatch1();
std::map<SimpleIdentifier, Contents>::iterator it = dataMap.begin();
it = dataMap.find(partialMatchID);

This is nice because I can go through each iterator in a while loop to find every matching key-value pair and do something with it.

I now want to extend it to be able to match to either member of the key matching 3, so that includes [ 3, * ] or [ *, 3 ]. SimpleIdentifier has been extended to a new objected called Identifier.

/**
 * \class Identifier
 * \brief Used to identify and sort data in the map
 */
class Identifier
{
public:
    Identifier():
        idA(-1),
        idB(-1),
        partialMatch(false),
        partialMatch1(false),
        partialMatch2(false),
        partialMatch3(false),
        partialMatch4(false) {}

    Identifier(const long long int& a, const long long int& b):
        idA(a),
        idB(b),
        partialMatch(false),
        partialMatch1(false),
        partialMatch2(false),
        partialMatch3(false),
        partialMatch4(false) {}

    void setPartialMatch() { partialMatch = true; }
    void setPartialMatch1() { partialMatch1 = true; }
    void setPartialMatch2() { partialMatch2 = true; }
    void setPartialMatch3() { partialMatch3 = true; }
    void setPartialMatch4() { partialMatch4 = true; }

    bool operator==(const Identifier& rhs) const
    {
        return (idA == rhs.idA) && (idB == rhs.idB);
    }

    bool operator<(const Identifier& rhs) const
    {
        if (partialMatch || rhs.partialMatch)
        {
            // In order to match, only 1 should be false, the other 3 may or may not be false
            //
            // Note: The issue here is that the check that validates for the rhs.partialMatch should be identical
            //       to the check that validates for partialMatch. Since this is const that may not be possible
            if(rhs.partialMatch)
            {
                unsigned int check1 = (idA < rhs.idA) ? 1 : 0; // Match A to A
                unsigned int check2 = (idB < rhs.idB) ? 1 : 0; // Match B to B
                unsigned int check3 = (idA < rhs.idB) ? 1 : 0; // Match A to B
                unsigned int check4 = (idB < rhs.idA) ? 1 : 0; // Match B to A

                if( (check1 + check2 + check3 + check4) > 0 )
                {
                    return true;
                }
            }
            else if(partialMatch)
            {
                unsigned int check1 = (idA < rhs.idA) ? 1 : 0; // Match A to A
                unsigned int check2 = (idB < rhs.idB) ? 1 : 0; // Match B to B
                unsigned int check3 = (idB < rhs.idA) ? 1 : 0; // Match B to A
                unsigned int check4 = (idA < rhs.idB) ? 1 : 0; // Match A to B

                if( (check1 + check2 + check3 + check4) > 0 )
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch1 || rhs.partialMatch1)
        {
            // Match A to A
            if(rhs.partialMatch1)
            {
                if(idA < rhs.idA)
                {
                    return true;
                }
            }
            else if(partialMatch1)
            {
                if(idA < rhs.idA)
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch2 || rhs.partialMatch2)
        {
            // Match B to B
            if(rhs.partialMatch2)
            {
                if(idB < rhs.idB)
                {
                    return true;
                }
            }
            else if(partialMatch2)
            {
                if(idB < rhs.idB)
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch3 || rhs.partialMatch3)
        {
            // Match A to B
            if(rhs.partialMatch3)
            {
                if(idA < rhs.idB)
                {
                    return true;
                }
            }
            else if(partialMatch3)
            {
                if(idB < rhs.idA)
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch4 || rhs.partialMatch4)
        {
            // Match B to A
            if(rhs.partialMatch4)
            {
                if(idB < rhs.idA)
                {
                    return true;
                }
            }
            else if(partialMatch4)
            {
                if(idA < rhs.idB)
                {
                    return true;
                }
            }

            return false;
        }
        else
        {
            if(idA < rhs.idA)
            {
                return true;
            }
            else if (idA == rhs.idA)
            {
                if(idB < rhs.idB)
                {
                    return true;
                }
            }

        }

        return false;
    }

private:
    long long int idA;
    long long int idB;

    bool partialMatch;
    bool partialMatch1;
    bool partialMatch2;
    bool partialMatch3;
    bool partialMatch4;
};

Identifier lets me do partial matching, looking for the four scenarios using a query Key. It looks for the four scenarios (not actual code)

queryKey.idA == idA
queryKey.idB == idB
queryKey.idA == idB
queryKey.idB == idA

However, in practice I need to do a while loop on each scenario only setting one of the partial matches (1 through 4) at a time.

setPartialMatch1(); // a-rhs.a
setPartialMatch2(); // b-rhs.b
setPartialMatch3(); // a-rhs.b
setPartialMatch4(); // b-rhs.a

I'd like to be able to enhance it so that in a single block I can identify the partially matching key.

setPartialMatch(); // magic

I've devised the unit test below. All of the partial matches using match 1 through match 4 work fine. However, doing a partial match so that I don't need to do each one doesn't work. You'll find that running this unit test will fail for all tests using setPartialMatch();

Any ideas or suggestions on how to get it to work, or alternatives would be great.

The full unit test is below:

/**
 * \file PartialMatchUnitTest.cpp
 *
 * \brief Unit testing for partial matching in std::map
 *
 * \author Otto Nahmee
 */

#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MODULE PartialMatchingUnitTest

#include <boost/test/unit_test.hpp>

#include <iostream>
#include <map>

/*****************************************************************************/

BOOST_AUTO_TEST_SUITE(TestSuite)

/**
 * \class Identifier
 * \brief Used to identify and sort data in the map
 */
class Identifier
{
public:
    Identifier():
        idA(-1),
        idB(-1),
        partialMatch(false),
        partialMatch1(false),
        partialMatch2(false),
        partialMatch3(false),
        partialMatch4(false) {}

    Identifier(const long long int& a, const long long int& b):
        idA(a),
        idB(b),
        partialMatch(false),
        partialMatch1(false),
        partialMatch2(false),
        partialMatch3(false),
        partialMatch4(false) {}

    void setPartialMatch() { partialMatch = true; }
    void setPartialMatch1() { partialMatch1 = true; }
    void setPartialMatch2() { partialMatch2 = true; }
    void setPartialMatch3() { partialMatch3 = true; }
    void setPartialMatch4() { partialMatch4 = true; }

    bool operator==(const Identifier& rhs) const
    {
        return (idA == rhs.idA) && (idB == rhs.idB);
    }

    bool operator<(const Identifier& rhs) const
    {
        if (partialMatch || rhs.partialMatch)
        {
            // In order to match, only 1 should be false, the other 3 may or may not be false
            //
            // Note: The issue here is that the check that validates for the rhs.partialMatch should be identical
            //       to the check that validates for partialMatch. Since this is const that may not be possible
            if(rhs.partialMatch)
            {
                unsigned int check1 = (idA < rhs.idA) ? 1 : 0; // Match A to A
                unsigned int check2 = (idB < rhs.idB) ? 1 : 0; // Match B to B
                unsigned int check3 = (idA < rhs.idB) ? 1 : 0; // Match A to B
                unsigned int check4 = (idB < rhs.idA) ? 1 : 0; // Match B to A

                if( (check1 + check2 + check3 + check4) > 0 )
                {
                    return true;
                }
            }
            else if(partialMatch)
            {
                unsigned int check1 = (idA < rhs.idA) ? 1 : 0; // Match A to A
                unsigned int check2 = (idB < rhs.idB) ? 1 : 0; // Match B to B
                unsigned int check3 = (idB < rhs.idA) ? 1 : 0; // Match B to A
                unsigned int check4 = (idA < rhs.idB) ? 1 : 0; // Match A to B

                if( (check1 + check2 + check3 + check4) > 0 )
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch1 || rhs.partialMatch1)
        {
            // Match A to A
            if(rhs.partialMatch1)
            {
                if(idA < rhs.idA)
                {
                    return true;
                }
            }
            else if(partialMatch1)
            {
                if(idA < rhs.idA)
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch2 || rhs.partialMatch2)
        {
            // Match B to B
            if(rhs.partialMatch2)
            {
                if(idB < rhs.idB)
                {
                    return true;
                }
            }
            else if(partialMatch2)
            {
                if(idB < rhs.idB)
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch3 || rhs.partialMatch3)
        {
            // Match A to B
            if(rhs.partialMatch3)
            {
                if(idA < rhs.idB)
                {
                    return true;
                }
            }
            else if(partialMatch3)
            {
                if(idB < rhs.idA)
                {
                    return true;
                }
            }

            return false;
        }
        else if (partialMatch4 || rhs.partialMatch4)
        {
            // Match B to A
            if(rhs.partialMatch4)
            {
                if(idB < rhs.idA)
                {
                    return true;
                }
            }
            else if(partialMatch4)
            {
                if(idA < rhs.idB)
                {
                    return true;
                }
            }

            return false;
        }
        else
        {
            if(idA < rhs.idA)
            {
                return true;
            }
            else if (idA == rhs.idA)
            {
                if(idB < rhs.idB)
                {
                    return true;
                }
            }

        }

        return false;
    }

private:
    long long int idA;
    long long int idB;

    bool partialMatch;
    bool partialMatch1;
    bool partialMatch2;
    bool partialMatch3;
    bool partialMatch4;
};

/**
 * \class Contents
 * \brief Contents to get merged in
 */
struct Contents
{
public:
    Contents():
        num1(0),
        num2(0),
        num3(0),
        num4(0)
    {}

    Contents(const long long int& n1, const long long int& n2, const long long int& n3, const long long int& n4):
        num1(n1),
        num2(n2),
        num3(n3),
        num4(n4)
    {}

    long long int num1;
    long long int num2;
    long long int num3;
    long long int num4;
};

typedef std::pair<Identifier, Contents> DataPair;
typedef std::map<Identifier, Contents> DataMap;



/**
 * \brief Testing Partial matching
 */
BOOST_AUTO_TEST_CASE(PartialMatch)
{
    DataMap dataMap;

    Identifier ID0(8, 9);
    dataMap[ID0] = Contents(1,2,3,4);

    Identifier ID1(10, 11);
    dataMap[ID1] = Contents(1,2,3,4);

    Identifier ID2(12, 14);
    dataMap[ID2] = Contents(1,2,3,4);

    Identifier ID3(15, 17);
    dataMap[ID3] = Contents(1,2,3,4);

    Identifier ID4(14, 22);
    dataMap[ID4] = Contents(1,2,3,4);

    Identifier ID5(23, 25);
    dataMap[ID5] = Contents(1,2,3,4);


    // Test perfect matching
    {
        Identifier perfectMatchID1(10, 11);

        DataMap::iterator it1 = dataMap.begin();
        it1 = dataMap.find(perfectMatchID1);
        BOOST_CHECK(it1 != dataMap.end());
        BOOST_CHECK(it1->first == ID1);


        Identifier perfectMatchID3(15, 17);

        DataMap::iterator it3 = dataMap.begin();
        it3 = dataMap.find(perfectMatchID3);
        BOOST_CHECK(it3 != dataMap.end());
        BOOST_CHECK(it3->first == ID3);
    }

    // Test partial matching
    // Try to match ID1 (10, 11);
    {
        Identifier partialMatchID1(10, 100);
        Identifier partialMatchID2(110, 11);
        Identifier partialMatchID3(110, 10);
        Identifier partialMatchID4(11, 100);

        Identifier partialMatchID5(10, 0);
        Identifier partialMatchID6(0, 11);
        Identifier partialMatchID7(0, 10);
        Identifier partialMatchID8(11, 0);

        Identifier partialMatchID9(10, 11);

        partialMatchID1.setPartialMatch1(); // a-rhs.a
        partialMatchID2.setPartialMatch2(); // b-rhs.b
        partialMatchID3.setPartialMatch3(); // a-rhs.b
        partialMatchID4.setPartialMatch4(); // b-rhs.a

        partialMatchID5.setPartialMatch1(); // a-rhs.a
        partialMatchID6.setPartialMatch2(); // b-rhs.b
        partialMatchID7.setPartialMatch3(); // a-rhs.b
        partialMatchID8.setPartialMatch4(); // b-rhs.a

        partialMatchID9.setPartialMatch1();

        DataMap::iterator it1 = dataMap.begin();
        it1 = dataMap.find(partialMatchID1);
        BOOST_CHECK(it1 != dataMap.end());
        BOOST_CHECK(it1->first == ID1);

        DataMap::iterator it2 = dataMap.begin();
        it2 = dataMap.find(partialMatchID2);
        BOOST_CHECK(it2 != dataMap.end());
        BOOST_CHECK(it2->first == ID1);

        DataMap::iterator it3 = dataMap.begin();
        it3 = dataMap.find(partialMatchID3);
        BOOST_CHECK(it3 != dataMap.end());
        BOOST_CHECK(it3->first == ID1);

        DataMap::iterator it4 = dataMap.begin();
        it4 = dataMap.find(partialMatchID4);
        BOOST_CHECK(it4 != dataMap.end());
        BOOST_CHECK(it4->first == ID1);

        DataMap::iterator it5 = dataMap.begin();
        it5 = dataMap.find(partialMatchID5);
        BOOST_CHECK(it5 != dataMap.end());
        BOOST_CHECK(it5->first == ID1);

        DataMap::iterator it6 = dataMap.begin();
        it6 = dataMap.find(partialMatchID6);
        BOOST_CHECK(it6 != dataMap.end());
        BOOST_CHECK(it6->first == ID1);

        DataMap::iterator it7 = dataMap.begin();
        it7 = dataMap.find(partialMatchID7);
        BOOST_CHECK(it7 != dataMap.end());
        BOOST_CHECK(it7->first == ID1);

        DataMap::iterator it8 = dataMap.begin();
        it8 = dataMap.find(partialMatchID8);
        BOOST_CHECK(it8 != dataMap.end());
        BOOST_CHECK(it8->first == ID1);

        DataMap::iterator it9 = dataMap.begin();
        it9 = dataMap.find(partialMatchID9);
        BOOST_CHECK(it9 != dataMap.end());
        BOOST_CHECK(it9->first == ID1);
    }

    // Try to match ID1 (10, 11);
    {
        Identifier partialMatchID1(10, 100);
        Identifier partialMatchID2(110, 11);
        Identifier partialMatchID3(11, 100);
        Identifier partialMatchID4(110, 10);

        Identifier partialMatchID5(10, 0);
        Identifier partialMatchID6(0, 11);
        Identifier partialMatchID7(11, 0);
        Identifier partialMatchID8(0, 10);

        Identifier partialMatchID9(10, 11);

        partialMatchID1.setPartialMatch();
        partialMatchID2.setPartialMatch();
        partialMatchID3.setPartialMatch();
        partialMatchID4.setPartialMatch();

        partialMatchID5.setPartialMatch();
        partialMatchID6.setPartialMatch();
        partialMatchID7.setPartialMatch();
        partialMatchID8.setPartialMatch();

        partialMatchID9.setPartialMatch();

        DataMap::iterator it1 = dataMap.begin();
        it1 = dataMap.find(partialMatchID1);
        BOOST_CHECK(it1 != dataMap.end());
        BOOST_CHECK(it1->first == ID1);

        DataMap::iterator it2 = dataMap.begin();
        it2 = dataMap.find(partialMatchID2);
        BOOST_CHECK(it2 != dataMap.end());
        BOOST_CHECK(it2->first == ID1);

        DataMap::iterator it3 = dataMap.begin();
        it3 = dataMap.find(partialMatchID3);
        BOOST_CHECK(it3 != dataMap.end());
        BOOST_CHECK(it3->first == ID1);

        DataMap::iterator it4 = dataMap.begin();
        it4 = dataMap.find(partialMatchID4);
        BOOST_CHECK(it4 != dataMap.end());
        BOOST_CHECK(it4->first == ID1);

        DataMap::iterator it5 = dataMap.begin();
        it5 = dataMap.find(partialMatchID5);
        BOOST_CHECK(it5 != dataMap.end());
        BOOST_CHECK(it5->first == ID1);

        DataMap::iterator it6 = dataMap.begin();
        it6 = dataMap.find(partialMatchID6);
        BOOST_CHECK(it6 != dataMap.end());
        BOOST_CHECK(it6->first == ID1);

        DataMap::iterator it7 = dataMap.begin();
        it7 = dataMap.find(partialMatchID7);
        BOOST_CHECK(it7 != dataMap.end());
        BOOST_CHECK(it7->first == ID1);

        DataMap::iterator it8 = dataMap.begin();
        it8 = dataMap.find(partialMatchID8);
        BOOST_CHECK(it8 != dataMap.end());
        BOOST_CHECK(it8->first == ID1);

        DataMap::iterator it9 = dataMap.begin();
        it9 = dataMap.find(partialMatchID9);
        BOOST_CHECK(it9 != dataMap.end());
        BOOST_CHECK(it9->first == ID1);
    }


    // Try to match ID3 (15, 17);
    {
        Identifier partialMatchID1(15, 100);
        Identifier partialMatchID2(110, 17);
        Identifier partialMatchID3(17, 100);
        Identifier partialMatchID4(110, 15);

        Identifier partialMatchID5(15, 0);
        Identifier partialMatchID6(0, 17);
        Identifier partialMatchID7(17, 0);
        Identifier partialMatchID8(0, 15);

        Identifier partialMatchID9(15, 17);

        partialMatchID1.setPartialMatch();
        partialMatchID2.setPartialMatch();
        partialMatchID3.setPartialMatch();
        partialMatchID4.setPartialMatch();

        partialMatchID5.setPartialMatch();
        partialMatchID6.setPartialMatch();
        partialMatchID7.setPartialMatch();
        partialMatchID8.setPartialMatch();

        partialMatchID9.setPartialMatch();


        DataMap::iterator it1 = dataMap.begin();
        it1 = dataMap.find(partialMatchID1);
        BOOST_CHECK(it1 != dataMap.end());
        BOOST_CHECK(it1->first == ID3);

        DataMap::iterator it2 = dataMap.begin();
        it2 = dataMap.find(partialMatchID2);
        BOOST_CHECK(it2 != dataMap.end());
        BOOST_CHECK(it2->first == ID3);

        DataMap::iterator it3 = dataMap.begin();
        it3 = dataMap.find(partialMatchID3);
        BOOST_CHECK(it3 != dataMap.end());
        BOOST_CHECK(it3->first == ID3);

        DataMap::iterator it4 = dataMap.begin();
        it4 = dataMap.find(partialMatchID4);
        BOOST_CHECK(it4 != dataMap.end());
        BOOST_CHECK(it4->first == ID3);

        DataMap::iterator it5 = dataMap.begin();
        it5 = dataMap.find(partialMatchID5);
        BOOST_CHECK(it5 != dataMap.end());
        BOOST_CHECK(it5->first == ID3);

        DataMap::iterator it6 = dataMap.begin();
        it6 = dataMap.find(partialMatchID6);
        BOOST_CHECK(it6 != dataMap.end());
        BOOST_CHECK(it6->first == ID3);

        DataMap::iterator it7 = dataMap.begin();
        it7 = dataMap.find(partialMatchID7);
        BOOST_CHECK(it7 != dataMap.end());
        BOOST_CHECK(it7->first == ID3);

        DataMap::iterator it8 = dataMap.begin();
        it8 = dataMap.find(partialMatchID8);
        BOOST_CHECK(it8 != dataMap.end());
        BOOST_CHECK(it8->first == ID3);

        DataMap::iterator it9 = dataMap.begin();
        it9 = dataMap.find(partialMatchID9);
        BOOST_CHECK(it9 != dataMap.end());
        BOOST_CHECK(it9->first == ID3);
    }


}

BOOST_AUTO_TEST_SUITE_END()

/*****************************************************************************/

Original Q&A

There are 1 best solutions below

**lakeweb** · Answer 1

You can't with a std::map. It answers to strict-weak-ordering The exception happens here in the map's comparator:

{   // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
return (!_Pred(_Left, _Right)
    ? false
    : _Pred(_Right, _Left)
        ? (_DEBUG_ERROR2("invalid comparator", _File, _Line), true)
        : true);

As well as I'm not sure what you are doing here:

Identifier partialMatchID(3, 2);
partialMatchID.setPartialMatch1();
std::map<SimpleIdentifier, Contents>::iterator it = dataMap.begin();
it = dataMap.find(partialMatchID);

This is nice because I can go through each iterator in a while loop to find every matching key-value pair and do something with it.

map.find will return only one unique match. If you are 'iterating' it must be beyond map.find. You can not do what you are trying to do with std::map, at least from what I understand.

Because you want to match on different ordering, I don't see any way but to use another indexing container, or, boost::multi_index, or, just do a linear search for the 'other' ordering.

Partial matching of a key using a std::map

There are 1 best solutions below

Related Questions in C++

Related Questions in STDMAP

Trending Questions

Popular # Hahtags

Popular Questions