map.hpp

Go to the documentation of this file.

 
 
#pragma once
 
#include "_avl.hpp"
#include "_avl_iterator.hpp"
 
#include <functional>
#include <iterator>
#include <memory>
#include <string>
#include <utility>
 
namespace datastructures {
 
template <class TKey, class TValue, class TKeyComp = std::less<TKey>,
          class TAlloc = std::allocator<std::pair<const TKey, TValue>>>
class map {
 
  public:
    // ==== Keys and values types ====
    using key_type = TKey;
    using mapped_type = TValue;
    using value_type = std::pair<const key_type, mapped_type>;
 
    using reference = value_type &;
    using const_reference = const value_type &;
 
    // ==== Comparisons types ====
 
    using key_compare = TKeyComp;
 
    struct value_compare {
      protected:
        friend class map;
        [[no_unique_address]] key_compare comp;
 
      public:
        value_compare(key_compare c) : comp(c) {}
 
        inline bool operator()(const value_type &a,
                               const value_type &b) const noexcept {
            return comp(a.first, b.first);
        }
 
        inline bool operator()(const key_type &a,
                               const value_type &b) const noexcept {
            return comp(a, b.first);
        }
 
        inline bool operator()(const value_type &a,
                               const key_type &b) const noexcept {
            return comp(a.first, b);
        }
 
        inline bool operator()(const key_type &a,
                               const key_type &b) const noexcept {
            return comp(a, b);
        }
    };
 
    // ==== Allocator and memory types ====
    using allocator_type = TAlloc;
    using alloc_traits = std::allocator_traits<allocator_type>;
    using size_type = typename alloc_traits::size_type;
    using difference_type = typename alloc_traits::difference_type;
 
    using pointer = typename alloc_traits::pointer;
    using const_pointer = typename alloc_traits::const_pointer;
 
  private:
    // ==== The Tree Type ====
 
    using tree_type =
        detail::avl_tree<key_type, value_type, value_compare, allocator_type>;
 
  public:
    // ==== Iterator types ====
    using iterator = detail::avl_iterator<tree_type, false>;
    using const_iterator = detail::avl_iterator<tree_type, true>;
 
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
  private:
    [[no_unique_address]] key_compare comparator;
    [[no_unique_address]] value_compare value_comparator;
 
    tree_type tree;
 
  public:
    // ==== Constructors & Assigments ====
    map();
 
    explicit map(const key_compare &comparator,
                 const allocator_type &allocator = allocator_type{});
 
    explicit map(const allocator_type &allocator);
 
    map(const map &other);
    map &operator=(const map &other);
 
    map(map &&other) noexcept;
    map &operator=(map &&other) noexcept;
 
    ~map() noexcept;
 
    // ==== Observers & Allocator getter ====
 
    [[nodiscard]] allocator_type get_allocator() const noexcept;
 
    [[nodiscard]] key_compare key_comp() const noexcept;
 
    [[nodiscard]] value_compare value_comp() const noexcept;
 
    // ==== Access Functions ====
 
    [[nodiscard]] mapped_type &at(const key_type &key);
 
    [[nodiscard]] const mapped_type &at(const key_type &key) const;
 
    mapped_type &operator[](const key_type &key);
 
    mapped_type &operator[](key_type &&key);
 
    [[nodiscard]] iterator find(const key_type &key) noexcept;
 
    [[nodiscard]] const_iterator find(const key_type &key) const noexcept;
 
    [[nodiscard]] bool contains(const key_type &key) const noexcept;
 
    [[nodiscard]] size_type count(const key_type &key) const noexcept;
 
    [[nodiscard]] iterator lower_bound(const key_type &key) noexcept;
 
    [[nodiscard]] const_iterator
    lower_bound(const key_type &key) const noexcept;
 
    [[nodiscard]] iterator upper_bound(const key_type &key) noexcept;
 
    [[nodiscard]] const_iterator
    upper_bound(const key_type &key) const noexcept;
 
    [[nodiscard]] std::pair<iterator, iterator>
    equal_range(const key_type &key) noexcept;
 
    [[nodiscard]] std::pair<const_iterator, const_iterator>
    equal_range(const key_type &key) const noexcept;
 
    // ==== Iterators ====
 
    [[nodiscard]] iterator begin() noexcept;
 
    [[nodiscard]] const_iterator begin() const noexcept;
 
    [[nodiscard]] const_iterator cbegin() const noexcept;
 
    [[nodiscard]] iterator end() noexcept;
 
    [[nodiscard]] const_iterator end() const noexcept;
 
    [[nodiscard]] const_iterator cend() const noexcept;
 
    [[nodiscard]] reverse_iterator rbegin() noexcept;
 
    [[nodiscard]] const_reverse_iterator rbegin() const noexcept;
 
    [[nodiscard]] const_reverse_iterator crbegin() const noexcept;
 
    [[nodiscard]] reverse_iterator rend() noexcept;
 
    [[nodiscard]] const_reverse_iterator rend() const noexcept;
 
    [[nodiscard]] const_reverse_iterator crend() const noexcept;
 
    // ==== Size Queries ====
 
    [[nodiscard]] bool empty() const noexcept;
 
    [[nodiscard]] size_type size() const noexcept;
 
    [[nodiscard]] int get_height() const noexcept;
 
    // ==== Update Operations ====
 
    void clear() noexcept;
 
    std::pair<iterator, bool> insert(const value_type &item);
 
    std::pair<iterator, bool> insert(value_type &&item);
 
    template <class TMapped>
    std::pair<iterator, bool> insert_or_assign(const key_type &key,
                                               TMapped &&value);
 
    template <class TMapped>
    std::pair<iterator, bool> insert_or_assign(key_type &&key, TMapped &&value);
 
    template <class... Args>
    std::pair<iterator, bool> try_emplace(const key_type &key, Args &&...args);
 
    template <class... Args>
    std::pair<iterator, bool> try_emplace(key_type &&key, Args &&...args);
 
    iterator erase(iterator pos) noexcept;
 
    iterator erase(const_iterator pos) noexcept;
 
    size_type erase(const key_type &key) noexcept;
 
    void swap(map &other) noexcept;
 
    // ==== Debug Functions ====
 
    std::string to_dot(bool print_invis) const;
};
 
} // namespace datastructures
 
// implementation
#include "map.ipp"