Container for Sets of Integers

Question

I implemented an unordered_set like container for storing small sets of unsigned integers. It uses a trivial hash table for lookups and an unordered array for quickly iterating over small sets.

I'm looking for suggestions on best practices and correctness.

#pragma once
#include <array>
#include <random>
#include <bitset>

// T - Type of integer.
// N - Number of integers in the set from 0 to N-1
template<typename T,T N> class integer_set
{
private:
  static constexpr T NOT_IN_SET = ~static_cast<T>(0);
  static const T MIN_SIZE_TO_SEARCH_INDEX;
public:
  class iterator
  {
  public:
    iterator(const iterator& it) = default;
    iterator& operator=(const iterator& it) = default;
    iterator();
    iterator(const T* element);
    bool operator==(const iterator& it) const;
    bool operator!=(const iterator& it) const;
    bool operator<(const iterator& it) const;
    bool operator>(const iterator& it) const;
    bool operator<=(const iterator& it) const;
    bool operator>=(const iterator& it) const;
    T operator*() const;
    T operator[](T i) const;
    iterator& operator++();
    iterator operator++(int);
    iterator& operator--();
    iterator operator--(int);
    iterator operator+(T i) const;
    iterator operator-(T i) const;
    iterator& operator+=(T i);
    iterator& operator-=(T i);
  private:
    const T* m_element;
  };
public:
  // The following are undefined if the set is empty:
  //   front()
  //   back()
  //   operator[]()
  //   min()
  //   max()
  //   random()
  integer_set();
  integer_set(const integer_set& set);
  integer_set& operator=(const integer_set& set);
  bool operator==(const integer_set& set) const;
  bool operator!=(const integer_set& set) const;
  bool operator<=(const integer_set& set) const;
  bool operator>=(const integer_set& set) const;
  bool operator<(const integer_set& set) const;
  bool operator>(const integer_set& set) const;
  T front() const;
  T back() const;
  iterator begin() const;
  iterator end() const;
  iterator find(T v) const;
  T operator[](T i) const;
  T min() const;
  T max() const;
  template<class URNG> T random(URNG& gen) const;
  T size() const;
  bool empty() const;
  bool contains(T v) const;
  void clear();
  void insert(T v);
  void insert(const integer_set& set);
  void erase(T v);
  void erase(const integer_set& set);
public:
  static integer_set union_(const integer_set& set1,const integer_set& set2);
  static integer_set intersection(const integer_set& set1,const integer_set& set2);
  static bool union_empty(const integer_set& set1,const integer_set& set2);
  static bool intersection_empty(const integer_set& set1,const integer_set& set2);
private:
  // Find the smallest size where searching the index has a probability >= 0.5 of requiring fewer operations than searching the list.
  static T min_size_to_search_index();
  // Probability that we will find at least one element in the set after picking size elements at random.
  static double get_probability(T size);
private:
  // m_index[element] is the index of that element in m_list or NOT_IN_SET. For checking if element is in set.
  std::array<T,N> m_index;
  // Unordered list of elements. For iterating over set.
  std::array<T,N> m_list;
  // Number of elements in set.
  T m_size;
};

namespace std
{
  template<typename T,T N> struct hash<integer_set<T,N>>
  {
    typedef integer_set<T,N> argument_type;
    typedef std::size_t result_type;
    result_type operator()(const argument_type& set) const
    {
      std::bitset<N> bits;
      for(T v : set)
        bits.set(v);
      return std::hash<std::bitset<N>>()(bits);
    }
  };
}

template<typename T,T N> constexpr T integer_set<T,N>::NOT_IN_SET;
template<typename T,T N> const T integer_set<T,N>::MIN_SIZE_TO_SEARCH_INDEX = {min_size_to_search_index()};

////////////////////////////////////////////////
// integer_set

template<typename T,T N> integer_set<T,N>::integer_set()
  :m_size{0}
{
  m_index.fill(NOT_IN_SET);
  static_assert(std::numeric_limits<T>::is_integer,"T must be an integer.");
  static_assert(std::is_unsigned<T>::value,"T must be unsigned.");
  static_assert(N<NOT_IN_SET,"N is too large.");
}

