127 lines
3.4 KiB
C++
127 lines
3.4 KiB
C++
|
|
#pragma once
|
|
|
|
#if !defined(MIJIN_CONTAINER_SORTED_VECTOR_HPP_INCLUDED)
|
|
#define MIJIN_CONTAINER_SORTED_VECTOR_HPP_INCLUDED 1
|
|
|
|
#include <algorithm>
|
|
#include <functional>
|
|
#include <vector>
|
|
#include "../util/functional.hpp"
|
|
|
|
namespace mijin
|
|
{
|
|
template<typename T,
|
|
basic_projection<T> TProj = std::identity,
|
|
ordering<projected_t<T, TProj>> TOrder = std::less<projected_t<T, TProj>>>
|
|
class SortedVector
|
|
{
|
|
public:
|
|
using key_t = projected_t<T, TProj>;
|
|
using base_t = std::vector<T>;
|
|
using iterator = base_t::const_iterator;
|
|
using const_iterator = iterator;
|
|
using reverse_iterator = base_t::const_reverse_iterator;
|
|
using const_reverse_iterator = reverse_iterator;
|
|
private:
|
|
std::vector<T> values_;
|
|
[[no_unique_address]] TProj proj_;
|
|
[[no_unique_address]] TOrder order_;
|
|
public:
|
|
explicit SortedVector(TProj proj = {}, TOrder order = {}) noexcept
|
|
: proj_(std::move(proj)), order_(std::move(order)) {}
|
|
explicit SortedVector(TOrder order) noexcept
|
|
: order_(std::move(order)) {}
|
|
SortedVector(const SortedVector&) = default;
|
|
SortedVector(SortedVector&&) noexcept = default;
|
|
explicit SortedVector(std::vector<T> values) : values_(std::move(values))
|
|
{
|
|
processValues();
|
|
}
|
|
SortedVector& operator=(const SortedVector&) = default;
|
|
SortedVector& operator=(SortedVector&&) noexcept = default;
|
|
|
|
// --- iterators ---
|
|
|
|
[[nodiscard]]
|
|
const_iterator begin() const noexcept { return values_.begin(); }
|
|
|
|
[[nodiscard]]
|
|
const_iterator cbegin() const noexcept { return values_.cbegin(); }
|
|
|
|
[[nodiscard]]
|
|
const_reverse_iterator rbegin() const noexcept { return values_.rbegin(); }
|
|
|
|
[[nodiscard]]
|
|
const_reverse_iterator crbegin() const noexcept { return values_.crbegin(); }
|
|
|
|
[[nodiscard]]
|
|
const_iterator end() const noexcept { return values_.end(); }
|
|
|
|
[[nodiscard]]
|
|
const_iterator cend() const noexcept { return values_.cend(); }
|
|
|
|
[[nodiscard]]
|
|
const_reverse_iterator rend() const noexcept { return values_.rend(); }
|
|
|
|
[[nodiscard]]
|
|
const_reverse_iterator crend() const noexcept { return values_.crend(); }
|
|
|
|
// --- reading ---
|
|
[[nodiscard]]
|
|
const T& at(std::size_t idx) const noexcept { return values_.at(idx); }
|
|
|
|
[[nodiscard]]
|
|
const T& operator[](std::size_t idx) const noexcept { return at(idx); }
|
|
|
|
[[nodiscard]]
|
|
std::size_t size() const noexcept { return values_.size(); }
|
|
|
|
[[nodiscard]]
|
|
bool empty() const noexcept { return values_.empty(); }
|
|
|
|
[[nodiscard]]
|
|
iterator find(key_t key) const noexcept
|
|
{
|
|
auto it = std::ranges::lower_bound(values_, key, order_, proj_);
|
|
if (it == values_.end() || std::invoke(proj_, *it) != key) {
|
|
return values_.end();
|
|
}
|
|
return it;
|
|
}
|
|
|
|
// --- writing ---
|
|
void clear()
|
|
{
|
|
values_.clear();
|
|
}
|
|
|
|
void emplace(std::vector<T> values)
|
|
{
|
|
values_ = std::move(values);
|
|
processValues();
|
|
}
|
|
|
|
template<typename TRange>
|
|
void appendRange(TRange&& range)
|
|
{
|
|
values_.append_range(std::forward<TRange>(range));
|
|
processValues();
|
|
}
|
|
|
|
[[nodiscard]]
|
|
std::vector<T>&& release() && noexcept
|
|
{
|
|
return std::exchange(values_, {});
|
|
}
|
|
private:
|
|
void processValues()
|
|
{
|
|
values_.shrink_to_fit();
|
|
std::ranges::sort(values_, order_, proj_);
|
|
}
|
|
};
|
|
} // namespace mijin
|
|
|
|
#endif // MIJIN_CONTAINER_SORTED_VECTOR_HPP_INCLUDED
|