containers.h

Go to the documentation of this file.

/* *****************************************************************************
 * kblib is a general utility library for C++14 and C++17, intended to provide
 * performant high-level abstractions and more expressive ways to do simple
 * things.
 *
 * Copyright (c) 2021 killerbee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef KBLIB_CONTAINERS_H
#define KBLIB_CONTAINERS_H
 
#include "fakestd.h"
#include "iterators.h"
#include "tdecl.h"
#include "traits.h"
 
#include <cstddef>
#include <deque>
#include <iterator>
#include <memory>
#include <stack>
#include <type_traits>
#include <vector>
 
namespace KBLIB_NS {
 
template <typename C>
KBLIB_NODISCARD constexpr auto pop(C& s) -> typename C::value_type {
   typename C::value_type ret = std::move(s.top());
   s.pop();
   return ret;
}
 
template <class C, typename K, typename V>
KBLIB_NODISCARD constexpr auto get_or(const C& m, const K& key, const V& defval)
    -> typename C::mapped_type {
   auto it = m.find(key);
   if (it == m.end())
      return defval;
   else
      return it->second;
}
 
template <typename Map, typename Key>
KBLIB_NODISCARD constexpr auto try_get(Map& map, Key&& key)
    -> copy_const_t<Map, typename Map::mapped_type>* {
   auto it = map.find(std::forward<Key>(key));
   if (it == map.end())
      return nullptr;
   else
      return &it->second;
}
 
template <typename iterator>
struct exists_t {
   iterator it;
   bool found;
   KBLIB_NODISCARD constexpr operator bool() const noexcept { return found; }
   KBLIB_NODISCARD constexpr auto operator*() const noexcept(noexcept(*it))
       -> decltype(*it) {
      return *it;
   }
   KBLIB_NODISCARD constexpr auto operator->() const noexcept -> iterator {
      return it;
   }
   KBLIB_NODISCARD constexpr auto addr() const noexcept -> auto* {
      return to_pointer(it);
   }
};
 
template <typename M, typename K>
KBLIB_NODISCARD constexpr auto get_check(M&& m, const K& key) noexcept(
    noexcept(m.find(key) != m.end())) -> exists_t<decltype(m.find(key))> {
   auto it = m.find(key);
   return {it, it != m.end()};
}
 
template <typename V>
auto force_shrink_to_fit(V& vec) -> void {
   if (std::is_nothrow_move_constructible<typename V::value_type>::value) {
      V tmp;
      try_reserve(tmp, vec.size());
      std::move(vec.begin(), vec.end(), std::back_inserter(tmp));
      vec = std::move(tmp);
   } else {
      V tmp(vec.begin(), vec.end());
      vec = std::move(tmp);
   }
   return;
}
 
template <typename C, std::size_t size>
struct construct_with_size {
   KBLIB_NODISCARD constexpr static auto make() -> C { return C(size); }
};
 
template <typename C, std::size_t size>
struct construct_with_capacity {
   KBLIB_NODISCARD constexpr static auto make() -> C {
      C c;
      c.reserve(size);
      return c;
   }
};
 
template <typename Container, typename Range>
KBLIB_NODISCARD constexpr auto construct_from_range(Range&& r) -> Container {
   using std::begin;
   using std::end;
   return Container{begin(std::forward<Range>(r)), end(std::forward<Range>(r))};
}
 
template <typename Container, bool ArrayLike = not is_resizable_v<Container>>
class KBLIB_NODISCARD build_iterator {
 private:
   std::shared_ptr<Container> range;
 
 public:
   using value_type = void;
   using difference_type = void;
   using pointer = void;
   using reference = void;
   using iterator_category = std::output_iterator_tag;
 
   template <typename... Args>
   build_iterator(Args&&... args)
       : range(std::make_shared<Container>(std::forward<Args>(args)...)) {}
 
   KBLIB_NODISCARD constexpr auto base() noexcept(
       std::is_nothrow_move_constructible<Container>::value) -> Container {
      auto holder = std::move(range);
      return std::move(*holder);
   }
 
   KBLIB_NODISCARD constexpr explicit operator Container() noexcept(
       std::is_nothrow_move_constructible<Container>::value) {
      auto holder = std::move(range);
      return std::move(*holder);
   }
 
   KBLIB_NODISCARD constexpr auto operator*() const
       noexcept(noexcept(*std::back_inserter(*range))) -> decltype(auto) {
      return std::back_inserter(*range);
   }
 
   KBLIB_NODISCARD constexpr auto operator++() -> build_iterator& {
      return *this;
   }
   KBLIB_NODISCARD constexpr auto operator++(int) -> build_iterator& {
      return *this;
   }
};
 
KBLIB_UNUSED constexpr struct build_end_t {
   template <typename T>
   KBLIB_NODISCARD constexpr operator T() const
       noexcept(noexcept(T{std::declval<build_end_t&>()})) {
      return T{this};
   }
} build_end;
 
template <typename Container>
class KBLIB_NODISCARD build_iterator<Container, true> {
 public:
   using value_type = void;
   using difference_type = void;
   using pointer = void;
   using reference = void;
   using iterator_category = std::output_iterator_tag;
 
   template <typename... Args>
   build_iterator(Args&&... args)
       : range(std::make_shared<Container>(std::forward<Args>(args)...)) {}
 
   build_iterator(const build_end_t&)
       : range{nullptr}
       , index(std::tuple_size<Container>::value) {}
 
   KBLIB_NODISCARD auto base() noexcept(
       std::is_nothrow_move_constructible<Container>::value) -> Container {
      auto holder = std::move(range);
      return std::move(*holder);
   }
 
   KBLIB_NODISCARD explicit operator Container() noexcept(
       std::is_nothrow_move_constructible<Container>::value) {
      auto holder = std::move(range);
      return std::move(*holder);
   }
 
   KBLIB_NODISCARD auto operator*() const noexcept -> decltype(auto) {
      return (*range)[index];
   }
   KBLIB_NODISCARD auto operator->() const noexcept -> auto* {
      return &(*range)[index];
   }
 
   auto operator++() -> build_iterator& {
      ++index;
      return *this;
   }
   auto operator++(int) -> build_iterator& {
      auto tmp = *this;
      ++index;
      return tmp;
   }
 
   KBLIB_NODISCARD constexpr auto size() const noexcept -> std::size_t {
      return kblib::size(*range);
   }
 
   KBLIB_NODISCARD constexpr friend auto operator==(
       const build_iterator<Container>& it, build_end_t) noexcept -> bool {
      return it.index == it.size();
   }
   KBLIB_NODISCARD constexpr friend auto operator!=(
       const build_iterator<Container>& it, build_end_t) noexcept -> bool {
      return it.index != it.size();
   }
 
   KBLIB_NODISCARD constexpr friend auto operator==(
       build_end_t, const build_iterator<Container>& it) noexcept -> bool {
      return it.index == it.size();
   }
   KBLIB_NODISCARD constexpr friend auto operator!=(
       build_end_t, const build_iterator<Container>& it) noexcept -> bool {
      return it.index != it.size();
   }
 
   KBLIB_NODISCARD constexpr friend auto operator==(
       const build_iterator<Container>& it1,
       const build_iterator<Container>& it2) noexcept -> bool {
      return it1.index == it2.index;
   }
   KBLIB_NODISCARD constexpr friend auto operator!=(
       const build_iterator<Container>& it1,
       const build_iterator<Container>& it2) noexcept -> bool {
      return it1.index != it2.index;
   }
 
 private:
   std::shared_ptr<Container> range;
   std::size_t index{};
};
 
} // namespace KBLIB_NS
 
namespace std {
#if defined(__clang__)
// Because apparently -Wno-mismatched-tags doesn't work
#  pragma clang diagnostic push
#  pragma clang diagnostic ignored "-Wmismatched-tags"
#endif
 
template <typename C, std::size_t Size>
struct tuple_size<::kblib::construct_with_size<C, Size>>
    : public integral_constant<size_t, Size> {};
 
#if defined(__clang__)
#  pragma clang diagnostic pop
#endif
} // namespace std
 
namespace KBLIB_NS {
namespace detail {
 
   template <typename Container, std::size_t N>
   struct buildiota_impl<construct_with_size<Container, N>, false> {
      template <typename T>
      constexpr static auto impl(T value) -> Container {
         Container out = construct_with_size<Container, N>::make();
         for (auto& v : out) {
            v = value;
            ++value;
         }
         return out;
      }
      template <typename T, typename I>
      constexpr static auto impl(T value, I incr) -> Container {
         Container out = construct_with_size<Container, N>::make();
         for (auto& v : out) {
            v = value;
            value += incr;
         }
         return out;
      }
   };
 
} // namespace detail
 
template <typename T, typename Container = std::vector<T>>
class [[deprecated("use a class derived from std::stack instead")]] stack {
 public:
   // Member types
 
   using container_type = Container;
   using value_type = typename Container::value_type;
   using size_type = typename Container::size_type;
   using reference = typename Container::reference;
   using const_reference = typename Container::const_reference;
 
   static_assert(std::is_same<T, value_type>::value,
                 "Container::value_type must be T.");
 
 private:
   container_type backing;
 
 public:
   // Constructors
 
   stack()
       : stack(Container()) {}
   explicit stack(const Container& cont)
       : backing(cont) {}
 
   template <typename Alloc,
             typename std::enable_if<
                 std::uses_allocator<container_type, Alloc>::value, int>::type
             = 0>
   explicit stack(const Alloc& alloc);
   template <typename Alloc,
             typename std::enable_if<
                 std::uses_allocator<container_type, Alloc>::value, int>::type
             = 0>
   stack(const Container& cont, const Alloc& alloc);
   template <typename Alloc,
             typename std::enable_if<
                 std::uses_allocator<container_type, Alloc>::value, int>::type
             = 0>
   stack(Container && cont, const Alloc& alloc);
   template <typename Alloc,
             typename std::enable_if<
                 std::uses_allocator<container_type, Alloc>::value, int>::type
             = 0>
   stack(const stack& cont, const Alloc& alloc);
   template <typename Alloc,
             typename std::enable_if<
                 std::uses_allocator<container_type, Alloc>::value, int>::type
             = 0>
   stack(stack && cont, const Alloc& alloc);
 
   // Element access
 
   KBLIB_NODISCARD auto top()& noexcept(noexcept(backing.back()))->reference {
      return backing.back();
   }
   KBLIB_NODISCARD auto top() const& noexcept(noexcept(backing.back()))
       ->const_reference {
      return backing.back();
   }
 
   // Capacity
 
   KBLIB_NODISCARD auto empty() const noexcept->bool { return backing.empty(); }
   KBLIB_NODISCARD auto size() const noexcept->size_type {
      return backing.size();
   }
 
   // Modifiers
 
   auto push(const value_type& value)->decltype(auto) {
      return backing.push_back(value);
   }
   auto push(value_type && value)->decltype(auto) {
      return backing.push_back(std::move(value));
   }
 
   template <typename... Args>
   auto emplace(Args && ... args)&->decltype(auto) {
      return backing.emplace_back(std::forward<Args>(args)...);
   }
 
   auto pop() noexcept(noexcept(backing.pop_back()))->void {
      backing.pop_back();
      return;
   }
   auto clear() noexcept(noexcept(backing.clear()))->void {
      backing.clear();
      return;
   }
 
   auto swap(stack
             & other) noexcept(fakestd::is_nothrow_swappable<Container>::value)
       ->void {
      using std::swap;
      swap(backing, other.backing);
      return;
   }
 
   // Container access
 
   KBLIB_NODISCARD auto container() const&->container_type& { return backing; }
   KBLIB_NODISCARD auto container()&->container_type& { return backing; }
 
   KBLIB_NODISCARD auto container()&&->container_type {
      return std::move(backing);
   }
};
 
} // namespace KBLIB_NS
 
#endif // KBLIB_CONTAINERS_H