logo标签列表

两个`std::map`的交集

c++dictionarystdstdmapc++-standard-library
16

假设我有两个 std::map，如下：

map<int, double> A;
map<int, double> B;

我想要获取这两个地图的交集，形式如下：

map<int, pair<double,double> > C;

这里的键是A和B中都存在的值，并且该值是分别来自A和B的值对。

是否有一种使用标准库的简洁方法？

如果您可以假设A和B中的所有键都相同，那么可以使用STL的std::transform完成这个任务。我猜... transform函数是make_pair。 - Muxecoid
9个回答
17
#include <map>
#include <utility>
template <typename KeyType, typename LeftValue, typename RightValue>
std::map<KeyType, std::pair<LeftValue, RightValue>>
IntersectMaps(const std::map<KeyType, LeftValue>& left, 
              const std::map<KeyType, RightValue>& right) {
    std::map<KeyType, std::pair<LeftValue, RightValue>> result;
    typename std::map<KeyType, LeftValue>::const_iterator il  = left.begin();
    typename std::map<KeyType, RightValue>::const_iterator ir = right.begin();
    while (il != left.end() && ir != right.end()) {
        if (il->first < ir->first)
            ++il;
        else if (ir->first < il->first)
            ++ir;
        else {
            result.insert(std::make_pair(il->first, std::make_pair(il->second, ir->second)));
            ++il;
            ++ir;
        }
    }
    return result;
}

虽然我还没有测试过这个代码，甚至也没有编译过它…但是它应该是O(n)的。因为这个代码被模板化了，所以它可以处理任何具有相同键类型的两个映射。

1
+1：对于泛化为“LeftValue”和“RightValue”，尽管在当前问题定义中它们相同。 - Arun
+1，因为我没有强制要求额外的要求（operator==）:) - David Rodríguez - dribeas
1
const_iterators缺少typename。 - Georg Fritzsche
很抱歉打破好事，但我看不出这个算法怎么能正确地工作。迭代器会向前移动直到找到匹配的键，同时跳过潜在的匹配项。依我看，这个算法给出了任意结果，并且不能输出所有键匹配的元组。 - SkyWalker
整个答案中我没有看到任何地方说地图需要按键排序...任何复制粘贴的人都可能会遇到麻烦。 - SkyWalker
显示剩余2条评论
11

我认为没有一个纯STL的方法能够实现你想要的功能。手动实现应该不会太复杂。

请注意，std::set_intersection不是解决方案。主要原因在于它比较了解除引用的迭代器，然后将其中一个元素复制到输出迭代器。

虽然完全解除引用迭代器的比较包括相关值（我理解您不希望考虑作为键的一部分），可以通过提供只测试键（std::pair<const Key, Value>::first）的比较函数来解决，但算法仅复制两个值中的一个而不组成解决方案的问题无法从外部解决。

编辑：函数的简单线性时间实现：

请注意，正如@Mark Ransom所评论的那样，此解决方案增加了一个额外的要求：键必须可比较相等。这不是他的解决方案here，或者类似于@Matthiew M的答案here的一个问题。对于这个修复，修改此算法将是可耻的 :)

@Mark实现的另一个巨大优势是，它可以从存储不同值类型的映射中组合，只要键相同即可（这似乎是一个显而易见的要求）。我希望我能在那里多次投票..

template <typename Key, typename Value>
std::map<Key,std::pair<Value,Value> > 
merge_maps( std::map<Key,Value> const & lhs, std::map<Key,Value> const & rhs )
{
    typedef typename std::map<Key,Value>::const_iterator input_iterator;
    std::map<Key, std::pair<Value,Value> > result;
    for ( input_iterator it1 = lhs.begin(), it2 = rhs.begin(),
                         end1 = lhs.end(), end2 = rhs.end();
            it1 != end1 && it2 != end2; )
    {
        if ( it1->first == it2->first )
        {
            result[it1->first] = std::make_pair( it1->second, it2->second );
            ++it1; ++it2;
        }
        else
        {
            if ( it1->first < it2->first )
                ++it1;
            else
                ++it2;
        }
    }
    return result;
}
+1：比我的解决方案更优雅且不那么啰嗦。而且该函数是模板化的。 - Arun
你的代码与我的非常相似，而且你似乎比我快了2分钟。它看起来格式更好。我的代码有一个简单的优点，它只依赖于 operator< 而不是 operator==。对于 int 键可能没有影响，但对于更复杂的内容可能会有所不同。 - Mark Ransom
@Mark Ransom：你的解决方案的另一个巨大优势是它比我的更通用，允许从具有不相关值类型的映射中合并 / 组合。 - David Rodríguez - dribeas
1
StackOverflow的核心在于提供最佳答案。如果你根据我的概念修改了你的答案，我一点也不会介意 - 实际上我一直在等待这样做，这样我就可以放心地给你一个+1。无论如何，我现在会这样做，只是为了满足自己的虚荣心。 - Mark Ransom
7
#include <map>
using namespace std;
typedef int KeyType;
typedef double ValueType;
typedef map< KeyType, ValueType > MyMap;
typedef MyMap::iterator MyMapIter;
typedef MyMap::const_iterator MyMapConstIter;
typedef pair< ValueType, ValueType > ValueTypePair;
typedef map< KeyType, ValueTypePair > MyMapIntersection;

