uvector.h

Go to the documentation of this file.

#ifndef AOCOMMON_UVECTOR_H_
#define AOCOMMON_UVECTOR_H_
 
#include <algorithm>
#include <cstring>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <utility>

 
namespace aocommon {


template <typename Tp, typename Alloc = std::allocator<Tp>>
class UVector : private Alloc {
  static_assert(std::is_standard_layout<Tp>(),
                "A UVector can only hold classes with standard layout");
 
 public:
  typedef Tp value_type;
  typedef Alloc allocator_type;
  typedef Tp& reference;
  typedef const Tp& const_reference;
  typedef Tp* pointer;
  typedef const Tp* const_pointer;
  typedef Tp* iterator;
  typedef const Tp* const_iterator;
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::ptrdiff_t difference_type;
  typedef std::size_t size_t;
  typedef std::size_t size_type;
 
 private:
#if __cplusplus > 201402L
  typedef typename std::allocator_traits<allocator_type>::is_always_equal allocator_is_always_equal;
#else
  typedef std::false_type allocator_is_always_equal;
#endif
  pointer _begin, _end, _endOfStorage;
 
 public:
  explicit UVector(const allocator_type& allocator = Alloc()) noexcept
      : Alloc(allocator), _begin(nullptr), _end(nullptr), _endOfStorage(nullptr) {}

  explicit UVector(size_t n) : _begin(allocate(n)), _end(_begin + n), _endOfStorage(_end) {}

  UVector(size_t n, const value_type& val, const allocator_type& allocator = Alloc())
      : Alloc(allocator), _begin(allocate(n)), _end(_begin + n), _endOfStorage(_end) {
    std::uninitialized_fill_n<Tp*, size_t>(_begin, n, val);
  }

  template <class InputIterator>
  UVector(InputIterator first, InputIterator last, const allocator_type& allocator = Alloc())
      : Alloc(allocator) {
    construct_from_range<InputIterator>(first, last, std::is_integral<InputIterator>());
  }

  UVector(const UVector<Tp, Alloc>& other)
      : Alloc(std::allocator_traits<Alloc>::select_on_container_copy_construction(
            static_cast<allocator_type>(other))),
        _begin(allocate(other.size())),
        _end(_begin + other.size()),
        _endOfStorage(_end) {
    std::copy(other._begin, other._end, _begin);
  }

  UVector(const UVector<Tp, Alloc>& other, const allocator_type& allocator)
      : Alloc(allocator),
        _begin(allocate(other.size())),
        _end(_begin + other.size()),
        _endOfStorage(_end) {
    std::copy(other._begin, other._end, _begin);
  }

  UVector(UVector<Tp, Alloc>&& other) noexcept
      : Alloc(std::move(other)),
        _begin(other._begin),
        _end(other._end),
        _endOfStorage(other._endOfStorage) {
    other._begin = nullptr;
    other._end = nullptr;
    other._endOfStorage = nullptr;
  }

  UVector(UVector<Tp, Alloc>&& other, const allocator_type& allocator) noexcept
      : Alloc(allocator),
        _begin(other._begin),
        _end(other._end),
        _endOfStorage(other._endOfStorage) {
    other._begin = nullptr;
    other._end = nullptr;
    other._endOfStorage = nullptr;
  }

  UVector(std::initializer_list<Tp> initlist, const allocator_type& allocator = Alloc())
      : Alloc(allocator),
        _begin(allocate(initlist.size())),
        _end(_begin + initlist.size()),
        _endOfStorage(_end) {
    iterator destIter = _begin;
    for (typename std::initializer_list<Tp>::const_iterator i = initlist.begin();
         i != initlist.end(); ++i) {
      *destIter = *i;
      ++destIter;
    }
  }

  ~UVector() noexcept { deallocate(); }

  UVector& operator=(const UVector<Tp, Alloc>& other) {
    return assign_copy_from(
        other, typename std::allocator_traits<Alloc>::propagate_on_container_copy_assignment());
  }

