SortedVector.hpp

 
#pragma once
 
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>
 
namespace dlinear {
struct Bound;  // Forward declaration
 
template <class T, class Compare = std::less<T>>
class SortedVector {
 public:
  using value_type = T;                                
  using size_type = size_t;                            
  using difference_type = std::ptrdiff_t;              
  using reference = T&;                                
  using const_reference = const T&;                    
  using pointer = T*;                                  
  using const_pointer = const T*;                      
  using iterator = typename std::vector<T>::iterator;  
  using const_iterator = typename std::vector<T>::const_iterator;  
  using reverse_iterator =
      typename std::vector<T>::reverse_iterator;  
  using const_reverse_iterator =
      typename std::vector<T>::const_reverse_iterator;  
 
  SortedVector() = default;
  explicit SortedVector(size_t size) : vector_(size) {}
  SortedVector(std::initializer_list<T> list) {
    vector_.reserve(list.size());
    for (const auto& value : list) insert(value);
  }
 
  template <typename V>
  iterator insert(V&& value) {
    auto it = std::lower_bound(vector_.cbegin(), vector_.cend(), value, compare_);
    return vector_.insert(it, std::forward<V>(value));
  }
 
  template <typename V>
  iterator insert(V&& value, bool insert_lower) {
    auto it = insert_lower ? std::lower_bound(vector_.cbegin(), vector_.cend(), value, compare_)
                           : std::upper_bound(vector_.cbegin(), vector_.cend(), value, compare_);
    return vector_.insert(it, std::forward<V>(value));
  }
 
  template <typename... Args>
  iterator emplace(Args&&... args) {
    return insert(T(std::forward<Args>(args)...));
  }
 
  template <typename... Args>
  iterator emplace(bool insert_lower, Args&&... args) {
    return insert(T(std::forward<Args>(args)...), insert_lower);
  }
 
  [[nodiscard]] size_t size() const { return vector_.size(); }
 
  [[nodiscard]] bool empty() const { return vector_.empty(); }
 
  const T& at(size_t i) const {
    if (i >= vector_.size()) throw std::out_of_range("Index out of range");
    return vector_[i];
  }
 
  const T& at(int i) const {
    if (i < 0) i = static_cast<int>(vector_.size()) + i;
    if (i < 0 || i >= static_cast<int>(vector_.size())) throw std::out_of_range("Index out of range");
    return vector_[i];
  }
 
  const T& operator[](size_t i) const { return vector_[i]; }
 
  const T& front() const { return vector_.front(); }
 
  const T& back() const { return vector_.back(); }
 
  bool erase(const const_iterator& it) {
    if (it == vector_.end()) return false;
    vector_.erase(it);
    return true;
  }
  bool erase(size_t i) {
    if (i >= vector_.size()) return false;
    vector_.erase(vector_.begin() + i);
    return true;
  }
  bool erase(int i) {
    if (i < 0) i = static_cast<int>(vector_.size()) - i;
    if (i < 0 || i >= static_cast<int>(vector_.size())) return false;
    vector_.erase(vector_.begin() + i);
    return true;
  }
  bool erase_value(const T& value) {
    auto it = std::lower_bound(vector_.cbegin(), vector_.cend(), value, compare_);
    if (it == vector_.cend() || !is_equal(*it, value)) return false;
    vector_.erase(it);
    return true;
  }
 
  const_iterator find(const T& value) const {
    auto it = std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
    if (it == vector_.end() || !is_equal(*it, value)) return end();
    return it;
  }
 
  const_iterator lower_bound(const T& value) const {
    return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
  }
 
  const_iterator upper_bound(const T& value) const {
    return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
  }
 
  [[nodiscard]] size_t count(const T& value) const {
    auto it = find(value);
    if (it == vector_.end()) return 0;
    size_t count = 1;
    for (it++; it != vector_.end() && is_equal(*it, value); ++it) ++count;
    return count;
  }
 
  [[nodiscard]] bool contains(const T& value) const { return find(value) != end(); }
 
  [[nodiscard]] const_iterator lesser_end(const T& value) const {
    return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
  }
 
  [[nodiscard]] const_iterator greater_begin(const T& value) const {
    auto it = std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
    while (it != vector_.cend() && is_equal(*it, value)) ++it;
    return it;
  }
 
  void clear() { vector_.clear(); }
 
  iterator begin() { return vector_.begin(); }
  iterator end() { return vector_.end(); }
  const_iterator begin() const { return vector_.cbegin(); }
  const_iterator end() const { return vector_.cend(); }
  const_iterator cbegin() const { return vector_.begin(); }
  const_iterator cend() const { return vector_.end(); }
  reverse_iterator rbegin() { return vector_.rbegin(); }
  reverse_iterator rend() { return vector_.rend(); }
  const_reverse_iterator rbegin() const { return vector_.crbegin(); }
  const_reverse_iterator rend() const { return vector_.crend(); }
  const_reverse_iterator crbegin() const { return vector_.crbegin(); }
  const_reverse_iterator crend() const { return vector_.crend(); }
 
 private:
  [[nodiscard]] inline bool is_equal(const T& lhs, const T& rhs) const {
    return !compare_(lhs, rhs) && !compare_(rhs, lhs);
  }
 
  std::vector<T> vector_;  
  Compare compare_;        
};
 
template <typename T>
std::ostream& operator<<(std::ostream& os, const SortedVector<T>& it) {
  std::copy(it.cbegin(), std::prev(it.cend()), std::ostream_iterator<T>(os, ", "));
  return os << *(it.crbegin());
}
 
extern template class SortedVector<Bound>;
extern template class SortedVector<int>;
extern template class SortedVector<double>;
 
}  // namespace dlinear