C++ Set-Theoretic Operations on Virtual Containers 
by Gregory Begelman, Lev Finkelstein, Evgeniy Gabrilovich

Listing One
void temp_intersection() {
   vector<int> vec1, vec2, temp_result;
   ... // prepare input sequences in 'vec1' and 'vec2'
   set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), 
    back_inserter(temp_result)); // build the result in a temporary container
   for (int i = 0; i < temp_result.size(); ++i) {
      // do something
   }
}

Listing Two
class callback {
      void do_something(int v) {
         // do something
      }
public:
      callback &operator=(int v) { do_something(v); return *this;}
      callback &operator*() { return *this; }
      // op++ for output iterators has a dummy implementation
      callback &operator++() { return *this; }
      callback &operator++(int) { return *this; }
};
void callback_intersection() {
   vector<int> vec1, vec2;
   ...
   set_intersection(vec1.begin(), vec1.end(), vec2.begin(), 
                                              vec2.end(), callback());
}

Listing Three
void online_intersection() {
   vector<int> vec1, vec2;
   ...
   typedef set_intersection_online<int, 
                                   vector<int>::iterator> IntersectionOnline;
   IntersectionOnline res(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
   for (IntersectionOnline::const_iterator iter = 
                                     res.begin(); iter != res.end(); ++iter) {
      // do something
   }
}

Listing Four
template<class _T, class _Iter1, 
                   class _Iter2, class _StrictWeakOrdering, class _Tag>
class _const_set_online_iterator {
public:
   typedef _T value_type;     
private:
   // Iterators to the current and last elements of the input ranges
   _Iter1 _current1, _last1;
   _Iter2 _current2, _last2;
   // Possible outcomes of comparing the current elements in the input ranges:
   // FIRST      : _StrictWeakOrdering(*current1, *current2) == true
   //                   or the second range has been exhausted              
   // SECOND : _StrictWeakOrdering(*current2, *current1) == true
   //                   or the first range has been exhausted
   // EQUAL    : neither the first nor the second condition is true
   enum compare_state { FIRST, SECOND, EQUAL };

   // The comparison state is used in iterator increment and dereference
   compare_state _compare;
      
   compare_state get_compare_state() const {
      if (_current1 == _last1) return SECOND;
      if (_current2 == _last2) return FIRST;
      if (_StrictWeakOrdering()(*_current1, *_current2)) return FIRST;
      if (_StrictWeakOrdering()(*_current2, *_current1)) return SECOND;
      return EQUAL;
   }

   // These functions need to be defined with the corresponding tag parameter:
   // inline _const_set_online_iterator& _pre_increment(const _Tag&);
   // inline void _find_next(const _Tag&);
   // inline const value_type _dereference(const _Tag&) const;
   //
   // Since MS VC++ does not support partial template specialization we 
   // declare these functions for all possible tags. The implementation, 
   // however, is provided only for the pertinent tag.
   INSTANTIATE_FOR_ALL_OPERATIONS(DECLARE_PRE_INCREMENT)
   INSTANTIATE_FOR_ALL_OPERATIONS(DECLARE_DEREFERENCE)
   INSTANTIATE_FOR_ALL_OPERATIONS(DECLARE_FIND_NEXT)
   
   void find_next() { 
      _find_next(_Tag()); 
   }
public:
   // The constructor takes two boundary elements for each of the input ranges
   _const_set_online_iterator(const _Iter1& current1, const _Iter1& last1,
                   const _Iter2& current2, const _Iter2& last2) :
      _current1(current1), _last1(last1), _current2(current2), _last2(last2)
   {
      _compare = get_compare_state(); 
                                // update compare state for current elements
      find_next();  // find the next element for which the predicate is true
   }
   // Basic operators
   bool operator==(const _const_set_online_iterator& rhs) const {
      return ((_current1 == rhs._current1) && (_current2 == rhs._current2));
   }
   bool operator!=(const _const_set_online_iterator& rhs) const {
      return !operator==(rhs);
   }
   _const_set_online_iterator& operator++() {
      return _pre_increment(_Tag());
   }
   _const_set_online_iterator& operator++(int) {
      _const_set_online_iterator temp = *this;
      ++(*this);
      return temp;
   }
   const value_type operator*() const { 
      return _dereference(_Tag()); 
   }
};

Listing Five
struct union_tag {};
struct intersection_tag {};
struct difference_tag {};
struct symmetric_difference_tag {};
struct merge_tag {};

// Declaration of the pre-increment operator
#define DECLARE_PRE_INCREMENT(tag)               \
inline _const_set_online_iterator& _pre_increment(const tag&);

// Declaration of the dereference operator
#define DECLARE_DEREFERENCE(tag)                 \
inline const value_type &_dereference(const tag&) const;

// Declaration of 'find_next' function
#define DECLARE_FIND_NEXT(tag)                    \ 
inline void _find_next(const tag&);

#define INSTANTIATE_FOR_ALL_OPERATIONS(MACRO)     \
MACRO(union_tag)                                  \
MACRO(intersection_tag)                           \
MACRO(difference_tag)                             \
MACRO(symmetric_difference_tag)                   \
MACRO(merge_tag)


Listing Six
template<class _T, class _Iter1, class _Iter2, 
                                 class _StrictWeakOrdering, class _Tag>
class _set_online {
   _Iter1 _first1, _last1;
   _Iter2 _first2, _last2;
public:
   typedef _T value_type;
   typedef _const_set_online_iterator<_T, _Iter1, 
                                    _Iter2, _StrictWeakOrdering, _Tag> 
                _const_iterator;
   _set_online(_Iter1 first1, _Iter1 last1, _Iter2 first2, _Iter2 last2) :
      _first1(first1), _last1(last1), _first2(first2), _last2(last2) {}
   _const_iterator begin() const { return _const_iterator(_first1, 
                                               _last1, _first2, _last2); }
   _const_iterator end() const { return _const_iterator(_last1, 
                                               _last1, _last2, _last2); }
};


Listing Seven
INSTANTIATE_SET_ONLINE(set_intersection_online, intersection_tag)

INSTANTIATE_PRE_INCREMENT(intersection_tag)
{
   ++_current1;
   ++_current2;
   find_next();
   return *this;
}
INSTANTIATE_DEREFERENCE(intersection_tag)
{
   return *_current1;
}
INSTANTIATE_FIND_NEXT(intersection_tag)
{
   if (_current1 == _last1 || _current2 == _last2) {
      _current1 = _last1;
      _current2 = _last2;
      return;
   }
   while (_StrictWeakOrdering()(*_current1, *_current2) || 
    _StrictWeakOrdering()(*_current2, *_current1)) 
   {
      while ((_current1 != _last1) && 
        _StrictWeakOrdering()(*_current1, *_current2))
         ++_current1;
            
      if (_current1 == _last1) {
         _current2 = _last2;
         return;
      }
      while ((_current2 != _last2) && 
        _StrictWeakOrdering()(*_current2, *_current1))
         ++_current2;
      if (_current2 == _last2) {
         _current1 = _last1;
         return;
      }
   }
}

Listing Eight
// Auxiliary macro for instantiating "virtual containers"
#define INSTANTIATE_SET_ONLINE(classname, tag)          \
template<class _T,                                      \
         class _Iter1,                                  \
         class _Iter2 = _Iter1,                         \
         class _StrictWeakOrdering = std::less<_T> >    \
class classname :                                       \
   public _set_online<_T, _Iter1, _Iter2, _StrictWeakOrdering, tag>     \
{                                                       \
public:                                                 \
   typedef _T value_type;                               \
   classname (_Iter1 first1, _Iter1 last1, _Iter2 first2, _Iter2 last2) :  \
      _set_online<_T, _Iter1, _Iter2, _StrictWeakOrdering, tag> \
   (first1, last1, first2, last2)                       \
   {}                                                   \
};
// Auxiliary macro for instantiating the pre-increment operator
#define INSTANTIATE_PRE_INCREMENT(tag)                  \
template<class _T, class _Iter1, class _Iter2, class _StrictWeakOrdering,   \
               class _Tag>                              \
inline _const_set_online_iterator<_T, _Iter1, _Iter2,   \
                                         _StrictWeakOrdering, _Tag>&      \
   _const_set_online_iterator<_T, _Iter1, _Iter2,       \
                                       _StrictWeakOrdering, _Tag>::       \
_pre_increment(const tag&)
// Auxiliary macro for instantiating the dereference operator
#define INSTANTIATE_DEREFERENCE(tag)                    \
template<class _T, class _Iter1, class _Iter2, class _StrictWeakOrdering,  \
              class _Tag>                               \
inline const _const_set_online_iterator<_T, _Iter1, _Iter2,                \
                                 _StrictWeakOrdering, _Tag>::value_type    \
   &_const_set_online_iterator<_T, _Iter1, _Iter2,       \
                       _StrictWeakOrdering, _Tag>::      \
_dereference(const tag&) const

// Auxiliary macro for instantiating the "find_next" function
#define INSTANTIATE_FIND_NEXT(tag)                      \
template<class _T, class _Iter1, class _Iter2, class _StrictWeakOrdering,  \
               class _Tag>                              \
inline void _const_set_online_iterator<_T, _Iter1, _Iter2,              \
                                     _StrictWeakOrdering, _Tag>::        \
_find_next(const tag&)





1

