Sparse set

sparse_set.h

#pragma once

// Using Uninitialized Memory for Fun and Profit
// http://research.swtch.com/sparse
#include <vector>
class SparseSet
{
private:
  size_t n_;
  std::vector<uint32_t> dense_, sparse_;

public:
  SparseSet(size_t capacity = 1453689) 
    : n_(0), dense_(capacity), sparse_(capacity) 
  {}
  ~SparseSet() {}

  bool empty() const    { return n_ == 0; }
  uint32_t back() const { return dense_[n_-1]; }
  void clear()          { n_ = 0; }

  using iterator = std::vector<uint32_t>::iterator;
  using const_iterator = std::vector<uint32_t>::const_iterator;

  iterator  begin()     { return dense_.begin(); }
  iterator  end()       { return dense_.begin() + n_; }
  const_iterator  begin() const { return dense_.begin(); }
  const_iterator  end()   const { return dense_.begin() + n_; }

  bool has(uint32_t i) const { 
    if (i >= dense_.size()) 
      return false; 
    auto x = sparse_[i];
    return x < n_ && dense_[x] == i;
  }

  void grow(size_t n)   {
    n = std::max(n, dense_.size()) * 2;
    dense_.resize(n);
    sparse_.resize(n);
  }

  void insert(uint32_t i) {
    if (has(i)) return;
    if (i >= dense_.size()) grow(i);

    dense_[n_] = i;
    sparse_[i] = n_;
    ++n_;
  }

  void remove(uint32_t i) {
    if (!has(i)) return;

    uint32_t j = dense_[n_-1];
    dense_[sparse_[i]] = j;
    sparse_[j] = sparse_[i];
    --n_;
  }
};