template<typename T,T N> integer_set<T,N>::integer_set(const integer_set& set)
  :m_index(set.m_index),m_size{set.m_size}
{
  for(T i=0; i<m_size; ++i)
    m_list[i] = set.m_list[i];
}

template<typename T,T N> integer_set<T,N>& integer_set<T,N>::operator=(const integer_set& set)
{
  m_size = set.m_size;
  m_index = set.m_index;
  for(T i=0; i<m_size; ++i)
    m_list[i] = set.m_list[i];
  return *this;
}

template<typename T,T N> bool integer_set<T,N>::operator==(const integer_set& set) const
{
  if(m_size != set.m_size)
    return false;
  for(T v : set)
  {
    if(!contains(v))
      return false;
  }
  return true;
}

template<typename T,T N> bool integer_set<T,N>::operator!=(const integer_set& set) const
{
  return !operator==(set);
}

template<typename T,T N> bool integer_set<T,N>::operator<=(const integer_set& set) const
{
  return m_index <= set.m_index;
}

template<typename T,T N> bool integer_set<T,N>::operator>=(const integer_set& set) const
{
  return m_index >= set.m_index;
}

template<typename T,T N> bool integer_set<T,N>::operator<(const integer_set& set) const
{
  return m_index < set.m_index;
}

template<typename T,T N> bool integer_set<T,N>::operator>(const integer_set& set) const
{
  return m_index > set.m_index;
}

template<typename T,T N> T integer_set<T,N>::front() const
{
  return m_list[0];
}

template<typename T,T N> T integer_set<T,N>::back() const
{
  return m_list[m_size-1];
}

template<typename T,T N> typename integer_set<T,N>::iterator integer_set<T,N>::begin() const
{
  return iterator(m_list.data());
}

template<typename T,T N> typename integer_set<T,N>::iterator integer_set<T,N>::end() const
{
  return iterator(m_list.data()+m_size);
}

template<typename T,T N> typename integer_set<T,N>::iterator integer_set<T,N>::find(T v) const
{
  if(m_index[v] == NOT_IN_SET)
    return end();
  else
    return iterator(m_list.data()+m_index[v]);
}

template<typename T,T N> T integer_set<T,N>::operator[](T i) const
{
  return m_list[i];
}

template<typename T,T N> T integer_set<T,N>::min() const
{
  if(m_size >= MIN_SIZE_TO_SEARCH_INDEX)
  {
    for(T i=0; i<N; ++i)
    {
      if(m_index[i] != NOT_IN_SET)
        return i;
    }
  }
  else
  {
    T min = m_list[0];
    for(T i=1; i<m_size; ++i)
    {
      if(m_list[i] < min)
        min = m_list[i];
    }
    return min;
  }
  return NOT_IN_SET;
}

template<typename T,T N> T integer_set<T,N>::max() const
{
  if(m_size >= MIN_SIZE_TO_SEARCH_INDEX)
  {
    for(T i=N; i>0; --i)
    {
      if(m_index[i-1] != NOT_IN_SET)
        return i-1;
    }
  }
  else
  {
    T max = m_list[0];
    for(T i=1; i<m_size; ++i)
    {
      if(m_list[i] > max)
        max = m_list[i];
    }
    return max;
  }
  return NOT_IN_SET;
}

template<typename T,T N> template<class URNG> T integer_set<T,N>::random(URNG& gen) const
{
  return m_list[std::uniform_int_distribution<T>(0,m_size-1)(gen)];
}

template<typename T,T N> T integer_set<T,N>::size() const
{
  return m_size;
}

template<typename T,T N> bool integer_set<T,N>::empty() const
{
  return m_size == 0;
}

template<typename T,T N> bool integer_set<T,N>::contains(T v) const
{
  return m_index[v] != NOT_IN_SET;
}

template<typename T,T N> void integer_set<T,N>::clear()
{
  for(T v : *this)
    m_index[v] = NOT_IN_SET;
  m_size = 0;
}

