sfl::devector

Table of Contents

Summary
Template Parameters
Public Member Types
Public Member Functions
- (constructor)
- (destructor)
- assign
- assign_range
- operator=
- get_allocator
- begin, cbegin
- end, cend
- rbegin, crbegin
- rend, crend
- nth
- index_of
- empty
- size
- max_size
- capacity
- available_front
- available_back
- reserve_front
- reserve_back
- shrink_to_fit
- at
- operator[]
- front
- back
- data
- clear
- emplace
- insert
- insert_range
- emplace_front
- emplace_back
- push_front
- push_back
- prepend_range
- append_range
- pop_front
- pop_back
- erase
- resize
- resize_front
- resize_back
- swap
Non-member Functions
- operator==
- operator!=
- operator<
- operator>
- operator<=
- operator>=
- swap
- erase
- erase_if
Deduction Guides (since C++17)

Summary

Defined in header sfl/devector.hpp:

namespace sfl
{
    template < typename T,
               typename Allocator = std::allocator<T> >
    class devector;
}

sfl::devector (double-ended vector) is a sequence container similar to std::vector with slightly different underlying storage that allows fast insertion and deletion at both its beginning and its end.

sfl::devector has member functions push_front and pop_front that allow fast insertion and deletion at the beginning of the container. Other member function like emplace, insert and erase also allow faster insertion and deletion at the beginning of the container than it is in case of std::vector.

Elements of sfl::devector are always stored contiguously in the memory.

sfl::devector is not specialized for bool.

sfl::devector meets the requirements of Container, AllocatorAwareContainer, ReversibleContainer, ContiguousContainer and SequenceContainer.

Template Parameters

```
typename T
```
The type of the elements.
```
typename Allocator
```
Allocator used for memory allocation/deallocation and construction/destruction of elements.

This type must meet the requirements of Allocator.

The program is ill-formed if Allocator::value_type is not the same as T.

Public Member Types

Member Type	Definition
`allocator_type`	`Allocator`
`allocator_traits`	`std::allocator_traits<Allocator>`
`value_type`	`T`
`size_type`	`typename allocator_traits::size_type`
`difference_type`	`typename allocator_traits::difference_type`
`reference`	`T&`
`const_reference`	`const T&`
`pointer`	`typename allocator_traits::pointer`
`const_pointer`	`typename allocator_traits::const_pointer`
`iterator`	LegacyRandomAccessIterator and LegacyContiguousIterator to `value_type`
`const_iterator`	LegacyRandomAccessIterator and LegacyContiguousIterator to `const value_type`
`reverse_iterator`	`std::reverse_iterator<iterator>`
`const_reverse_iterator`	`std::reverse_iterator<const_iterator>`

Public Member Functions

(constructor)

```
devector() noexcept;
```

explicit devector(const Allocator& alloc)
    noexcept(std::is_nothrow_copy_constructible<Allocator>::value);

Effects: Constructs an empty container.

Complexity: Constant.

```
devector(size_type n);
```
```
explicit devector(size_type n, const Allocator& alloc);
```
Effects: Constructs the container with n default-constructed elements.

Complexity: Linear in n.
```
devector(size_type n, const T& value);
```
```
devector(size_type n, const T& value, const Allocator& alloc);
```
Effects: Constructs the container with n copies of elements with value value.

Complexity: Linear in n.

template <typename InputIt>
devector(InputIt first, InputIt last);

```
template <typename InputIt>
devector(InputIt first, InputIt last, const Allocator& alloc);
```
Effects: Constructs the container with the contents of the range [first, last).

Note: This overload participates in overload resolution only if InputIt satisfies requirements of LegacyInputIterator.

Complexity: Linear in std::distance(first, last).

devector(std::initializer_list<T> ilist);

```
devector(std::initializer_list<T> ilist, const Allocator& alloc);
```
Effects: Constructs the container with the contents of the initializer list ilist.

Complexity: Linear in ilist.size().
```
devector(const devector& other);
```
```
devector(const devector& other, const Allocator& alloc);
```
Effects: Copy constructor. Constructs the container with the copy of the contents of other.

