倒排列表求交集算法 包括baeza yates的交集算法

#ifndef __INTERSECT_HPP__
#define __INTERSECT_HPP__

#include "probe.hpp"

namespace themas {

/*
* like stl's set_intersect
*/
template<class InputIterator, class OutputIterator>
void linear_intersect(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator out)
{
if ( (end2 - begin2) > (end1 - begin1) )
{
// why in the world would i do this?
// hmmmmmmm.......... !
std::swap(begin1, begin2);
std::swap(end1, end2);
}
while (begin1 != end1 && begin2 != end2)
{
if (*begin1 < *begin2)
++begin1;
else if (*begin2 < *begin1)
++begin2;
else
{
*out++ = *begin1;
++begin1;
++begin2;
}
}
}

/*
* this time with a comparator!
*/
template<class InputIterator, class OutputIterator, class Comparator >
void linear_intersect(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator out, Comparator cmp)
{
if ( (end2 - begin2) > (end1 - begin1) )
{
// why in the world would i do this?
// hmmmmmmm.......... !
std::swap(begin1, begin2);
std::swap(end1, end2);
}
while (begin1 != end1 && begin2 != end2)
{
if (cmp( *begin1, *begin2 ) )
++begin1;
else if ( cmp(*begin2, *begin1) )
++begin2;
else
{
*out++ = *begin1;
++begin1;
++begin2;
}
}
}

/*
* baeza_intersect
*/
template< template <class, class> class Probe,
class RandomAccessIterator, class OutputIterator>
void baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1,
RandomAccessIterator begin2, RandomAccessIterator end2,
OutputIterator out)
{
RandomAccessIterator probe1, probe2;

if ( (end1 - begin1) < ( end2 - begin2 ) )
{
if ( begin1 == end1 )
return;
probe1 = begin1 + ( ( end1 - begin1 ) >> 1 );
probe2 = lower_bound< Probe >( begin2, end2, *probe1 );
baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out); // intersect left
if (! (probe2 == end2 || *probe1 < *probe2 ))
*out++ = *probe2++;
baeza_intersect< Probe >(++probe1, end1, probe2, end2, out); // intersect right
}
else
{
if ( begin2 == end2 )
return;
probe2 = begin2 + ( ( end2 - begin2 ) >> 1 );
probe1 = lower_bound< Probe >( begin1, end1, *probe2 );
baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out); // intersect left
if (! (probe1 == end1 || *probe2 < *probe1 ))
*out++ = *probe1++;
baeza_intersect< Probe >(probe1, end1, ++probe2, end2, out); // intersect right
}
}

/*
* with a comparator
*/
template< template <class, class> class Probe,
class RandomAccessIterator, class OutputIterator, class Comparator >
void baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1,
RandomAccessIterator begin2, RandomAccessIterator end2,
OutputIterator out, Comparator cmp)
{
RandomAccessIterator probe1, probe2;

if ( (end1 - begin1) < ( end2 - begin2 ) )
{
if ( begin1 == end1 )
return;
probe1 = begin1 + ( ( end1 - begin1 ) >> 1 );
probe2 = lower_bound< Probe >( begin2, end2, *probe1, cmp );
baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out, cmp); // intersect left
if (! (probe2 == end2 || cmp( *probe1, *probe2 ) ))
*out++ = *probe2++;
baeza_intersect< Probe >(++probe1, end1, probe2, end2, out, cmp); // intersect right
}
else
{
if ( begin2 == end2 )
return;
probe2 = begin2 + ( ( end2 - begin2 ) >> 1 );
probe1 = lower_bound< Probe >( begin1, end1, *probe2, cmp );
baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out, cmp); // intersect left
if (! (probe1 == end1 || cmp( *probe2, *probe1 ) ))
*out++ = *probe1++;
baeza_intersect< Probe >(probe1, end1, ++probe2, end2, out, cmp); // intersect right
}
}

} // themas

#endif // __INTERSECT_HPP__

#include <iostream>
#include <vector>
#include <set>
#include <ctime>

#include <boost/random/mersenne_twister.hpp>

#include "intersect.hpp"

using namespace themas;

int main(int argc, char * argv[])
{
std::set<int> nums1, nums2;
std::vector<int> result1, result2, result3;

boost::mt19937 rng(time(NULL));

for ( unsigned int i = rng() % 16384; i != 0; --i )
nums1.insert(rng());
for ( unsigned int i = rng() % 16384; i != 0; --i )
nums2.insert(rng());
for ( unsigned int i = rng() % 16384; i != 0; --i )
{
unsigned int j = rng();
nums1.insert(j);
nums2.insert(j);
}
std::vector<int> v1(nums1.begin(), nums1.end()), v2(nums2.begin(), nums2.end());

linear_intersect(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result1));
baeza_intersect < binary_probe > (v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result2));
baeza_intersect < interpolation_probe > (v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result3));

if (result1 != result2 || result1 != result3)
std::cout << "FAIL!" << std::endl;
else
std::cout << "PASS!" << std::endl;
}

|
4月前
|

50 0
|
4月前
|

【算法训练-回溯算法 一】【排列问题】全排列、全排列II
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
77 0
|
11月前
|

C++二分算法习题：判断是否是完全平方数[容易]和排列箱子[容易]
C++二分算法习题：判断是否是完全平方数[容易]和排列箱子[容易]
57 1
|
11月前
|

49 0
|
11月前
|

33 0
|
4月前
|

42 2
|
1月前
|

LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
43 0
|
3月前
|

【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
21 1
|
3月前
|

33 0
|
3月前
|

【经典LeetCode算法题目专栏分类】【第8期】滑动窗口：最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口：最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
27 0