template<typename T,T N> void integer_set<T,N>::insert(T v)
{
  if(contains(v))
    return;
  m_index[v] = m_size;
  m_list[m_size] = v;
  ++m_size;
}

template<typename T,T N> void integer_set<T,N>::insert(const integer_set& set)
{
  for(T v : set)
    insert(v);
}

template<typename T,T N> void integer_set<T,N>::erase(T v)
{
  if(!contains(v))
    return;
  --m_size;
  // If this element is not the last in the list
  // move the last element in the list to the index of v.
  if(m_index[v] != m_size)
  {
    m_list[m_index[v]] = m_list[m_size];
    m_index[m_list[m_size]] = m_index[v];
  }
  m_index[v] = NOT_IN_SET;
}

template<typename T,T N> void integer_set<T,N>::erase(const integer_set& set)
{
  for(T v : set)
    erase(v);
}

template<typename T,T N> integer_set<T,N> integer_set<T,N>::union_(const integer_set& set1,const integer_set& set2)
{
  if(set1.m_size <= set2.m_size)
  {
    integer_set out(set2);
    out.insert(set1);
    return out;
  }
  else
  {
    integer_set out(set1);
    out.insert(set2);
    return out;
  }
}

template<typename T,T N> integer_set<T,N> integer_set<T,N>::intersection(const integer_set& set1,const integer_set& set2)
{
  integer_set out;
  if(set1.m_size <= set2.m_size)
  {
    for(T v : set1)
    {
      if(set2.contains(v))
        out.insert(v);
    }
  }
  else
  {
    for(T v : set2)
    {
      if(set1.contains(v))
        out.insert(v);
    }
  }
  return out;
}

template<typename T,T N> bool integer_set<T,N>::union_empty(const integer_set& set1,const integer_set& set2)
{
  return set1.m_size == 0 && set2.m_size == 0;
}

template<typename T,T N> bool integer_set<T,N>::intersection_empty(const integer_set& set1,const integer_set& set2)
{
  if(set1.m_size <= set2.m_size)
  {
    for(T v : set1)
    {
      if(set2.contains(v))
        return false;
    }
  }
  else
  {
    for(T v : set2)
    {
      if(set1.contains(v))
        return false;
    }
  }
  return true;
}

template<typename T,T N> T integer_set<T,N>::min_size_to_search_index()
{
  // Bisection
  T min_size = 1;
  T max_size = N;
  T mid_size = (min_size+max_size)/2;
  do
  {
    if(get_probability(mid_size) >= 0.5)
      max_size = mid_size;
    else
      min_size = mid_size;
    mid_size = (min_size+max_size)/2;
  }
  while(mid_size != min_size);

  return max_size;
}

template<typename T,T N> double integer_set<T,N>::get_probability(T size)
{
  // Simplification of the hypergeometric distribution.
  // 1-hygepdf(0,N,size,size) =
  //     (N-size)!*(N-size)!
  // 1 - ___________________
  //      (N-size-size)!*N!
  double num = static_cast<double>(N-size);
  double den = static_cast<double>(N);
  double p = num/den;
  for(T i=1; i<size; ++i)
  {
    --num;
    --den;
    p *= num/den;
  }
  return 1.0-p;
}

////////////////////////////////////////////////
// integer_set::iterator

template<typename T,T N> integer_set<T,N>::iterator::iterator()
  :m_element{nullptr}
{}

template<typename T,T N> integer_set<T,N>::iterator::iterator(const T* element)
  :m_element{element}
{}

template<typename T,T N> bool integer_set<T,N>::iterator::operator==(const iterator& it) const
{
  return m_element == it.m_element;
}

template<typename T,T N> bool integer_set<T,N>::iterator::operator!=(const iterator& it) const
{
  return m_element != it.m_element;
}

template<typename T,T N> bool integer_set<T,N>::iterator::operator<(const iterator& it) const
{
  return m_element < it.m_element;
}

