container_utils.h

Go to the documentation of this file.

/*******************************************************************\
 
Module: Container utilities
 
Author: Diffblue Ltd.
 
\*******************************************************************/
 
#ifndef CPROVER_UTIL_CONTAINER_UTILS_H
#define CPROVER_UTIL_CONTAINER_UTILS_H
 
#include <set>

template <class T, class Compare, class Alloc>
bool util_inplace_set_union(
  std::set<T, Compare, Alloc> &target,
  const std::set<T, Compare, Alloc> &source)
{
  bool changed = false;
  typename std::set<T, Compare, Alloc>::iterator it = target.begin();
 
  for(const auto &s : source)
  {
    while(it != target.end() && Compare()(*it, s))
    {
      ++it;
    }
 
    if(it == target.end() || Compare()(s, *it))
    {
      // Insertion hint should point at element that will follow the new element
      target.insert(it, s);
      changed = true;
    }
    else if(it != target.end())
    {
      ++it;
    }
  }
 
  return changed;
}
 
#endif // CPROVER_UTIL_CONTAINER_UTILS_H