假设我有两个 std::map
,如下:
map<int, double> A;
map<int, double> B;
我想要获取这两个地图的交集,形式如下:
map<int, pair<double,double> > C;
这里的键是A
和B
中都存在的值,并且该值是分别来自A
和B
的值对。
是否有一种使用标准库的简洁方法?
假设我有两个 std::map
,如下:
map<int, double> A;
map<int, double> B;
我想要获取这两个地图的交集,形式如下:
map<int, pair<double,double> > C;
这里的键是A
和B
中都存在的值,并且该值是分别来自A
和B
的值对。
是否有一种使用标准库的简洁方法?
#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)的。因为这个代码被模板化了,所以它可以处理任何具有相同键类型的两个映射。
operator==
):) - David Rodríguez - dribeasconst_iterators
缺少typename
。 - Georg Fritzsche我认为没有一个纯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;
}
operator<
而不是 operator==
。对于 int
键可能没有影响,但对于更复杂的内容可能会有所不同。 - Mark Ransom#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 ) );
}
}
}
find
调用来进行改进。Map是有序的,并且您可以同时迭代两个输入Map。每当左右迭代器值不同时,使两个中的最小值前进。当前的算法成本为O(N log M)
,而改进后的解决方案将是O( max(N,M) )
,其中N
和M
是两个输入Map的大小。无论如何都要+1,因为实际上提供了一个可行的解决方案 :) - David Rodríguez - dribeasfor
循环。 - T.E.D.copy_if
或现有的std::remove_copy_if
来使用执行find
的函数对象进行过滤,但这将无法提供第二个值以进行组合。可以尝试使用生成组合值的函数对象进行std::transform
,但由于该函数对象需要始终生成一个值并且不能进行过滤,因此也会失败。 - David Rodríguez - dribeasstd::set_difference
,仍然无法组合结果值,我现在已经没有更多的想法了。 - David Rodríguez - dribeasO(N)
时间内遍历,其中N
是元素数量。简单的证明是绘制一棵树,并在首先向下遍历然后向上返回时绘制每个链接。在树的遍历过程中,每条边恰好被遍历两次。 - David Rodríguez - dribeas编辑:由于我相信有一种更好的类似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 - dribeasstd::inserter
到std::set_difference
,您可以避免三个中间容器中的两个。无论如何,它都不像简单的双重循环那样干净。重点应该放在可维护性上,而这里的代码(这是主观的)比直接实现更难以维护。 - David Rodríguez - dribeasmap
已排序这一事实。(我竟然忽略了这一点,真是惭愧。)感谢 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;
}
}
}
好的,准备好动手了吗 :)
我将使用 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中找到 :)
#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;
}
大约一年后……但是没关系 :)
这个是针对一个 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生成一个插入迭代器
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;
}