  UVector& operator=(UVector<Tp, Alloc>&& other) noexcept(
      std::allocator_traits<Alloc>::propagate_on_container_move_assignment::value ||
      allocator_is_always_equal::value) {
    return assign_move_from(
        std::move(other),
        typename std::allocator_traits<Alloc>::propagate_on_container_move_assignment());
  }

  iterator begin() noexcept { return _begin; }

  const_iterator begin() const noexcept { return _begin; }

  iterator end() noexcept { return _end; }

  const_iterator end() const noexcept { return _end; }

  reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }

  const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }

  reverse_iterator rend() noexcept { return reverse_iterator(begin()); }

  const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }

  const_iterator cbegin() const noexcept { return _begin; }

  const_iterator cend() const noexcept { return _end; }

  const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }

  const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }

  size_t size() const noexcept { return _end - _begin; }

  size_t max_size() const noexcept { return Alloc::max_size(); }

  void resize(size_t n) {
    if (capacity() < n) {
      size_t newSize = enlarge_size(n);
      pointer newStorage = allocate(newSize);
      std::move(_begin, _end, newStorage);
      deallocate();
      _begin = newStorage;
      _endOfStorage = _begin + newSize;
    }
    _end = _begin + n;
  }

  void resize(size_t n, const Tp& val) {
    size_t oldSize = size();
    if (capacity() < n) {
      pointer newStorage = allocate(n);
      std::move(_begin, _end, newStorage);
      deallocate();
      _begin = newStorage;
      _endOfStorage = _begin + n;
    }
    _end = _begin + n;
    if (oldSize < n) std::uninitialized_fill<Tp*>(_begin + oldSize, _end, val);
  }

  size_t capacity() const noexcept { return _endOfStorage - _begin; }

  bool empty() const noexcept { return _begin == _end; }

  void reserve(size_t n) {
    if (capacity() < n) {
      const size_t curSize = size();
      pointer newStorage = allocate(n);
      std::move(_begin, _begin + curSize, newStorage);
      deallocate();
      _begin = newStorage;
      _end = newStorage + curSize;
      _endOfStorage = _begin + n;
    }
  }

  void shrink_to_fit() {
    const size_t curSize = size();
    if (curSize == 0) {
      deallocate();
      _begin = nullptr;
      _end = nullptr;
      _endOfStorage = nullptr;
    } else if (curSize < capacity()) {
      pointer newStorage = allocate(curSize);
      std::move(_begin, _begin + curSize, newStorage);
      deallocate();
      _begin = newStorage;
      _end = newStorage + curSize;
      _endOfStorage = _begin + curSize;
    }
  }

  Tp& operator[](size_t index) noexcept { return _begin[index]; }

  const Tp& operator[](size_t index) const noexcept { return _begin[index]; }

  Tp& at(size_t index) {
    check_bounds(index);
    return _begin[index];
  }

  const Tp& at(size_t index) const {
    check_bounds(index);
    return _begin[index];
  }

  Tp& front() noexcept { return *_begin; }

  const Tp& front() const noexcept { return *_begin; }

  Tp& back() noexcept { return *(_end - 1); }

  const Tp& back() const noexcept { return *(_end - 1); }

  Tp* data() noexcept { return _begin; }

  const Tp* data() const noexcept { return _begin; }

  template <class InputIterator>
  void assign(InputIterator first, InputIterator last) {
    assign_from_range<InputIterator>(first, last, std::is_integral<InputIterator>());
  }

  void assign(size_t n, const Tp& val) {
    if (n > capacity()) {
      iterator newStorage = allocate(n);
      deallocate();
      _begin = newStorage;
      _endOfStorage = _begin + n;
    }
    _end = _begin + n;
    std::uninitialized_fill_n<Tp*, size_t>(_begin, n, val);
  }

  void assign(std::initializer_list<Tp> initlist) {
    if (initlist.size() > capacity()) {
      iterator newStorage = allocate(initlist.size());
      deallocate();
      _begin = newStorage;
      _endOfStorage = _begin + initlist.size();
    }
    _end = _begin + initlist.size();
    iterator destIter = _begin;
    for (typename std::initializer_list<Tp>::const_iterator i = initlist.begin();
         i != initlist.end(); ++i) {
      *destIter = *i;
      ++destIter;
    }
  }

  void push_back(const Tp& item) {
    if (_end == _endOfStorage) enlarge(enlarge_size(1));
    *_end = item;
    ++_end;
  }

  void push_back(Tp&& item) {
    if (_end == _endOfStorage) enlarge(enlarge_size(1));
    *_end = std::move(item);
    ++_end;
  }

  void pop_back() { --_end; }

  iterator insert(const_iterator position, const Tp& item) {
    if (_end == _endOfStorage) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(1), index, 1);
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + 1);
      ++_end;
    }
    *const_cast<iterator>(position) = item;
    return const_cast<iterator>(position);
  }

  iterator insert(const_iterator position, size_t n, const Tp& val) {
    if (capacity() < size() + n) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(n), index, n);
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + n);
      _end += n;
    }
    std::uninitialized_fill_n<Tp*, size_t>(const_cast<iterator>(position), n, val);
    return const_cast<iterator>(position);
  }

  template <class InputIterator>
  iterator insert(const_iterator position, InputIterator first, InputIterator last) {
    return insert_from_range<InputIterator>(position, first, last,
                                            std::is_integral<InputIterator>());
  }

  iterator insert(const_iterator position, Tp&& item) {
    if (_end == _endOfStorage) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(1), index, 1);
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + 1);
      ++_end;
    }
    *const_cast<iterator>(position) = std::move(item);
    return const_cast<iterator>(position);
  }

  iterator insert(const_iterator position, std::initializer_list<Tp> initlist) {
    if (capacity() < size() + initlist.size()) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(initlist.size()), index, initlist.size());
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + initlist.size());
      _end += initlist.size();
    }
    iterator destIter = const_cast<iterator>(position);
    for (typename std::initializer_list<Tp>::const_iterator i = initlist.begin();
         i != initlist.end(); ++i) {
      *destIter = *i;
      ++destIter;
    }
    return const_cast<iterator>(position);
  }

  iterator erase(const_iterator position) {
    std::move(const_cast<iterator>(position) + 1, _end, const_cast<iterator>(position));
    --_end;
    return const_cast<iterator>(position);
  }

  iterator erase(const_iterator first, const_iterator last) {
    std::move(const_cast<iterator>(last), _end, const_cast<iterator>(first));
    _end -= last - first;
    return const_cast<iterator>(first);
  }

  void swap(UVector<Tp, Alloc>& other) noexcept {
    swap(other, typename std::allocator_traits<Alloc>::propagate_on_container_swap());
  }

  void clear() { _end = _begin; }

  template <typename... Args>
  iterator emplace(const_iterator position, Args&&... args) {
    if (_end == _endOfStorage) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(1), index, 1);
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + 1);
      ++_end;
    }
    *const_cast<iterator>(position) = Tp(std::forward<Args>(args)...);
    return const_cast<iterator>(position);
  }

  template <typename... Args>
  Tp& emplace_back(Args&&... args) {
    if (_end == _endOfStorage) enlarge(enlarge_size(1));
    *_end = Tp(std::forward<Args>(args)...);
    ++_end;
    return back();
  }

  allocator_type get_allocator() const noexcept { return *this; }
 
  // --- NON STANDARD METHODS ---

  iterator insert_uninitialized(const_iterator position, size_t n) {
    if (capacity() < size() + n) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(n), index, n);
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + n);
      _end += n;
    }
    return const_cast<iterator>(position);
  }

  template <class InputIterator>
  void push_back(InputIterator first, InputIterator last) {
    push_back_range<InputIterator>(first, last, std::is_integral<InputIterator>());
  }

  void push_back(size_t n, const Tp& val) {
    if (capacity() - size() < n) {
      enlarge(enlarge_size(n));
    }
    std::uninitialized_fill_n<Tp*, size_t>(_end, n, val);
    _end += n;
  }

  void push_back(std::initializer_list<Tp> initlist) {
    if (capacity() - size() < initlist.size()) {
      enlarge(enlarge_size(initlist.size()));
    }
    for (typename std::initializer_list<Tp>::iterator i = initlist.begin(); i != initlist.end();
         ++i) {
      *_end = *i;
      ++_end;
    }
  }

  void push_back_uninitialized(size_t n) { resize(size() + n); }
 
 private:
  pointer allocate(size_t n) { return Alloc::allocate(n); }
 
  void deallocate() noexcept { deallocate(_begin, capacity()); }
 
  void deallocate(pointer begin, size_t n) noexcept {
    if (begin != nullptr) Alloc::deallocate(begin, n);
  }
 
  template <typename InputIterator>
  void construct_from_range(InputIterator first, InputIterator last, std::false_type) {
    construct_from_range<InputIterator>(
        first, last, typename std::iterator_traits<InputIterator>::iterator_category());
  }
 
  template <typename Integral>
  void construct_from_range(Integral n, Integral val, std::true_type) {
    _begin = allocate(n);
    _end = _begin + n;
    _endOfStorage = _end;
    std::uninitialized_fill_n<Tp*, size_t>(_begin, n, val);
  }
 
  template <typename InputIterator>
  void construct_from_range(InputIterator first, InputIterator last, std::forward_iterator_tag) {
    size_t n = std::distance(first, last);
    _begin = allocate(n);
    _end = _begin + n;
    _endOfStorage = _begin + n;
    Tp* destIter = _begin;
    while (first != last) {
      *destIter = *first;
      ++destIter;
      ++first;
    }
  }
 
  template <typename InputIterator>
  void assign_from_range(InputIterator first, InputIterator last, std::false_type) {
    assign_from_range<InputIterator>(
        first, last, typename std::iterator_traits<InputIterator>::iterator_category());
  }
 
  // This function is called from assign(iter,iter) when Tp is an integral. In
  // that case, the user tried to call assign(n, &val), but it got caught by the
  // wrong overload.
  template <typename Integral>
  void assign_from_range(Integral n, Integral val, std::true_type) {
    if (size_t(n) > capacity()) {
      iterator newStorage = allocate(n);
      deallocate();
      _begin = newStorage;
      _endOfStorage = _begin + n;
    }
    _end = _begin + n;
    std::uninitialized_fill_n<Tp*, size_t>(_begin, n, val);
  }
 
  template <typename InputIterator>
  void assign_from_range(InputIterator first, InputIterator last, std::forward_iterator_tag) {
    size_t n = std::distance(first, last);
    if (n > capacity()) {
      iterator newStorage = allocate(n);
      deallocate();
      _begin = newStorage;
      _endOfStorage = _begin + n;
    }
    _end = _begin + n;
    Tp* destIter = _begin;
    while (first != last) {
      *destIter = *first;
      ++destIter;
      ++first;
    }
  }
 
  template <typename InputIterator>
  iterator insert_from_range(const_iterator position, InputIterator first, InputIterator last,
                             std::false_type) {
    return insert_from_range<InputIterator>(
        position, first, last, typename std::iterator_traits<InputIterator>::iterator_category());
  }
 
  template <typename Integral>
  iterator insert_from_range(const_iterator position, Integral n, Integral val, std::true_type) {
    if (capacity() < size() + n) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(n), index, n);
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + n);
      _end += n;
    }
    std::uninitialized_fill_n<Tp*, size_t>(const_cast<iterator>(position), n, val);
    return const_cast<iterator>(position);
  }
 
  template <typename InputIterator>
  iterator insert_from_range(const_iterator position, InputIterator first, InputIterator last,
                             std::forward_iterator_tag) {
    size_t n = std::distance(first, last);
    if (capacity() < size() + n) {
      size_t index = position - _begin;
      enlarge_for_insert(enlarge_size(n), index, n);
      position = _begin + index;
    } else {
      std::move_backward(const_cast<iterator>(position), _end, _end + n);
      _end += n;
    }
    Tp* destIter = const_cast<iterator>(position);
    while (first != last) {
      *destIter = *first;
      ++destIter;
      ++first;
    }
    return const_cast<iterator>(position);
  }
 
  void check_bounds(size_t index) const {
    if (index >= size()) throw std::out_of_range("Access to element in UVector past end");
  }
 
  size_t enlarge_size(size_t extra_space_needed) const noexcept {
    return size() + std::max(size(), extra_space_needed);
  }
 
  void enlarge(size_t newSize) {
    pointer newStorage = allocate(newSize);
    std::copy(_begin, _end, newStorage);
    deallocate();
    _end = newStorage + size();
    _begin = newStorage;
    _endOfStorage = _begin + newSize;
  }
 
  void enlarge_for_insert(size_t newSize, size_t insert_position, size_t insert_count) {
    pointer newStorage = allocate(newSize);
    std::copy(_begin, _begin + insert_position, newStorage);
    std::copy(_begin + insert_position, _end, newStorage + insert_position + insert_count);
    deallocate();
    _end = newStorage + size() + insert_count;
    _begin = newStorage;
    _endOfStorage = _begin + newSize;
  }
 
  // implementation of operator=(const&) without
  // propagate_on_container_copy_assignment
  UVector& assign_copy_from(const UVector<Tp, Alloc>& other, std::false_type) {
    const size_t n = other.size();
    if (n > capacity()) {
      iterator newStorage = allocate(n);
      deallocate();
      _begin = newStorage;
      _end = _begin + n;
      _endOfStorage = _end;
    }
    std::copy(other._begin, other._begin + n, _begin);
    return *this;
  }
 
  // implementation of operator=(const&) with
  // propagate_on_container_copy_assignment
  UVector& assign_copy_from(const UVector<Tp, Alloc>& other, std::true_type) {
    if (allocator_is_always_equal() || static_cast<Alloc&>(other) == static_cast<Alloc&>(*this)) {
      assign_copy_from(other, std::false_type());
    } else {
      const size_t n = other.size();
      iterator newStorage = static_cast<Alloc&>(other).allocate(n);
      deallocate();
      _begin = newStorage;
      _end = _begin + n;
      _endOfStorage = _end;
      std::copy(other._begin, other._begin + n, _begin);
      Alloc::operator=(static_cast<Alloc&>(other));
    }
    return *this;
  }
 
  // implementation of operator=() without
  // propagate_on_container_move_assignment
  UVector& assign_move_from(UVector<Tp, Alloc>&& other,
                            std::false_type) noexcept(allocator_is_always_equal::value) {
    if (allocator_is_always_equal::value ||
        static_cast<Alloc&>(other) == static_cast<Alloc&>(*this)) {
      deallocate();
      _begin = other._begin;
      _end = other._end;
      _endOfStorage = other._endOfStorage;
      other._begin = nullptr;
      other._end = nullptr;
      other._endOfStorage = nullptr;
    } else {
      // We should not propagate the allocator and the allocators are different.
      // This means we can not swap the allocated space, since then we would
      // deallocate the space with a different allocator type. Therefore, we
      // need to copy:
      assign_copy_from(other, std::false_type());
    }
    return *this;
  }
 
  // implementation of operator=() with propagate_on_container_move_assignment
  UVector& assign_move_from(UVector<Tp, Alloc>&& other, std::true_type) noexcept {
    deallocate();
    Alloc::operator=(std::move(static_cast<Alloc&>(other)));
    _begin = other._begin;
    _end = other._end;
    _endOfStorage = other._endOfStorage;
    other._begin = nullptr;
    other._end = nullptr;
    other._endOfStorage = nullptr;
    return *this;
  }
 
  // implementation of swap with propagate_on_container_swap
  void swap(UVector<Tp, Alloc>& other, std::true_type) noexcept {
    std::swap(_begin, other._begin);
    std::swap(_end, other._end);
    std::swap(_endOfStorage, other._endOfStorage);
    std::swap(static_cast<Alloc&>(other), static_cast<Alloc&>(*this));
  }
 
  // implementation of swap without propagate_on_container_swap
  void swap(UVector<Tp, Alloc>& other, std::false_type) noexcept {
    std::swap(_begin, other._begin);
    std::swap(_end, other._end);
    std::swap(_endOfStorage, other._endOfStorage);
  }
 
  template <typename InputIterator>
  void push_back_range(InputIterator first, InputIterator last, std::false_type) {
    push_back_range<InputIterator>(
        first, last, typename std::iterator_traits<InputIterator>::iterator_category());
  }
 
  // This function is called from push_back(iter,iter) when Tp is an integral.
  // In that case, the user tried to call push_back(n, &val), but it got caught
  // by the wrong overload.
  template <typename Integral>
  void push_back_range(Integral n, Integral val, std::true_type) {
    if (capacity() - size() < size_t(n)) {
      enlarge(enlarge_size(n));
    }
    std::uninitialized_fill_n<Tp*, size_t>(_end, n, val);
    _end += n;
  }
 
  template <typename InputIterator>
  void push_back_range(InputIterator first, InputIterator last, std::forward_iterator_tag) {
    size_t n = std::distance(first, last);
    if (n > capacity() - size()) {
      enlarge(enlarge_size(n));
    }
    while (first != last) {
      *_end = *first;
      ++_end;
      ++first;
    }
  }
};