Complexity: Linear in other.size().
```
devector(devector&& other);
```
```
devector(devector&& other, const Allocator& alloc);
```
Effects: Move constructor. Constructs the container with the contents of other using move semantics.

other is not guaranteed to be empty after the move.

other is in a valid but unspecified state after the move.

Complexity: Constant in the best case. Linear in size in the worst case.

template <typename Range>
devector(sfl::from_range_t, Range&& range);

```
template <typename Range>
devector(sfl::from_range_t, Range&& range, const Allocator& alloc);
```
Effects: Constructs the container with the contents of range.

Note: It is available in C++11. In C++20 are used proper C++20 range concepts.

(destructor)

```
~devector();
```
Effects: Destructs the container. The destructors of the elements are called and the used storage is deallocated.

Complexity: Linear in size().

assign

```
void assign(size_type n, const T& value);
```
Effects: Replaces the contents of the container with n copies of value value.

Complexity: Linear in n.
```
template <typename InputIt>
void assign(InputIt first, InputIt last);
```
Effects: Replaces the contents of the container with the contents of the range [first, last).

Note: This overload participates in overload resolution only if InputIt satisfies requirements of LegacyInputIterator.

Note: The behavior is undefined if either first or last is an iterator into *this.

Complexity: Linear in std::distance(first, last).
```
void assign(std::initializer_list<T> ilist);
```
Effects: Replaces the contents of the container with the contents of the initializer list ilist.

Complexity: Linear in ilist.size().

assign_range

```
template <typename Range>
void assign_range(Range&& range);
```
Effects: Replaces the contents of the container with the contents of range.

Note: It is available in C++11. In C++20 are used proper C++20 range concepts.

operator=

```
devector& operator=(const devector& other);
```
Effects: Copy assignment operator. Replaces the contents with a copy of the contents of other.

Returns: *this().

Complexity: Linear in size.
```
devector& operator=(devector&& other);
```
Effects: Move assignment operator. Replaces the contents with those of other using move semantics.

other is not guaranteed to be empty after the move.

other is in a valid but unspecified state after the move.

Returns: *this().

Complexity: Constant in the best case. Linear in size in the worst case.
```
devector& operator=(std::initializer_list<T> ilist);
```
Effects: Replaces the contents with those identified by initializer list ilist.

Returns: *this().

Complexity: Linear in size.

get_allocator

```
allocator_type get_allocator() const noexcept;
```
Effects: Returns the allocator associated with the container.

Complexity: Constant.

begin, cbegin

```
iterator begin() noexcept;
```
```
const_iterator begin() const noexcept;
```
```
const_iterator cbegin() const noexcept;
```
Effects: Returns an iterator to the first element of the container. If the container is empty, the returned iterator will be equal to end().

Complexity: Constant.

end, cend

```
iterator end() noexcept;
```
```
const_iterator end() const noexcept;
```
```
const_iterator cend() const noexcept;
```
Effects: Returns an iterator to the element following the last element of the container. This element acts as a placeholder; attempting to access it results in undefined behavior.

Complexity: Constant.

rbegin, crbegin

```
reverse_iterator rbegin() noexcept;
```

const_reverse_iterator rbegin() const noexcept;

```
const_reverse_iterator crbegin() const noexcept;
```
Effects: Returns a reverse iterator to the first element of the reversed container. It corresponds to the last element of the non-reversed container. If the container is empty, the returned iterator is equal to rend().

Complexity: Constant.

rend, crend

```
reverse_iterator rend() noexcept;
```

const_reverse_iterator rend() const noexcept;

```
const_reverse_iterator crend() const noexcept;
```
Effects: Returns a reverse iterator to the element following the last element of the reversed container. It corresponds to the element preceding the first element of the non-reversed container. This element acts as a placeholder, attempting to access it results in undefined behavior.

Complexity: Constant.

nth

```
iterator nth(size_type pos) noexcept;
```
```
const_iterator nth(size_type pos) const noexcept;
```
Preconditions: pos <= size()

Effects: Returns an iterator to the element at position pos.

