Loading...
Searching...
No Matches
reservedvector.hh
Go to the documentation of this file.
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
#ifndef DUNE_COMMON_RESERVEDVECTOR_HH
#define DUNE_COMMON_RESERVEDVECTOR_HH
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <cstddef>
#include <initializer_list>
#include <dune/common/hash.hh>
#include <dune/common/std/algorithm.hh>
#include <dune/common/std/compare.hh>
#ifdef CHECK_RESERVEDVECTOR
#define CHECKSIZE(X) assert(X)
#else
#define CHECKSIZE(X) {}
#endif
namespace Dune
{
template<class T, int n>
class ReservedVector
{
using storage_type = std::array<T,n>;
public:
typedef typename storage_type::value_type value_type;
typedef typename storage_type::pointer pointer;
typedef typename storage_type::const_pointer const_pointer;
typedef typename storage_type::reference reference;
typedef typename storage_type::const_reference const_reference;
typedef typename storage_type::size_type size_type;
typedef typename storage_type::difference_type difference_type;
typedef typename storage_type::iterator iterator;
typedef typename storage_type::const_iterator const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
constexpr ReservedVector()
noexcept(std::is_nothrow_default_constructible_v<value_type>)
: storage_()
, size_(0)
{}
explicit constexpr ReservedVector(size_type count)
noexcept(std::is_nothrow_default_constructible_v<value_type>)
: storage_()
, size_(count)
{
assert(count <= n);
}
constexpr ReservedVector(size_type count, const value_type& value)
noexcept(std::is_nothrow_copy_assignable_v<value_type> &&
noexcept(ReservedVector(count)))
: ReservedVector(count)
{
for (size_type i=0; i<count; ++i)
storage_[i] = value;
}
template<class InputIt,
std::enable_if_t<std::is_convertible_v<typename std::iterator_traits<InputIt>::value_type, value_type>, int> = 0>
constexpr ReservedVector(InputIt first, InputIt last)
noexcept(std::is_nothrow_copy_assignable_v<value_type> &&
noexcept(ReservedVector()))
: ReservedVector()
{
for (size_type i=0; i<n && first!=last; ++i,++size_)
storage_[i] = *first++;
assert(first == last);
}
constexpr ReservedVector(std::initializer_list<value_type> const& l)
noexcept(std::is_nothrow_copy_assignable_v<value_type> &&
noexcept(ReservedVector(l.begin(),l.end())))
: ReservedVector(l.begin(),l.end())
{}
constexpr bool operator== (const ReservedVector& that) const noexcept
{
if (size() != that.size())
return false;
for (size_type i=0; i<size(); ++i)
if (!(storage_[i]==that.storage_[i]))
return false;
return true;
}
constexpr auto operator<=> (const ReservedVector& that) const noexcept
{
return Std::lexicographical_compare_three_way(begin(), end(), that.begin(), that.end());
}
constexpr void clear() noexcept
{
size_ = 0;
}
constexpr void resize(size_type s) noexcept
{
CHECKSIZE(s<=n);
size_ = s;
}
constexpr void push_back(const value_type& t)
noexcept(std::is_nothrow_copy_assignable_v<value_type>)
{
CHECKSIZE(size_<n);
storage_[size_++] = t;
}
constexpr void push_back(value_type&& t)
noexcept(std::is_nothrow_move_assignable_v<value_type>)
{
CHECKSIZE(size_<n);
storage_[size_++] = std::move(t);
}
template<class... Args>
reference emplace_back(Args&&... args)
noexcept(std::is_nothrow_constructible_v<value_type,decltype(args)...>)
{
CHECKSIZE(size_<n);
value_type* p = &storage_[size_++];
// first destroy any previously (default) constructed element at that location
p->~value_type();
// construct the value_type in place
// NOTE: This is not an integral constant expression.
// With c++20 we could use std::construct_at
::new (const_cast<void*>(static_cast<const volatile void*>(p)))
value_type(std::forward<Args>(args)...);
return *p;
}
constexpr void pop_back() noexcept
{
if (! empty()) size_--;
}
constexpr iterator begin() noexcept
{
return storage_.begin();
}
constexpr const_iterator begin() const noexcept
{
return storage_.begin();
}
constexpr const_iterator cbegin() const noexcept
{
return storage_.cbegin();
}
constexpr reverse_iterator rbegin() noexcept
{
return reverse_iterator{begin()+size()};
}
constexpr const_reverse_iterator rbegin() const noexcept
{
return const_reverse_iterator{begin()+size()};
}
constexpr const_reverse_iterator crbegin() const noexcept
{
return const_reverse_iterator{begin()+size()};
}
constexpr iterator end() noexcept
{
return storage_.begin()+size();
}
constexpr const_iterator end() const noexcept
{
return storage_.begin()+size();
}
constexpr const_iterator cend() const noexcept
{
return storage_.cbegin()+size();
}
constexpr reverse_iterator rend() noexcept
{
return reverse_iterator{begin()};
}
constexpr const_reverse_iterator rend() const noexcept
{
return const_reverse_iterator{begin()};
}
constexpr const_reverse_iterator crend() const noexcept
{
return const_reverse_iterator{begin()};
}
constexpr reference at(size_type i)
{
if (!(i < size()))
throw std::out_of_range("Index out of range");
return storage_[i];
}
constexpr const_reference at(size_type i) const
{
if (!(i < size()))
throw std::out_of_range("Index out of range");
return storage_[i];
}
constexpr reference operator[] (size_type i) noexcept
{
CHECKSIZE(size_>i);
return storage_[i];
}
constexpr const_reference operator[] (size_type i) const noexcept
{
CHECKSIZE(size_>i);
return storage_[i];
}
constexpr reference front() noexcept
{
CHECKSIZE(size_>0);
return storage_[0];
}
constexpr const_reference front() const noexcept
{
CHECKSIZE(size_>0);
return storage_[0];
}
constexpr reference back() noexcept
{
CHECKSIZE(size_>0);
return storage_[size_-1];
}
constexpr const_reference back() const noexcept
{
CHECKSIZE(size_>0);
return storage_[size_-1];
}
constexpr pointer data() noexcept
{
return storage_.data();
}
constexpr const_pointer data() const noexcept
{
return storage_.data();
}
constexpr size_type size() const noexcept
{
return size_;
}
constexpr bool empty() const noexcept
{
return size_==0;
}
static constexpr size_type capacity() noexcept
{
return n;
}
static constexpr size_type max_size() noexcept
{
return n;
}
constexpr void fill(const value_type& value)
noexcept(std::is_nothrow_copy_assignable_v<value_type>)
{
for (size_type i=0; i<size(); ++i)
storage_[i] = value;
}
void swap(ReservedVector& other)
noexcept(std::is_nothrow_swappable_v<value_type>)
{
using std::swap;
swap(storage_, other.storage_);
swap(size_, other.size_);
}
friend std::ostream& operator<< (std::ostream& s, const ReservedVector& v)
{
for (size_type i=0; i<v.size(); i++)
s << v[i] << " ";
return s;
}
inline friend std::size_t hash_value(const ReservedVector& v) noexcept
{
return hash_range(v.storage_.data(),v.storage_.data()+v.size_);
}
private:
storage_type storage_;
size_type size_;
};
}
DUNE_DEFINE_HASH(DUNE_HASH_TEMPLATE_ARGS(typename T, int n),DUNE_HASH_TYPE(Dune::ReservedVector<T,n>))
#undef CHECKSIZE
#endif // DUNE_COMMON_RESERVEDVECTOR_HH
algorithm.hh
compare.hh
This file provides some concepts introduced in the C++20 standard library <compare> and <concepts> no...
hash.hh
Support for calculating hash values of objects.
DUNE_DEFINE_HASH
#define DUNE_DEFINE_HASH(template_args, type)
Defines the required struct specialization to make type hashable via Dune::hash.
Definition hash.hh:100
DUNE_HASH_TYPE
#define DUNE_HASH_TYPE(...)
Wrapper macro for the type to be hashed in DUNE_DEFINE_HASH.
Definition hash.hh:117
DUNE_HASH_TEMPLATE_ARGS
#define DUNE_HASH_TEMPLATE_ARGS(...)
Wrapper macro for the template arguments in DUNE_DEFINE_HASH.
Definition hash.hh:109
CHECKSIZE
#define CHECKSIZE(X)
Definition reservedvector.hh:27
std
STL namespace.
Dune
Dune namespace
Definition alignedallocator.hh:13
Dune::hash_range
std::size_t hash_range(It first, It last)
Hashes all elements in the range [first,last) and returns the combined hash.
Definition hash.hh:322
Dune::Std::lexicographical_compare_three_way
constexpr auto lexicographical_compare_three_way(I1 f1, I1 l1, I2 f2, I2 l2, Cmp comp={}) -> decltype(comp(*f1, *f2))
Lexicographically compares two ranges [first1, last1) and [first2, last2) using three-way comparison ...
Definition algorithm.hh:37
Dune::ReservedVector
A Vector class with statically reserved memory.
Definition reservedvector.hh:49
Dune::ReservedVector::front
constexpr const_reference front() const noexcept
Returns const reference to first element of vector.
Definition reservedvector.hh:324
Dune::ReservedVector::crend
constexpr const_reverse_iterator crend() const noexcept
Returns a const reverse-iterator pointing to the begin of the vector.
Definition reservedvector.hh:277
Dune::ReservedVector::ReservedVector
constexpr ReservedVector(size_type count) noexcept(std::is_nothrow_default_constructible_v< value_type >)
Constructs the vector with count elements that will be default-initialized.
Definition reservedvector.hh:91
Dune::ReservedVector::fill
constexpr void fill(const value_type &value) noexcept(std::is_nothrow_copy_assignable_v< value_type >)
Fill the container with the value.
Definition reservedvector.hh:389
Dune::ReservedVector::pointer
storage_type::pointer pointer
Pointer to T.
Definition reservedvector.hh:59
Dune::ReservedVector::rbegin
constexpr reverse_iterator rbegin() noexcept
Returns a const reverse-iterator pointing to the end of the vector.
Definition reservedvector.hh:229
Dune::ReservedVector::rend
constexpr const_reverse_iterator rend() const noexcept
Returns a const reverse-iterator pointing to the begin of the vector.
Definition reservedvector.hh:271
Dune::ReservedVector::max_size
static constexpr size_type max_size() noexcept
Returns the maximum length of the vector.
Definition reservedvector.hh:379
Dune::ReservedVector::at
constexpr const_reference at(size_type i) const
Returns a const reference to the i'th element.
Definition reservedvector.hh:295
Dune::ReservedVector::reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
Reverse iterator.
Definition reservedvector.hh:75
Dune::ReservedVector::end
constexpr iterator end() noexcept
Returns an iterator pointing to the end of the vector.
Definition reservedvector.hh:247
Dune::ReservedVector::size
constexpr size_type size() const noexcept
Returns number of elements in the vector.
Definition reservedvector.hh:361
Dune::ReservedVector::empty
constexpr bool empty() const noexcept
Returns true if vector has no elements.
Definition reservedvector.hh:367
Dune::ReservedVector::begin
constexpr iterator begin() noexcept
Returns a iterator pointing to the beginning of the vector.
Definition reservedvector.hh:211
Dune::ReservedVector::push_back
constexpr void push_back(const value_type &t) noexcept(std::is_nothrow_copy_assignable_v< value_type >)
Appends an element to the end of a vector, up to the maximum size n, O(1) time.
Definition reservedvector.hh:168
Dune::ReservedVector::rend
constexpr reverse_iterator rend() noexcept
Returns a const reverse-iterator pointing to the begin of the vector.
Definition reservedvector.hh:265
Dune::ReservedVector::iterator
storage_type::iterator iterator
Iterator used to iterate through a vector.
Definition reservedvector.hh:71
Dune::ReservedVector::cbegin
constexpr const_iterator cbegin() const noexcept
Returns a const_iterator pointing to the beginning of the vector.
Definition reservedvector.hh:223
Dune::ReservedVector::const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
Const reverse iterator.
Definition reservedvector.hh:77
Dune::ReservedVector::data
constexpr pointer data() noexcept
Returns pointer to the underlying memory.
Definition reservedvector.hh:345
Dune::ReservedVector::back
constexpr const_reference back() const noexcept
Returns const reference to last element of vector.
Definition reservedvector.hh:338
Dune::ReservedVector::operator<<
friend std::ostream & operator<<(std::ostream &s, const ReservedVector &v)
Send ReservedVector to an output stream.
Definition reservedvector.hh:408
Dune::ReservedVector::operator==
constexpr bool operator==(const ReservedVector &that) const noexcept
Compares the values in the vector this with that for equality.
Definition reservedvector.hh:134
Dune::ReservedVector::pop_back
constexpr void pop_back() noexcept
Erases the last element of the vector, O(1) time.
Definition reservedvector.hh:201
Dune::ReservedVector::hash_value
friend std::size_t hash_value(const ReservedVector &v) noexcept
Definition reservedvector.hh:415
Dune::ReservedVector::difference_type
storage_type::difference_type difference_type
A signed integral type.
Definition reservedvector.hh:69
Dune::ReservedVector::end
constexpr const_iterator end() const noexcept
Returns a const_iterator pointing to the end of the vector.
Definition reservedvector.hh:253
Dune::ReservedVector::clear
constexpr void clear() noexcept
Erases all elements.
Definition reservedvector.hh:155
Dune::ReservedVector::ReservedVector
constexpr ReservedVector() noexcept(std::is_nothrow_default_constructible_v< value_type >)
Constructs an empty vector.
Definition reservedvector.hh:84
Dune::ReservedVector::const_iterator
storage_type::const_iterator const_iterator
Const iterator used to iterate through a vector.
Definition reservedvector.hh:73
Dune::ReservedVector::emplace_back
reference emplace_back(Args &&... args) noexcept(std::is_nothrow_constructible_v< value_type, decltype(args)... >)
Appends an element to the end of a vector by constructing it in place.
Definition reservedvector.hh:185
Dune::ReservedVector::size_type
storage_type::size_type size_type
An unsigned integral type.
Definition reservedvector.hh:67
Dune::ReservedVector::const_reference
storage_type::const_reference const_reference
Const reference to T.
Definition reservedvector.hh:65
Dune::ReservedVector::swap
void swap(ReservedVector &other) noexcept(std::is_nothrow_swappable_v< value_type >)
Swap the content with another vector.
Definition reservedvector.hh:397
Dune::ReservedVector::ReservedVector
constexpr ReservedVector(InputIt first, InputIt last) noexcept(std::is_nothrow_copy_assignable_v< value_type > &&noexcept(ReservedVector()))
Constructs the vector from an iterator range [first,last).
Definition reservedvector.hh:112
Dune::ReservedVector::data
constexpr const_pointer data() const noexcept
Returns const pointer to the underlying memory.
Definition reservedvector.hh:351
Dune::ReservedVector::at
constexpr reference at(size_type i)
Returns reference to the i'th element.
Definition reservedvector.hh:287
Dune::ReservedVector::cend
constexpr const_iterator cend() const noexcept
Returns a const_iterator pointing to the end of the vector.
Definition reservedvector.hh:259
Dune::ReservedVector::operator<=>
constexpr auto operator<=>(const ReservedVector &that) const noexcept
Lexicographically compares the values in the vector this with that.
Definition reservedvector.hh:145
Dune::ReservedVector::back
constexpr reference back() noexcept
Returns reference to last element of vector.
Definition reservedvector.hh:331
Dune::ReservedVector::rbegin
constexpr const_reverse_iterator rbegin() const noexcept
Returns a const reverse-iterator pointing to the end of the vector.
Definition reservedvector.hh:235
Dune::ReservedVector::value_type
storage_type::value_type value_type
The type of object, T, stored in the vector.
Definition reservedvector.hh:57
Dune::ReservedVector::begin
constexpr const_iterator begin() const noexcept
Returns a const_iterator pointing to the beginning of the vector.
Definition reservedvector.hh:217
Dune::ReservedVector::ReservedVector
constexpr ReservedVector(size_type count, const value_type &value) noexcept(std::is_nothrow_copy_assignable_v< value_type > &&noexcept(ReservedVector(count)))
Constructs the vector with count copies of elements with value value.
Definition reservedvector.hh:100
Dune::ReservedVector::operator[]
constexpr reference operator[](size_type i) noexcept
Returns reference to the i'th element.
Definition reservedvector.hh:303
Dune::ReservedVector::front
constexpr reference front() noexcept
Returns reference to first element of vector.
Definition reservedvector.hh:317
Dune::ReservedVector::const_pointer
storage_type::const_pointer const_pointer
Const pointer to T.
Definition reservedvector.hh:61
Dune::ReservedVector::ReservedVector
constexpr ReservedVector(std::initializer_list< value_type > const &l) noexcept(std::is_nothrow_copy_assignable_v< value_type > &&noexcept(ReservedVector(l.begin(), l.end())))
Constructs the vector from an initializer list.
Definition reservedvector.hh:123
Dune::ReservedVector::resize
constexpr void resize(size_type s) noexcept
Specifies a new size for the vector.
Definition reservedvector.hh:161
Dune::ReservedVector::capacity
static constexpr size_type capacity() noexcept
Returns current capacity (allocated memory) of the vector.
Definition reservedvector.hh:373
Dune::ReservedVector::reference
storage_type::reference reference
Reference to T.
Definition reservedvector.hh:63
Dune::ReservedVector::crbegin
constexpr const_reverse_iterator crbegin() const noexcept
Returns a const reverse-iterator pointing to the end of the vector.
Definition reservedvector.hh:241
Dune::ReservedVector::push_back
constexpr void push_back(value_type &&t) noexcept(std::is_nothrow_move_assignable_v< value_type >)
Appends an element to the end of a vector by moving the value, up to the maximum size n,...
Definition reservedvector.hh:176