int main() {
    MyMap A;
    MyMap B;
    MyMapIntersection C;

    // fill up A, B

    for( MyMapConstIter cit = A.begin(); cit != A.end(); ++cit ) {
        const KeyType x = cit->first;
        MyMapConstIter found = B.find( x );
        if( found != B.end() ) {
            ValueTypePair valuePair =
                ValueTypePair( cit->second, found->second );
            C.insert( pair< KeyType, ValueTypePair>( x, valuePair ) );
        }
    }
}
2
该算法可以通过避免find调用来进行改进。Map是有序的，并且您可以同时迭代两个输入Map。每当左右迭代器值不同时，使两个中的最小值前进。当前的算法成本为O(N log M)，而改进后的解决方案将是O( max(N,M) )，其中N和M是两个输入Map的大小。无论如何都要+1，因为实际上提供了一个可行的解决方案 :) - David Rodríguez - dribeas
1
不用太费力地查看它，我认为在<algorithm>中应该有一些东西可以让你摆脱for循环。 - T.E.D.
@T.E.D.：我认为没有。显然，代码正在迭代单个容器，但事实是迭代同时发生在两个不同的容器中。按照当前的实现方式，似乎可以使用缺失的copy_if或现有的std::remove_copy_if来使用执行find的函数对象进行过滤，但这将无法提供第二个值以进行组合。可以尝试使用生成组合值的函数对象进行std::transform，但由于该函数对象需要始终生成一个值并且不能进行过滤，因此也会失败。 - David Rodríguez - dribeas
...再次使用std::set_difference，仍然无法组合结果值，我现在已经没有更多的想法了。 - David Rodríguez - dribeas
@Niki Yoshiuchi：错误。每个节点都有指向其父节点的指针的二叉树可以在O(N)时间内遍历，其中N是元素数量。简单的证明是绘制一棵树，并在首先向下遍历然后向上返回时绘制每个链接。在树的遍历过程中，每条边恰好被遍历两次。 - David Rodríguez - dribeas
显示剩余2条评论
1

编辑：由于我相信有一种更好的类似STL的解决方案，所以我找到了一种。它与原来的不同，因此我将其作为单独的答案发布。

这里有一些技巧。首先，您想使用set_intersection，但您有两个映射。解决方案是自定义比较器和std::transform算法。比我更熟悉标准库的人可能可以优化这个过程，但它确实有效。请注意，boost::bind可以让您减少使其工作的愚蠢助手函数。

#include <algorithm>
#include <map>
#include <set>

bool myLess(const std::map<int,double>::value_type &v1,
            const std::map<int,double>::value_type &v2) {
    return v1.first < v2.first;
}
int getKey(const std::map<int,double>::value_type &v) {
    return v.first;
}

struct functor {
    std::map<int,double> &m1,&m2;
    functor(std::map<int,double> &im1, std::map<int,double> &im2) : m1(im1), m2(im2) {}
    std::pair<int,std::pair<double,double> > operator() (int x) {
        return std::make_pair(x, std::make_pair(m1[x],m2[x]));
    }
};

int main() {
    std::map<int,double> m1, m2;
    m1[0]=0;m1[1]=1; m1[2]=2; m1[3]=3;
            m2[1]=11;m2[2]=12;m2[3]=13;m2[4]=14;

    std::set<int> keys1,keys2,keys;
    //Extract the keys from each map with a transform
    std::transform(m1.begin(),m1.end(),std::inserter(keys1,keys1.begin()),getKey);
    std::transform(m2.begin(),m2.end(),std::inserter(keys2,keys2.begin()),getKey);
    //set_intersection to get the common keys
    std::set_intersection(keys1.begin(),keys1.end(),keys2.begin(),keys2.end(),
            std::inserter(keys,keys.begin()));

    std::map<int, std::pair<double,double> > result;
    functor f(m1,m2);  //stash our maps into the functor for later use
    //transform from the key list to the double-map
    std::transform(keys.begin(),keys.end(),std::inserter(result,result.begin()),f);
    return 0;
}

