Template Class sorted

Class Documentation

template<class Container, class Compare = std::less<typename Container::value_type>>
class util::sorted

A container of elements that are kept sorted.

    const util::sorted_vector<int> numbers = {3, 1, 2};
    assert(numbers.at(0) == 1);
    assert(numbers.at(1) == 2);
    assert(numbers.at(2) == 3);
tparam Container

the type of container to keep sorted

tparam Compare

A comparison function object which returns ​true if the first argument is less than (i.e. is ordered before) the second. The type must meet the requirements of Compare.

Public Types

using value_type = typename Container::value_type
using size_type = typename Container::size_type
using const_reference = const value_type&
using const_pointer = const value_type*
using const_iterator = typename Container::const_iterator
using is_forward_list = std::is_same<Container, std::forward_list<value_type, typename Container::allocator_type>>
using is_list = std::is_same<Container, std::list<value_type, typename Container::allocator_type>>

Public Functions

sorted() noexcept = default
~sorted() = default
sorted(const sorted&) = default
sorted(sorted&&) noexcept = default
auto operator=(const sorted&) -> sorted& = default
auto operator=(sorted&&) noexcept -> sorted& = default
template<class OtherContainer>
explicit sorted(const OtherContainer &container)

Constructs a sorted container from a given container of elements.

    std::vector<int> unsorted = {3, 1, 2};
    const util::sorted_vector<int> numbers(unsorted);
    assert(numbers.at(0) == 1);
    assert(numbers.at(1) == 2);
    assert(numbers.at(2) == 3);

Template Parameters

OtherContainer – the type of the container to insert, can be the same as the underlying container of this sorted container

Parameters

container – the container of elements to insert, must have begin() and end() methods returning input iterators

template<class InputIt>
sorted(InputIt begin, InputIt end)

Constructs a sorted container from a given range of elements to insert.

    auto unsorted = {3, 1, 2};
    const util::sorted_vector<int> numbers(std::begin(unsorted), std::end(unsorted));
    assert(numbers.at(0) == 1);
    assert(numbers.at(1) == 2);
    assert(numbers.at(2) == 3);

Template Parameters

InputIt – the type of the input iterator

Parameters

  • begin – the beginning iterator of the range of elements to insert

  • end – the iterator of the element one position after the last element

sorted(std::initializer_list<value_type> ilist)

Constructs a sorted container from a given initializer list.

    const util::sorted_vector<int> numbers = {3, 1, 2};
    assert(numbers.at(0) == 1);
    assert(numbers.at(1) == 2);
    assert(numbers.at(2) == 3);

Parameters

ilist – the list of elements to initalize the sorted container with

auto at(size_type pos) const -> const_reference

Returns a const reference to an element at the requested position with boundary checking.

    const util::sorted_vector<int> numbers = {3, 1, 2};
    assert(numbers.at(0) == 1);
    assert(numbers.at(1) == 2);
    assert(numbers.at(2) == 3);

Parameters

pos – the position of the element to return

Throws

out_of_range – if pos >= size()

Returns

a const reference to the element at the requested position

auto operator[](size_type pos) const -> const_reference

Returns a const reference to an element at the requested position without boundary checking. Undefined behaviour if accessing a position >= size().

    const util::sorted_vector<int> numbers = {3, 1, 2};
    assert(numbers[0] == 1);
    assert(numbers[1] == 2);
    assert(numbers[2] == 3);

Parameters

pos – the position of the element to return

Returns

a const reference to the element at the requested position

auto front() const -> const_reference
auto back() const -> const_reference
auto data() const noexcept -> const_pointer
auto begin() const noexcept -> const_iterator
auto cbegin() const noexcept -> const_iterator
auto end() const noexcept -> const_iterator
auto cend() const noexcept -> const_iterator
auto empty() const noexcept -> bool
auto size() const noexcept -> size_type

Returns the count of elements in this sorted container.

    util::sorted_vector<std::string> names;
    assert(names.size() == 0);
    names.insert("Chris");
    names.insert("Dora");
    assert(names.size() == 2);

Returns

the number of contained elements

auto max_size() const noexcept -> size_type
auto capacity() const noexcept -> size_type

Returns the current available allocated space for elements of this sorted container.

    util::sorted_vector<std::string> cities;
    assert(cities.capacity() == 0);
    cities.insert("Madrid");
    cities.insert("Prague");
    cities.insert("Vienna");
    assert(cities.capacity() >= 3);

void reserve(size_type new_cap)
void shrink_to_fit()
void resize(size_type count)
void resize(size_type count, const_reference value)
void clear() noexcept

Clears all elements from this sorted container.

Invalidates any references, pointers, or iterators referring to contained elements. Any past-the-end iterators are also invalidated, but leaves the capacity() of the container unchanged.

    util::sorted_vector<double> doubles({1, 2, 3});
    const auto cap = doubles.capacity();
    doubles.clear();
    assert(doubles.size() == 0);
    assert(doubles.capacity() == cap);

auto insert(const_reference value) -> const_iterator

Inserts an element into the sorted container.

In contrast to the normal container’s insert method, this insert does not take an additional position parameter. The position is determined by the sorting algorithm. The method invalidates any references, pointers, or iterators referring to contained elements. Any past-the-end iterators are also invalidated.

    util::sorted_vector<int> numbers({3, 1, 2});
    auto it = numbers.insert(0);
    assert(*it == 0);
    assert(numbers.at(0) == 0);
    assert(numbers.at(1) == 1);
    assert(numbers.at(2) == 2);
    assert(numbers.at(3) == 3);

Parameters

value – the element to insert

Returns

a const iterator to the inserted element

auto insert(value_type &&value) -> const_iterator

See

sorted<Container, Compare>::insert(const_reference value) -> const_iterator

auto insert(std::initializer_list<value_type> ilist) -> const_iterator
template<class InputIt>
void insert(InputIt first, InputIt last)
template<class ...Args>
auto emplace(Args&&... args) -> const_iterator
auto erase(const_iterator pos) -> const_iterator
auto erase(const_iterator first, const_iterator last) -> const_iterator
void pop_back()
void pop_front()
void swap(sorted &other)