If pos == size(), the returned iterator is equal to end().

Complexity: Constant.

index_of

```
size_type index_of(const_iterator pos) const noexcept;
```
Preconditions: cbegin() <= pos && pos <= cend()

Effects: Returns position of the element pointed by iterator pos, i.e. std::distance(begin(), pos).

If pos == end(), the returned value is equal to size().

Complexity: Constant.

empty

```
bool empty() const noexcept;
```
Effects: Returns true if the container has no elements, i.e. whether begin() == end().

Complexity: Constant.

size

```
size_type size() const noexcept;
```
Effects: Returns the number of elements in the container, i.e. std::distance(begin(), end()).

Complexity: Constant.

max_size

```
size_type max_size() const noexcept;
```
Effects: Returns the maximum number of elements the container is able to hold, i.e. std::distance(begin(), end()) for the largest container.

Complexity: Constant.

capacity

```
size_type capacity() const noexcept;
```
Effects: Returns the number of elements that the container has currently allocated space for.

Complexity: Constant.

available_front

```
size_type available() const noexcept;
```
Effects: Returns the number of elements that can be pushed to the front without requiring allocation of additional memory.

Complexity: Constant.

available_back

```
size_type available() const noexcept;
```
Effects: Returns the number of elements that can be pushed to the back without requiring allocation of additional memory.

Complexity: Constant.

reserve_front

```
void reserve_front(size_type new_capacity);
```
Effects: Ensures that n elements can be pushed to the front without requiring allocation of additional memory, where n is new_capacity - size(). Otherwise, there are no effects.

This function does not change size of the container.

If the capacity is changed, all iterators to the elements are invalidated, but references and pointers to elements remain valid. Otherwise, no iterators or references are invalidated.

Complexity: Linear.

Exceptions:
- Allocator::allocate may throw.
- T's move or copy constructor may throw.
If an exception is thrown:
- If type T has available noexcept move constructor:
  - This function has no effects (strong exception guarantee).
- Else if type T has available copy constructor:
  - This function has no effects (strong exception guarantee).
- Else if type T has available throwing move constructor:
  - Container is changed but in valid state (basic exception guarantee).

reserve_back

```
void reserve_back(size_type new_capacity);
```
Effects: Ensures that n elements can be pushed to the back without requiring allocation of additional memory, where n is new_capacity - size(). Otherwise, there are no effects.

This function does not change size of the container.

If the capacity is changed, all iterators to the elements are invalidated, but references and pointers to elements remain valid. Otherwise, no iterators or references are invalidated.

Complexity: Linear.

Exceptions:
- Allocator::allocate may throw.
- T's move or copy constructor may throw.
If an exception is thrown:
- If type T has available noexcept move constructor:
  - This function has no effects (strong exception guarantee).
- Else if type T has available copy constructor:
  - This function has no effects (strong exception guarantee).
- Else if type T has available throwing move constructor:
  - Container is changed but in valid state (basic exception guarantee).

shrink_to_fit

```
void shrink_to_fit();
```
Effects: If size() < capacity(), the function allocates memory for new storage of capacity equal to the value of size(), moves elements from old storage to new storage, and deallocates memory used by old storage. Otherwise, the function does nothing.

This function does not change size of the container.

If the capacity is changed, all iterators and all references to the elements are invalidated. Otherwise, no iterators or references are invalidated.

Complexity: Linear.

Exceptions:
- Allocator::allocate may throw.
- T's move or copy constructor may throw.
If an exception is thrown:
- If type T has available noexcept move constructor:
  - This function has no effects (strong exception guarantee).
- Else if type T has available copy constructor:
  - This function has no effects (strong exception guarantee).
- Else if type T has available throwing move constructor:
  - Container is changed but in valid state (basic exception guarantee).

at

```
reference at(size_type pos);
```
```
const_reference at(size_type pos) const;
```
Effects: Returns a reference to the element at specified location pos, with bounds checking.

Complexity: Constant.

Exceptions: std::out_of_range if pos >= size().

operator[]

reference operator[](size_type pos) noexcept;