像C++的大部分内容一样，最终使用起来非常流畅（在main()中的所有内容），但设置过程比我们实际想要的更冗长。

出于两个不同的原因，我并不十分喜欢这个提议的解决方案。首先，在main中找不到代码变得很“光滑”，我发现整个实现比一个简单的直接实现要不可读得多。该解决方案需要生成两个带有键的集合以及一个带有交集的第三个集合。虽然渐近复杂度是线性的，但内存成本（和动态分配的数量）已经翻了三倍。通过向std::set_intersection提供比较函数对象来避免第一个transform，可以改进它。 - David Rodríguez - dribeas
通过添加一个迭代器适配器而不是使用std::inserter到std::set_difference，您可以避免三个中间容器中的两个。无论如何，它都不像简单的双重循环那样干净。重点应该放在可维护性上，而这里的代码（这是主观的）比直接实现更难以维护。 - David Rodríguez - dribeas
我认为你无法避免第一个转换，但欢迎你尝试。问题在于set_intersection的输入和输出类型被绑定在相同的模板类型中。 - jkerian
迭代器适配器极大地简化了这段代码，但这并不完全（尽管有些人可能会争辩）是STL的实现。 - jkerian
1
一种更好的解决方案是基于 map 已排序这一事实。（我竟然忽略了这一点，真是惭愧。）感谢 David Rodríguez - dribeas 的建议。
#include <map>
using namespace std;
typedef int KeyType;
typedef double ValueType;

typedef map< KeyType, ValueType > MyMap;
typedef MyMap::iterator MyMapIter;
typedef MyMap::const_iterator MyMapConstIter;

typedef pair< ValueType, ValueType > ValueTypePair;

typedef map< KeyType, ValueTypePair > MyMapIntersection;


void constructInsert( MyMapIntersection & c, MyMapConstIter const & acit,
    MyMapConstIter const & bcit ) {

    ValueTypePair valuePair = ValueTypePair( acit->second, bcit->second );

    c.insert( pair< KeyType, ValueTypePair>( acit->first, valuePair ) );
}


int main() {

    MyMap A;
    MyMap B;
    MyMapIntersection C;

    // fill up A, B

    MyMapConstIter acit, bcit;
    for( acit = A.begin(), bcit = B.begin();
        (acit != A.end()) && (bcit != B.end()); /* Inside loop */ ) {

        const KeyType aKey = acit->first;
        const KeyType bKey = bcit->first;

        if( aKey < bKey ) {

            ++acit;
        }
        else if( aKey == bKey ) {

            constructInsert( C, acit, bcit );

            ++acit;
            ++bcit;
        }
        else {

            ++bcit;
        }
    }

}
1

好的，准备好动手了吗 :)

我将使用 std::mismatch 和 std::transform

首先，一些类型：

typedef std::map<int, double> input_map;
typedef input_map::const_reference const_reference;
typedef input_map::const_iterator const_iterator;
typedef std::pair<const_iterator,const_iterator> const_pair;

typedef std::map<int, std::pair<double,double> > result_map;

然后是谓词

bool less(const_reference lhs, const_reference rhs)
{
  return lhs.first < rhs.first;
}

result_map::value_type pack(const_reference lhs, const_reference rhs)
{
  assert(lhs.first == rhs.first);
  return std::make_pair(lhs.first, std::make_pair(lhs.second, rhs.second));
}

现在主程序：