template<typename T,T N> bool integer_set<T,N>::iterator::operator>(const iterator& it) const
{
  return m_element > it.m_element;
}

template<typename T,T N> bool integer_set<T,N>::iterator::operator<=(const iterator& it) const
{
  return m_element <= it.m_element;
}

template<typename T,T N> bool integer_set<T,N>::iterator::operator>=(const iterator& it) const
{
  return m_element >= it.m_element;
}

template<typename T,T N> T integer_set<T,N>::iterator::operator*() const
{
  return *m_element;
}

template<typename T,T N> T integer_set<T,N>::iterator::operator[](T i) const
{
  return m_element[i];
}

template<typename T,T N> typename integer_set<T,N>::iterator& integer_set<T,N>::iterator::operator++()
{
  ++m_element;
  return *this;
}

template<typename T,T N> typename integer_set<T,N>::iterator integer_set<T,N>::iterator::operator++(int)
{
  iterator temp(*this);
  operator++();
  return temp;
}

template<typename T,T N> typename integer_set<T,N>::iterator& integer_set<T,N>::iterator::operator--()
{
  --m_element;
  return *this;
}

template<typename T,T N> typename integer_set<T,N>::iterator integer_set<T,N>::iterator::operator--(int)
{
  iterator temp(*this);
  operator--();
  return temp;
}

template<typename T,T N> typename integer_set<T,N>::iterator integer_set<T,N>::iterator::operator+(T i) const
{
  return iterator(m_element+i);
}

template<typename T,T N> typename integer_set<T,N>::iterator integer_set<T,N>::iterator::operator-(T i) const
{
  return iterator(m_element-i);
}

template<typename T,T N> typename integer_set<T,N>::iterator& integer_set<T,N>::iterator::operator+=(T i)
{
  m_element += i;
  return *this;
}

template<typename T,T N> typename integer_set<T,N>::iterator& integer_set<T,N>::iterator::operator-=(T i)
{
  m_element -= i;
  return *this;
}

Edit:

I implemented this container to speed up a program that uses many set operations. This container gives me a speed up of two orders of magnitude compared to std::unordered_set.

These functions are nearly identical to std::set and std::unordered_set. Like std::unordered_set, iterators return the elements in no particular order.

integer_set();
integer_set(const integer_set& set);
integer_set& operator=(const integer_set& set);
bool operator==(const integer_set& set) const;
bool operator!=(const integer_set& set) const;
iterator begin() const;
iterator end() const;
T front() const;
T back() const;
iterator find(T v) const;
void clear();
bool empty() const;
T size() const;
void insert(T v);
void erase(T v);

These are convenience functions not provided by std::set or std::unordered_set:

// Same as insert(set.begin(),set.end())
void insert(const integer_set& set);
// Same as erase(set.begin,set.end())
void erase(const integer_set& set);
// Test if integer v is in set. Same as find(v) != end()
bool contains(T v) const;
// Smallest/largest integer in set.
T min() const;
T max() const;
// Random integer in set given a RNG e.g. std::mersenne_twister_engine
template<class URNG> T random(URNG& gen) const;
// Element of set. Same as *(begin()+i).
T operator[](T i) const;
// Lexicographical comparison
bool operator<=(const integer_set& set) const;
bool operator>=(const integer_set& set) const;
bool operator<(const integer_set& set) const;
bool operator>(const integer_set& set) const;
// Self Explanatory
integer_set union_(const integer_set& set1,const integer_set& set2);
integer_set intersection(const integer_set& set1,const integer_set& set2);
bool union_empty(const integer_set& set1,const integer_set& set2);
bool intersection_empty(const integer_set& set1,const integer_set& set2);

Here is an example:

#include "integer_set.h"
#include <cassert>