```
const_reference operator[](size_type pos) const noexcept;
```
Preconditions: pos < size()

Effects: Returns a reference to the element at specified location pos. No bounds checking is performed.

Note: This operator never inserts a new element into the container.

Complexity: Constant.

front

```
reference front() noexcept;
```
```
const_reference front() const noexcept;
```
Preconditions: !empty()

Effects: Returns a reference to the first element in the container.

Complexity: Constant.

back

```
reference back() noexcept;
```
```
const_reference back() const noexcept;
```
Preconditions: !empty()

Effects: Returns a reference to the last element in the container.

Complexity: Constant.

data

```
T* data() noexcept;
```
```
const T* data() const noexcept;
```
Effects: Returns pointer to the underlying array serving as element storage. The pointer is such that range [data(), data() + size()) is always a valid range, even if the container is empty. data() is not dereferenceable if the container is empty.

Complexity: Constant.

clear

```
void clear() noexcept;
```
Effects: Erases all elements from the container. After this call, size() returns zero and capacity() remains unchanged.

Complexity: Linear in size().

emplace

```
template <typename... Args>
iterator emplace(const_iterator pos, Args&&... args);
```
Preconditions: cbegin() <= pos && pos <= cend()

Effects: Inserts a new element into the container at position pos.

New element is constructed as value_type(std::forward<Args>(args)...).

args... may directly or indirectly refer to a value in the container.

Returns: Iterator to the inserted element.

Complexity: Constant plus linear in std::min(std::distance(begin(), pos), std::distance(pos, end())).

insert

```
iterator insert(const_iterator pos, const T& value);
```
Preconditions: cbegin() <= pos && pos <= cend()

Effects: Inserts copy of value at position pos.

Returns: Iterator to the inserted element.

Complexity: Constant plus linear in std::min(std::distance(begin(), pos), std::distance(pos, end())).
```
iterator insert(const_iterator pos, T&& value);
```
Preconditions: cbegin() <= pos && pos <= cend()

Effects: Inserts value using move semantics at position pos.

Returns: Iterator to the inserted element.

Complexity: Constant plus linear in std::min(std::distance(begin(), pos), std::distance(pos, end())).
```
iterator insert(const_iterator pos, size_type n, const T& value);
```
Preconditions: cbegin() <= pos && pos <= cend()

Effects: Inserts n copies of value before position pos.

Returns: Iterator to the first element inserted, or pos if n == 0.

Complexity: Constant plus linear in std::min(std::distance(begin(), pos), std::distance(pos, end())).
```
template <typename InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last);
```
Preconditions: cbegin() <= pos && pos <= cend()

Effects: Inserts elements from the range [first, last) before position pos.

Note: This overload participates in overload resolution only if InputIt satisfies requirements of LegacyInputIterator.

Note: The behavior is undefined if either first or last is an iterator into *this.

Returns: Iterator to the first element inserted, or pos if first == last.

Complexity: Linear in std::distance(first, last) plus linear in std::min(std::distance(begin(), pos), std::distance(pos, end())).
```
iterator insert(const_iterator pos, std::initializer_list<T> ilist);
```
Preconditions: cbegin() <= pos && pos <= cend()

Effects: Inserts elements from initializer list ilist before position pos.

Returns: Iterator to the first element inserted, or pos if ilist is empty.

Complexity: Linear in ilist.size() plus linear in std::min(std::distance(begin(), pos), std::distance(pos, end())).

insert_range

```
template <typename Range>
iterator insert_range(const_iterator pos, Range&& range);
```
Effects: Inserts elements from range before position pos. Elements are inserted in non-reversing order.

range must not overlap with the container. Otherwise, the behavior is undefined.

Returns: Iterator to the first element inserted, or pos if range is empty.

Note: It is available in C++11. In C++20 are used proper C++20 range concepts.

emplace_front

```
template <typename... Args>
reference emplace_front(Args&&... args);
```
Effects: Inserts a new element at the beginning of container.

New element is constructed as value_type(std::forward<Args>(args)...).

args... may directly or indirectly refer to a value in the container.

Returns: Reference to the inserted element.