result_map func(input_map const& m1, input_map const& m2)
{
  if (m1.empty() || m2.empty()) { return result_map(); }

  // mismatch unfortunately only checks one range
  // god do I hate those algorithms sometimes...
  if (*(--m1.end()) < *(--m2.end()) { return func(m2, m1); }

  const_pair current = std::make_pair(m1.begin(), m2.begin()),
             end = std::make_pair(m1.end(), m2.end());

  result_map result;

  // Infamous middle loop, the check is middle-way in the loop
  while(true)
  {
    const_pair next = std::mismatch(p.first, end.first, p.second, less);

    std::transform(current.first, next.first, current.second,
      std::inserter(result, result.begin()), pack);

    // If any of the iterators reached the end, then the loop will stop
    if (next.first == end.first || next.second == end.second) { break; }

    // Advance the lesser "next"
    if (less(*next.first, *next.second)) { ++next.first; }
    else                                 { ++next.second; }

    current = next;
  }

  return result;
}

我觉得这个解决方案相当优雅...尽管设置部分有些棘手，因为我们需要确保第一个范围由于而比第二个更快地结束...

请注意，前进部分真的很愚蠢，我们可以在这里专门循环，直到*next.first.key == * next.second.key，但这会使循环复杂化。

我真的不认为这比手工制作的循环更好...考虑一下：

result_map func2(input_map const& lhs, input_map const& rhs)
{
  result_map result;

  for (const_iterator lit = lhs.begin(), lend = lhs.end(),
                      rit = rhs.begin(), rend = rhs.end();
       lit != lend && rit != rend;)
  {
    if (lit->first < rit->first)      { ++lit; }
    else if (rit->first < lit->first) { ++rit; }
    else
    {
      result[lit->first] = std::make_pair(lit->second, rit->second);
      ++lit, ++rit;
    }
  }

  return result;
}

这样更加紧凑，可能更有效率...有时你需要的函数不够通用，不能在STL中找到 :)

1
以下是我之前答案的简化版，主要利用了set_intersection可以与映射作为输入一起使用的事实，但前提是你必须将输出设置为std::pairs的集合。结果还将中间值削减为单个“公共键”列表。
#include <algorithm>
#include <map>
#include <set>

struct cK { //This function object does double duty, the two argument version is for
            //the set_intersection, the one argument version is for the transform
    std::map<int,double> &m1,&m2;
    cK(std::map<int,double> &im1, std::map<int,double> &im2) : m1(im1), m2(im2)
    std::pair<int,std::pair<double,double> > operator() (std::pair<int,double> v
        return std::make_pair(v.first, std::make_pair(m1[v.first],m2[v.first]));
    }
    bool operator() (std::pair<int,double> v1, std::pair<int,double> v2) {
        return v1.first < v2.first;
    }
};

int main() {
    std::map<int,double> m1, m2;
    m1[0]=0;m1[1]=1; m1[2]=2; m1[3]=3;
            m2[1]=11;m2[2]=12;m2[3]=13;m2[4]=14;

    // Get the subset of map1 that has elements in map2
    std::set<std::pair<int,double> > sIntersection;
    cK compareKeys(m1,m2);
    std::set_intersection(m1.begin(),m1.end(),m2.begin(),m2.end(),
            std::inserter(sIntersection,sIntersection.begin()),compareKeys);

    // Use a custom transform to produce an output set
    std::map<int, std::pair<double,double> > result;
    std::transform(sIntersection.begin(),sIntersection.end(),
            std::inserter(result,result.begin()), compareKeys);
    return 0;
}
0

大约一年后……但是没关系 :)

这个是针对一个 set 容器的，不过你可以很容易地将它改成使用 map：

template <class InputIterator, class OutputIterator>
OutputIterator intersect(InputIterator lf, InputIterator ll, 
                         InputIterator rf, InputIterator rl, 
                         OutputIterator result)
{
    while(lf != ll && rf != rl)
    {
        if(*lf < *rf)
            ++lf;
        else if(*lf > *rf)
            ++rf;
        else
        {
            *result = *lf;
            ++lf;
            ++rf;
        }
    }
    return result;
}

使用方法：

intersect(set1.begin(), set1.end(), 
          set2.begin(), set2.end(), 
          inserter(output_container, output_container.begin()));

set1和set2都是集合容器，而output_container可以是set、list、array等。

inserter生成一个插入迭代器

0
template<typename K, typename V>
std::map<K, V> UnionMaps(const std::map<K, V> & left, const std::map<K, V> & right)
{
    std::map<K, V > result;
    typename std::map<K, V>::const_iterator il = left.begin();
    typename std::map<K, V>::const_iterator ir = right.begin();
    while (il != left.end() && ir != right.end())
    {
        if ((il->first < ir->first)){
            result.insert(make_pair(il->first, il->second));
            ++il;
        }else if ((ir->first < il->first)){
            result.insert(make_pair(ir->first, ir->second));
            ++ir;
        }else{
            result.insert(make_pair(il->first, il->second+ir->second));//add 
            ++il;
            ++ir;
        }
    }
    while (il != left.end() ){
        result.insert(make_pair(il->first, il->second));
        il++;
    }
    while (ir != right.end() ){
        result.insert(make_pair(ir->first, ir->second));
        ir++;
    }
    return result;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接