比较c++和pugixml 1.4中的两个xpath_node_set

Question

我有两个XML文件，如果它们相等，我想比较其中的一部分。XML文件可能非常不同，但我给出了一个示例。我有以下XML文件:

<EXECUTION_SET>
  <RESULT query_id="7" >
    <OP>
      <PROJ>
        <COLUMN col_name="City.ID" col_type="3" col_length="11" />
        <OP>
          <JOIN>
            <OP>
              <TABLE name="City" alias="City" access_type="5" total_record_length="67">
                <COLUMN col_name="ID" col_type="3" col_length="11" raw_length="4" /> 
                <COLUMN col_name="Name" col_type="254" col_length="35" raw_length="35" /> 
                <COLUMN col_name="CountryCode" col_type="254" col_length="3" raw_length="3" /> 
                <COLUMN col_name="District" col_type="254" col_length="20" raw_length="20" /> 
                <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
              </TABLE>
            </OP>
            <OP>
              <SEL>
                <COND>
                  <COND>
                    <VALUE><VARIABLE>Country.Population</VARIABLE></VALUE>
                  </COND>
                  <BOP><![CDATA[>]]></BOP>
                  <COND>
                    <VALUE><CONSTANT>80000000</CONSTANT></VALUE>
                  </COND>
                </COND>
                <OP>
                <OP>
                  <TABLE name="Country" alias="Country" access_type="5" total_record_length="261">
                    <COLUMN col_name="Code" col_type="254" col_length="3" raw_length="3" /> 
                    <COLUMN col_name="Name" col_type="254" col_length="52" raw_length="52" /> 
                    <COLUMN col_name="Continent" col_type="254" col_length="13" raw_length="1" /> 
                    <COLUMN col_name="Region" col_type="254" col_length="26" raw_length="26" /> 
                    <COLUMN col_name="SurfaceArea" col_type="4" col_length="10" raw_length="4" /> 
                    <COLUMN col_name="IndepYear" col_type="2" col_length="6" raw_length="2" /> 
                    <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
                    <COLUMN col_name="LifeExpectancy" col_type="4" col_length="3" raw_length="4" /> 
                    <COLUMN col_name="GNP" col_type="4" col_length="10" raw_length="4" /> 
                    <COLUMN col_name="GNPOld" col_type="4" col_length="10" raw_length="4" /> 
                    <COLUMN col_name="LocalName" col_type="254" col_length="45" raw_length="45" /> 
                    <COLUMN col_name="GovernmentForm" col_type="254" col_length="45" raw_length="45" /> 
                    <COLUMN col_name="HeadOfState" col_type="254" col_length="60" raw_length="60" /> 
                    <COLUMN col_name="Capital" col_type="3" col_length="11" raw_length="4" /> 
                    <COLUMN col_name="Code2" col_type="254" col_length="2" raw_length="2" /> 
                  </TABLE>
                </OP>
                </OP>
              </SEL>
            </OP>
          </JOIN>
        </OP>
      </PROJ>
    </OP>
  </RESULT>
</EXECUTION_SET>

第二个XML文件:

<EXECUTION_SET>
  <RESULT query_id="13" >
    <OP>
      <PROJ>
        <COLUMN col_name="Country.Code" col_type="254" col_length="3" />
        <OP>
          <SEL>
            <COND>
              <COND>
                <VALUE><VARIABLE>Country.Population</VARIABLE></VALUE>
              </COND>
              <BOP><![CDATA[>]]></BOP>
              <COND>
                <VALUE><CONSTANT>80000000</CONSTANT></VALUE>
              </COND>
            </COND>
            <OP>
            <OP>
              <TABLE name="Country" alias="Country" access_type="5" total_record_length="261">
                <COLUMN col_name="Code" col_type="254" col_length="3" raw_length="3" /> 
                <COLUMN col_name="Name" col_type="254" col_length="52" raw_length="52" /> 
                <COLUMN col_name="Continent" col_type="254" col_length="13" raw_length="1" /> 
                <COLUMN col_name="Region" col_type="254" col_length="26" raw_length="26" /> 
                <COLUMN col_name="SurfaceArea" col_type="4" col_length="10" raw_length="4" /> 
                <COLUMN col_name="IndepYear" col_type="2" col_length="6" raw_length="2" /> 
                <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
                <COLUMN col_name="LifeExpectancy" col_type="4" col_length="3" raw_length="4" /> 
                <COLUMN col_name="GNP" col_type="4" col_length="10" raw_length="4" /> 
                <COLUMN col_name="GNPOld" col_type="4" col_length="10" raw_length="4" /> 
                <COLUMN col_name="LocalName" col_type="254" col_length="45" raw_length="45" /> 
                <COLUMN col_name="GovernmentForm" col_type="254" col_length="45" raw_length="45" /> 
                <COLUMN col_name="HeadOfState" col_type="254" col_length="60" raw_length="60" /> 
                <COLUMN col_name="Capital" col_type="3" col_length="11" raw_length="4" /> 
                <COLUMN col_name="Code2" col_type="254" col_length="2" raw_length="2" /> 
              </TABLE>
            </OP>
            </OP>
          </SEL>
        </OP>
      </PROJ>
    </OP>
  </RESULT>
</EXECUTION_SET>

对于这两个XML文件，我想比较标记下的子部分是否相等。为此，我做了以下两个xpath查询:doc.select_nodes(std::string("//TABLE[@name='Country']/ancestor::SEL/COND").c_str());并将其写入变量pugi::xpath_node_set partialTree1和partialTree2中。

所以我得到两个xml文件的子部分。现在我想比较一下这两个部分。这应该是一种很有效的方法。

我有一个解决方案，但我不喜欢它，因为它需要太多的时间和空间。目前，我使用traverse函数来抛出子节，并将所有子节都写在字符串中。然后进行比较。但肯定有更好的办法。如果有人有什么建议就太好了。

Answer 1

作为查询的结果，您有一组来自不同文档的节点。每个节点都有一定数量的后代，为了比较两个节点，你必须比较它们所有的后代——如果你错过了一个，你就不知道这些树是否相等。

这表明比较节点的字符串转储的方法在时间方面是最优的复杂性。就空间而言，它不是最优的——就空间而言，最优算法会同步遍历两个树并直接比较值。像这样的代码应该可以工作:

template <typename It, typename Pred>
bool rangeEquals(It lb, It le, It rb, It re, Pred pred)
{
    It li = lb, ri = rb;
    for (; li != le && ri != re; ++li, ++ri)
        if (!pred(*li, *ri))
            return false;
    return li == le && ri == re;
}
bool attrEquals(pugi::xml_attribute la, pugi::xml_attribute ra)
{
    return
        strcmp(la.name(), ra.name()) == 0 &&
        strcmp(la.value(), ra.value()) == 0;
}
bool nodeEquals(pugi::xml_node ln, pugi::xml_node rn)
{
    return
        ln.type() == rn.type() &&
        strcmp(ln.name(), rn.name()) == 0 &&
        strcmp(ln.value(), rn.value()) == 0 &&
        rangeEquals(ln.attributes_begin(), ln.attributes_end(), rn.attributes_begin(), rn.attributes_end(), attrEquals) &&
        rangeEquals(ln.begin(), ln.end(), rn.begin(), rn.end(), nodeEquals);
}