使用std :: map部分匹配密鑰

我有一個關於如何在跨結構的兩個不同成員進行匹配時使用std :: map對象對結構鍵進行部分匹配的問題。使用std :: map部分匹配密鑰

讓我們從一個簡單的場景開始。假設我想對一個鍵進行部分匹配，只涉及結構的一個成員。我有以下地圖和關鍵字：

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已被擴展到一個新的被稱爲標識符的對象。

標識符讓我做部分匹配，使用查詢鍵尋找四個方案。它看起來對四種情況（而不是實際的代碼）

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

然而，在實踐中，我需要在同一時間做對每個場景只設置部分匹配的一個（1〜4）while循環。

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

我希望能夠加強它，以便在一個塊中我可以識別部分匹配的密鑰。

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() 

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

來源

2016-12-30 Otto Nahmee

你不能用一個std::map。它回答到strict-weak-ordering唯一的例外發生在這裏的映射的比較：

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

這是好的，因爲我可以去通過每個迭代器在一個while循環中找到每個匹配的鍵值對，並用它做一些事情。

map.find將只返回一個唯一匹配。如果您正在「迭代」，則必須超出map.find。至少根據我的理解，你不能做你想用std::map做的事情。

因爲你想匹配不同的順序，我沒有看到任何方式，但使用另一個索引容器，或boost :: multi_index，或者，只是做'其他'排序的線性搜索。

來源

2016-12-30 21:19:14 lakeweb

「map.find將只返回一個唯一匹配。如果您正在'迭代'它必須超出map.find」 - 它只返回一個唯一匹配。如果我把std :: find放在while循環中，那麼我可以找到所有匹配的鍵值對，直到不再匹配。 –

使用std :: map部分匹配密鑰

回答

相關問題