Complexity: Constant.

emplace_back

```
template <typename... Args>
reference emplace_back(Args&&... args);
```
Effects: Inserts a new element at the end of container.

New element is constructed as value_type(std::forward<Args>(args)...).

args... may directly or indirectly refer to a value in the container.

Returns: Reference to the inserted element.

Complexity: Constant.

push_front

```
void push_front(const T& value);
```
Effects: Inserts copy of value at the beginning of container.

Complexity: Constant.
```
void push_front(T&& value);
```
Effects: Inserts value using move semantics at the beginning of container.

Complexity: Constant.

push_back

```
void push_back(const T& value);
```
Effects: Inserts copy of value at the end of container.

Complexity: Constant.
```
void push_back(T&& value);
```
Effects: Inserts value using move semantics at the end of container.

Complexity: Constant.

prepend_range

```
template <typename Range>
void prepend_range(Range&& range);
```
Effects: Inserts elements from range before begin(). Elements are inserted in non-reversing order.

Note: It is available in C++11. In C++20 are used proper C++20 range concepts.

append_range

```
template <typename Range>
void append_range(Range&& range);
```
Effects: Inserts elements from range before end(). Elements are inserted in non-reversing order.

Note: It is available in C++11. In C++20 are used proper C++20 range concepts.

pop_front

```
void pop_front();
```
Preconditions: !empty()

Effects: Removes the first element of the container.

Complexity: Constant.

pop_back

```
void pop_back();
```
Preconditions: !empty()

Effects: Removes the last element of the container.

Complexity: Constant.

erase

```
iterator erase(const_iterator pos);
```
Preconditions: cbegin() <= pos && pos < cend()

Effects: Removes the element at pos.

Returns: Iterator following the last removed element.

If pos refers to the last element, then the end() iterator is returned.
```
iterator erase(const_iterator first, const_iterator last);
```
Preconditions: cbegin() <= first && first <= last && last <= cend()

Effects: Removes the elements in the range [first, last).

Returns: Iterator following the last removed element.

If last == end() prior to removal, then the updated end() iterator is returned.

If [first, last) is an empty range, then last is returned.

resize

```
void resize(size_type n);
```
Effects: Resizes the container to contain n elements.
1. If the size() > n, the last size() - n elements are removed.
2. If the size() < n, additional default-constructed elements are inserted into container. Additional elements could be inserted both at the beginning and at the end of container.
```
void resize(size_type n, const T& value);
```
Effects: Resizes the container to contain n elements.
1. If the size() > n, the last size() - n elements are removed.
2. If the size() < n, additional copies of value are inserted into container. Additional elements could be inserted both at the beginning and at the end of container.

resize_front

```
void resize_front(size_type n);
```
Effects: Resizes the container to contain n elements.
1. If the size() > n, the first size() - n elements are removed.
2. If the size() < n, additional default-constructed elements are inserted at the beginning of container.
```
void resize_front(size_type n, const T& value);
```
Effects: Resizes the container to contain n elements.
1. If the size() > n, the first size() - n elements are removed.
2. If the size() < n, additional copies of value are inserted at the beginning of container.

resize_back

```
void resize_back(size_type n);
```
Effects: Resizes the container to contain n elements.
1. If the size() > n, the last size() - n elements are removed.
2. If the size() < n, additional default-constructed elements are inserted at the end of container.
```
void resize_back(size_type n, const T& value);
```
Effects: Resizes the container to contain n elements.
1. If the size() > n, the last size() - n elements are removed.
2. If the size() < n, additional copies of value are inserted at the end of container.

swap

```
void swap(devector& other);
```
Preconditions: allocator_traits::propagate_on_container_swap::value || get_allocator() == other.get_allocator()

Effects: Exchanges the contents of the container with those of other.

Complexity: Constant.

Non-member Functions

operator==

```
template <typename T, typename A>
bool operator==
(
    const devector<T, A>& x,
    const devector<T, A>& y
);
```
Effects: Checks if the contents of x and y are equal.

