c++ - 使用 std::map 部分匹配键

标签 c++ stdmap

我有一个问题，关于当您在该结构的两个不同成员之间进行匹配时，如何使用 std::map 对象对该结构键进行部分匹配。

让我们从一个简单的场景开始。假设我想对一个键进行部分匹配，只涉及该结构的一个成员。我有以下 map 和 key :

std::map<SimpleIdentifier, Contents>

下面描述了 SimpleIdentifier。

/**
 * \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;
};

这让我可以对 A 进行排序，如果 A 相等，则对 B 进行排序。因此，如果我有以下数据

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: []

可以找到[ 3, 2 ]对应的键值对

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

我还可以找到对应于 [ 3, * ] 的部分匹配

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

这很好，因为我可以在 while 循环中遍历每个迭代器以找到每个匹配的键值对并对其进行处理。

我现在想扩展它以便能够匹配匹配 3 的键的任何一个成员，以便包括 [ 3, * ] 或 [ *, 3 ]。 SimpleIdentifier 已扩展为一个名为 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 让我可以进行部分匹配，使用查询 Key 查找四种场景。它寻找四种场景(不是实际代码)

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

但是，在实践中，我需要在每个场景中执行一个 while 循环，一次只设置一个部分匹配项(1 到 4)。 

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

我希望能够对其进行增强，以便在单个 block 中识别部分匹配的 key 。

setPartialMatch(); // magic

我设计了下面的单元测试。使用匹配 1 到匹配 4 的所有部分匹配都可以正常工作。但是，进行部分匹配以便我不需要对每一个都进行匹配是行不通的。您会发现运行此单元测试对于所有使用 setPartialMatch() 的测试都会失败；

任何关于如何使其工作或替代方案的想法或建议都很棒。

完整的单元测试如下:

/**
 * \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()

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

最佳答案

你不能使用 std::map。它回答 strict-weak-ordering异常发生在 map 的比较器中:

{   // 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);

以及我不确定你在这里做什么:

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 将只返回一个唯一的匹配项。如果您正在“迭代”，则它必须超出 map.find。你不能用 std::map 做你想做的事，至少从我的理解来看是这样。

因为你想匹配不同的顺序，我看不出有什么办法只能使用另一个索引容器，或者 boost::multi_index，或者只是对“其他”顺序进行线性搜索。

关于c++ - 使用 std::map 部分匹配键，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41402254/

上一篇：C++ SFML 网络 : Can't Establish a TCP Connection

下一篇：c++ - 加入线程时的性能问题

相关文章：

c++(不> = 11)，初始化映射中的嵌套对

c++ - 为什么调用 CDialog::OnShowWindow 会挂起我的应用程序？

c++ - header 和 ODR 中的类定义？

c++ - 整数和位数组之间的按位运算

c++ - 如何使模板别名作为模板类

c++ - 使用 goto 转义控制结构是否会产生不同的程序集？

c++ - 检查 std::map 的迭代器是否指向倒数第二个元素

c++ - 如何使用 uint64_t 键类型从 std::map<int, std::string> 返回值？

c++ - 删除元素时 map 迭代器如何失效？

c++ - C++ Map 中查找 float 键的优化

©2024 IT工具网  联系我们