std :: mapを使用したキーの部分一致

std :: mapオブジェクトを使用して構造体キーの部分一致を行う方法に関する質問があります。std :: mapを使用したキーの部分一致

簡単なシナリオから始めましょう。私がキーの部分マッチをしたいとしましょう、構造体の1つのメンバだけを必要とするとしましょう。私は次のマップとキーを持っています：

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が同じであれば、[私は次のようなデータ

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

を持っている場合、私はに対応するキーと値のペアを見つけることができますこのようにBにソート3、2]

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

Iはまた、部分一致[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という新しいオブジェクトに拡張されました。

識別子では、クエリキーを使用して4つのシナリオを探して部分的に一致させることができます。 4つのシナリオ（ない実際のコード）

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

私は部分的に一致するキーを特定できるので、1つのブロックでその機能を拡張できるようにしたいと考えています。

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で。

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

だけでなく、私はあなたがここで何をしているかわからないよう：それは例外がマップのコンパレータにここに起こるstrict-weak-orderingに答える

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

私は行くことができるので、これはいいですそれぞれの反復子をwhileループでに渡して、一致するすべてのキーと値のペアを見つけ、それを使って何かを行います。

map.findは、一意の一致を1つだけ返します。 iteratingの場合はmap.findを超えている必要があります。 std::mapでやろうとしていることを、少なくとも私が理解していることからすることはできません。

異なる順序で一致させたいので、別のインデックスコンテナ、またはboost :: multi_indexを使用するか、「その他」の並べ替えを線形検索するだけです。

出典

2016-12-30 21:19:14 lakeweb

"map.findは一意の一致を1つだけ返します。反復している場合、map.findを超えていなければなりません" - 一意の一致が1つだけ返されます。 whileループでstd :: findを実行すると、一致しなくなるまですべてのキーと値のペアが見つかります。 –

std :: mapを使用したキーの部分一致

答えて

関連する問題