int main()
{
  typedef integer_set<uint16_t,256> set256;

  set256 set1;
  set1.insert(144);
  set1.insert(255);
  set1.insert(0);
  assert(set1.find(0) != set1.end());
  assert(set1.contains(144));
  assert(set1.contains(255));
  set1.clear();
  assert(set1.begin() == set1.end());

  for(uint16_t i=30;i<100;i+=7)
    set1.insert(i);
  set1.insert(2);
  set1.insert(252);
  for(uint16_t i=121;i<240;i+=3)
    set1.insert(i);
  assert(set1.min() == 2);
  assert(set1.max() == 252);

  set256 set2;
  set2.insert(30);
  assert( set256::intersection(set1,set2).contains(30) );

  set2 = set1;
  for(uint16_t member : set2)
    set1.erase(member);
  assert(set1.empty());

  return 0;
}

Answer 1

The answer given by @galop1n is a good one, but since you asked for review, here is what could actually be improved in your code:

• Your class iterator is nothing but a wrapper which does exactly the same thing as std::array<T, N>::iterator. Therefore, you can simply write

  using iterator = typename std::array<T, N>::iterator;
  

  ...and delete your whole iterator implementation. The only things that are really important are the values passed to it by begin and end.

• It's not really important, but I would have kept my includes in alphbetical order so that I know exactly whether I have to look for an included header higher or lower in the list:

  #include <array>
  #include <bitset>
  #include <random>
  

• You obviously have a naming problem with union_. Since you are creating a set class, I would use operator& for intersection and operator| for union. While it is not recommended to overload operators when the meaning is not obvious, these operators are already commonly used for set operations (e.g. set and frozenset in Python's standard library). To improve consistency and usability, you can also implement operator&= and operator|=; users will expect them to be available if you already provide operator& and operator|.

• We already tackled the problem for union_ and intersection by making them operators, but I don't really like the fact that union_empty and intersection_empty are static functions. The need not be static since the only private member they access is m_size, and you can get this member by calling the method size. I would have made them free functions instead.

• I don't believe that checking for std::numeric_limits<T>::is_integer in the static assertions is useful since is_unsigned is only true for unsigned integer types. It is probably redundant.

• In the method random, you pass the random number generator by reference. The idiomatic way to pass a random number generator (e.g. std::shuffle or std::sample) is to pass it by universal reference and to std::forward it to the following function:

  template<typename T,T N>
  template<class URNG>
  T integer_set<T,N>::random(URNG&& gen) const
  {
      return m_list[std::uniform_int_distribution<T>(0,m_size-1)(std::forward<URNG>(gen))];
  }
  

• This line:

  template<typename T,T N> constexpr T integer_set<T,N>::NOT_IN_SET;
  

  Since you already initialized NOT_IN_SET directly in the class declaration, this line is useless. You should remove it.

Answer 2

You should learn about std::bitset.

It has almost everything you wants already with far less data storage. Encapsulate it inside your class to keep track of min, max and count in O(1) and write a custom iterator to list only the raised bits.

But according to your real usage, it may be not even needed and a mere std::bitset will be enough.

Below is your test case translated with a bitset:

#include <bitset>
#include <iostream>

int main() {
  std::cout <<  std::boolalpha;
  //typedef integer_set<uint16_t,256> set256;
  using set256 = std::bitset<256>;
  std::cout << "byte count for 256 bits : " << sizeof(set256) << '\n';

  set256 set1;
  set1.set(144);
  set1.set(255);
  set1.set(0);

  std::cout << "test separate bits : ";
  std::cout << set1.test(0) << " ";
  std::cout << set1.test(144) << " ";
  std::cout << set1.test(255) << "\n";

  std::cout << "count before after reset : ";
  std::cout << set1.count() << " ";
  set1.reset();
  std::cout << set1.count() << "\n";

  for(uint16_t i=30;i<100;i+=7)
    set1.set(i);
  set1.set(2);
  set1.set(252);
  for(uint16_t i=121;i<240;i+=3)
    set1.set(i);

  set256 set2;
  set2.set(30);

  auto inter = set1&set2;
  std::cout << "test over an intersection : " << inter.test(30) << "\n";

  set2 = set1;
  set1 &= ~set2;
  std::cout << "a complicated way to clear a bit set by anding a flipped copy : " << set1.count() << "\n";

  return 0;
}