The contents of x and y are equal if the following conditions hold:
- x.size() == y.size()
- Each element in x compares equal with the element in y at the same position.
Returns: true if the contents of the x and y are equal, false otherwise.

Complexity: Constant if x and y are of different size, otherwise linear in the size of the container.

operator!=

```
template <typename T, typename A>
bool operator!=
(
    const devector<T, A>& x,
    const devector<T, A>& y
);
```
Effects: Checks if the contents of x and y are equal.

For details see operator==.

Returns: true if the contents of the x and y are not equal, false otherwise.

Complexity: Constant if x and y are of different size, otherwise linear in the size of the container.

operator<

```
template <typename T, typename A>
bool operator<
(
    const devector<T, A>& x,
    const devector<T, A>& y
);
```
Effects: Compares the contents of x and y lexicographically. The comparison is performed by a function std::lexicographical_compare.

Returns: true if the contents of the x are lexicographically less than the contents of y, false otherwise.

Complexity: Linear in the size of the container.

operator>

```
template <typename T, typename A>
bool operator>
(
    const devector<T, A>& x,
    const devector<T, A>& y
);
```
Effects: Compares the contents of x and y lexicographically. The comparison is performed by a function std::lexicographical_compare.

Returns: true if the contents of the x are lexicographically greater than the contents of y, false otherwise.

Complexity: Linear in the size of the container.

operator<=

```
template <typename T, typename A>
bool operator<=
(
    const devector<T, A>& x,
    const devector<T, A>& y
);
```
Effects: Compares the contents of x and y lexicographically. The comparison is performed by a function std::lexicographical_compare.

Returns: true if the contents of the x are lexicographically less than or equal to the contents of y, false otherwise.

Complexity: Linear in the size of the container.

operator>=

```
template <typename T, typename A>
bool operator>=
(
    const devector<T, A>& x,
    const devector<T, A>& y
);
```
Effects: Compares the contents of x and y lexicographically. The comparison is performed by a function std::lexicographical_compare.

Returns: true if the contents of the x are lexicographically greater than or equal to the contents of y, false otherwise.

Complexity: Linear in the size of the container.

swap

template <typename T, typename A>
void swap
(
    devector<T, A>& x,
    devector<T, A>& y
);

Effects: Swaps the contents of x and y. Calls x.swap(y).

erase

```
template <typename T, typename A, typename U>
typename devector<T, A>::size_type
    erase(devector<T, A>& c, const U& value);
```
Effects: Erases all elements that compare equal to value from the container.

Returns: The number of erased elements.

Complexity: Linear.

erase_if

```
template <typename T, typename A, typename Predicate>
typename devector<T, A>::size_type
    erase_if(devector<T, A>& c, Predicate pred);
```
Effects: Erases all elements that satisfy the predicate pred from the container.

pred is unary predicate which returns true if the element should be removed.

Returns: The number of erased elements.

Complexity: Linear.

Deduction Guides (since C++17)

template < typename InputIt,
           typename Allocator = std::allocator<
               typename std::iterator_traits<InputIt>::value_type> >
devector(InputIt, InputIt, Allocator = Allocator())
    -> devector<typename std::iterator_traits<InputIt>::value_type, Allocator>;

Effects: Deduction from an iterator range.

Note: This overload participates in overload resolution only if InputIt satisfies requirements of LegacyInputIterator.

End of document.

Files

devector.md

Latest commit

History

devector.md

File metadata and controls

sfl::devector

Summary

Template Parameters

Public Member Types

Public Member Functions

(constructor)

(destructor)

assign

assign_range

operator=

get_allocator

begin, cbegin

end, cend

rbegin, crbegin

rend, crend

nth

index_of

empty

size

max_size

capacity

available_front

available_back

reserve_front

reserve_back

shrink_to_fit

at

operator[]

front

back

data

clear

emplace

insert

insert_range

emplace_front

emplace_back

push_front

push_back

prepend_range

append_range

pop_front

pop_back

erase

resize

resize_front

resize_back

swap

Non-member Functions

operator==

operator!=

operator<

operator>

operator<=

operator>=

swap

erase

erase_if

Deduction Guides (since C++17)