template <class Tp, class Alloc>
inline bool operator==(const UVector<Tp, Alloc>& lhs, const UVector<Tp, Alloc>& rhs) noexcept {
  return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template <class Tp, class Alloc>
inline bool operator!=(const UVector<Tp, Alloc>& lhs, const UVector<Tp, Alloc>& rhs) noexcept {
  return !(lhs == rhs);
}

template <class Tp, class Alloc>
inline bool operator<(const UVector<Tp, Alloc>& lhs, const UVector<Tp, Alloc>& rhs) noexcept {
  const size_t minSize = std::min(lhs.size(), rhs.size());
  for (size_t i = 0; i != minSize; ++i) {
    if (lhs[i] < rhs[i])
      return true;
    else if (lhs[i] > rhs[i])
      return false;
  }
  return lhs.size() < rhs.size();
}

template <class Tp, class Alloc>
inline bool operator<=(const UVector<Tp, Alloc>& lhs, const UVector<Tp, Alloc>& rhs) noexcept {
  const size_t minSize = std::min(lhs.size(), rhs.size());
  for (size_t i = 0; i != minSize; ++i) {
    if (lhs[i] < rhs[i])
      return true;
    else if (lhs[i] > rhs[i])
      return false;
  }
  return lhs.size() <= rhs.size();
}

template <class Tp, class Alloc>
inline bool operator>(const UVector<Tp, Alloc>& lhs, const UVector<Tp, Alloc>& rhs) noexcept {
  return rhs < lhs;
}

template <class Tp, class Alloc>
inline bool operator>=(const UVector<Tp, Alloc>& lhs, const UVector<Tp, Alloc>& rhs) noexcept {
  return rhs <= lhs;
}

template <class Tp, class Alloc>
inline void swap(UVector<Tp, Alloc>& x, UVector<Tp, Alloc>& y) {
  x.swap(y);
}

 
}  // namespace aocommon
 
#endif  // AOCOMMON_UVECTOR_H_