kblib  0.2.3
General utilities library for modern C++
containers.h
Go to the documentation of this file.
1 /* *****************************************************************************
2  * kblib is a general utility library for C++14 and C++17, intended to provide
3  * performant high-level abstractions and more expressive ways to do simple
4  * things.
5  *
6  * Copyright (c) 2021 killerbee
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program. If not, see <https://www.gnu.org/licenses/>.
20  * ****************************************************************************/
21 
31 #ifndef KBLIB_CONTAINERS_H
32 #define KBLIB_CONTAINERS_H
33 
34 #include "fakestd.h"
35 #include "iterators.h"
36 #include "tdecl.h"
37 #include "traits.h"
38 
39 #include <cstddef>
40 #include <deque>
41 #include <iterator>
42 #include <memory>
43 #include <stack>
44 #include <type_traits>
45 #include <vector>
46 
47 namespace kblib {
48 
49 template <typename C>
50 KBLIB_NODISCARD constexpr auto pop(C& s) -> typename C::value_type {
51  typename C::value_type ret = std::move(s.top());
52  s.pop();
53  return ret;
54 }
55 
56 template <class C, typename K, typename V>
57 KBLIB_NODISCARD constexpr auto get_or(const C& m, const K& key, const V& defval)
58  -> typename C::mapped_type {
59  auto it = m.find(key);
60  if (it == m.end())
61  return defval;
62  else
63  return it->second;
64 }
65 
66 template <typename Map, typename Key>
67 KBLIB_NODISCARD constexpr auto try_get(Map& map, Key&& key)
69  auto it = map.find(std::forward<Key>(key));
70  if (it == map.end())
71  return nullptr;
72  else
73  return &it->second;
74 }
75 
76 template <typename iterator>
77 struct exists_t {
78  iterator it;
79  bool found;
80  KBLIB_NODISCARD constexpr operator bool() const noexcept { return found; }
81  KBLIB_NODISCARD constexpr auto operator*() const noexcept(noexcept(*it))
82  -> decltype(*it) {
83  return *it;
84  }
85  KBLIB_NODISCARD constexpr auto operator->() const noexcept -> iterator {
86  return it;
87  }
88  KBLIB_NODISCARD constexpr auto addr() const noexcept -> auto* {
89  return to_pointer(it);
90  }
91 };
92 
93 template <typename M, typename K>
94 KBLIB_NODISCARD constexpr auto get_check(M&& m, const K& key) noexcept(
95  noexcept(m.find(key) != m.end())) -> exists_t<decltype(m.find(key))> {
96  auto it = m.find(key);
97  return {it, it != m.end()};
98 }
99 
115 template <typename V>
116 auto force_shrink_to_fit(V& vec) -> void {
117  if (std::is_nothrow_move_constructible<typename V::value_type>::value) {
118  V tmp;
119  try_reserve(tmp, vec.size());
120  std::move(vec.begin(), vec.end(), std::back_inserter(tmp));
121  vec = std::move(tmp);
122  } else {
123  V tmp(vec.begin(), vec.end());
124  vec = std::move(tmp);
125  }
126  return;
127 }
128 
129 template <typename C, std::size_t size>
131  KBLIB_NODISCARD constexpr static auto make() -> C { return C(size); }
132 };
133 
134 template <typename C, std::size_t size>
136  KBLIB_NODISCARD constexpr static auto make() -> C {
137  C c;
138  c.reserve(size);
139  return c;
140  }
141 };
142 
151 template <typename Container, typename Range>
152 KBLIB_NODISCARD constexpr auto construct_from_range(Range&& r) -> Container {
153  using std::begin;
154  using std::end;
155  return Container{begin(std::forward<Range>(r)), end(std::forward<Range>(r))};
156 }
157 
158 template <typename Container, bool ArrayLike = not is_resizable_v<Container>>
160  private:
169  std::shared_ptr<Container> range;
170 
171  public:
172  using value_type = void;
173  using difference_type = void;
174  using pointer = void;
175  using reference = void;
176  using iterator_category = std::output_iterator_tag;
177 
178  template <typename... Args>
179  build_iterator(Args&&... args)
180  : range(std::make_shared<Container>(std::forward<Args>(args)...)) {}
181 
182  KBLIB_NODISCARD constexpr auto base() noexcept(
183  std::is_nothrow_move_constructible<Container>::value) -> Container {
184  auto holder = std::move(range);
185  return std::move(*holder);
186  }
187 
188  KBLIB_NODISCARD constexpr explicit operator Container() noexcept(
189  std::is_nothrow_move_constructible<Container>::value) {
190  auto holder = std::move(range);
191  return std::move(*holder);
192  }
193 
202  KBLIB_NODISCARD constexpr auto operator*() const
203  noexcept(noexcept(*std::back_inserter(*range))) -> decltype(auto) {
204  return std::back_inserter(*range);
205  }
206 
211  return *this;
212  }
216  KBLIB_NODISCARD constexpr auto operator++(int) -> build_iterator& {
217  return *this;
218  }
219 };
220 
221 KBLIB_UNUSED constexpr struct build_end_t {
222  template <typename T>
223  KBLIB_NODISCARD constexpr operator T() const
224  noexcept(noexcept(T{std::declval<build_end_t&>()})) {
225  return T{this};
226  }
228 
229 template <typename Container>
230 class KBLIB_NODISCARD build_iterator<Container, true> {
231  public:
232  using value_type = void;
233  using difference_type = void;
234  using pointer = void;
235  using reference = void;
236  using iterator_category = std::output_iterator_tag;
237 
238  template <typename... Args>
239  build_iterator(Args&&... args)
240  : range(std::make_shared<Container>(std::forward<Args>(args)...)) {}
241 
243  : range{nullptr}
244  , index(std::tuple_size<Container>::value) {}
245 
246  KBLIB_NODISCARD auto base() noexcept(
247  std::is_nothrow_move_constructible<Container>::value) -> Container {
248  auto holder = std::move(range);
249  return std::move(*holder);
250  }
251 
252  KBLIB_NODISCARD explicit operator Container() noexcept(
253  std::is_nothrow_move_constructible<Container>::value) {
254  auto holder = std::move(range);
255  return std::move(*holder);
256  }
257 
258  KBLIB_NODISCARD auto operator*() const noexcept -> decltype(auto) {
259  return (*range)[index];
260  }
261  KBLIB_NODISCARD auto operator->() const noexcept -> auto* {
262  return &(*range)[index];
263  }
264 
269  ++index;
270  return *this;
271  }
275  auto operator++(int) -> build_iterator& {
276  auto tmp = *this;
277  ++index;
278  return tmp;
279  }
280 
281  KBLIB_NODISCARD constexpr auto size() const noexcept -> std::size_t {
282  return kblib::size(*range);
283  }
284 
285  KBLIB_NODISCARD constexpr friend auto operator==(
286  const build_iterator<Container>& it, build_end_t) noexcept -> bool {
287  return it.index == it.size();
288  }
289  KBLIB_NODISCARD constexpr friend auto operator!=(
290  const build_iterator<Container>& it, build_end_t) noexcept -> bool {
291  return it.index != it.size();
292  }
293 
294  KBLIB_NODISCARD constexpr friend auto operator==(
295  build_end_t, const build_iterator<Container>& it) noexcept -> bool {
296  return it.index == it.size();
297  }
298  KBLIB_NODISCARD constexpr friend auto operator!=(
299  build_end_t, const build_iterator<Container>& it) noexcept -> bool {
300  return it.index != it.size();
301  }
302 
303  KBLIB_NODISCARD constexpr friend auto operator==(
304  const build_iterator<Container>& it1,
305  const build_iterator<Container>& it2) noexcept -> bool {
306  return it1.index == it2.index;
307  }
308  KBLIB_NODISCARD constexpr friend auto operator!=(
309  const build_iterator<Container>& it1,
310  const build_iterator<Container>& it2) noexcept -> bool {
311  return it1.index != it2.index;
312  }
313 
314  private:
323  std::shared_ptr<Container> range;
324  std::size_t index{};
325 };
326 
327 } // namespace kblib
328 
329 namespace std {
330 #if defined(__clang__)
331 // Because apparently -Wno-mismatched-tags doesn't work
332 # pragma clang diagnostic push
333 # pragma clang diagnostic ignored "-Wmismatched-tags"
334 #endif
335 
336 template <typename C, std::size_t Size>
337 struct tuple_size<::kblib::construct_with_size<C, Size>>
338  : public integral_constant<size_t, Size> {};
339 
340 #if defined(__clang__)
341 # pragma clang diagnostic pop
342 #endif
343 } // namespace std
344 
345 namespace kblib {
346 namespace detail {
347 
348  template <typename Container, std::size_t N>
349  struct buildiota_impl<construct_with_size<Container, N>, false> {
350  template <typename T>
351  constexpr static auto impl(T value) -> Container {
352  Container out = construct_with_size<Container, N>::make();
353  for (auto& v : out) {
354  v = value;
355  ++value;
356  }
357  return out;
358  }
359  template <typename T, typename I>
360  constexpr static auto impl(T value, I incr) -> Container {
361  Container out = construct_with_size<Container, N>::make();
362  for (auto& v : out) {
363  v = value;
364  value += incr;
365  }
366  return out;
367  }
368  };
369 
370 } // namespace detail
371 
372 template <typename T, typename Container = std::vector<T>>
373 class [[deprecated("use a class derived from std::stack instead")]] stack {
374  public:
375  // Member types
376 
377  using container_type = Container;
378  using value_type = typename Container::value_type;
379  using size_type = typename Container::size_type;
380  using reference = typename Container::reference;
381  using const_reference = typename Container::const_reference;
382 
383  static_assert(std::is_same<T, value_type>::value,
384  "Container::value_type must be T.");
385 
386  private:
387  container_type backing;
388 
389  public:
390  // Constructors
391 
393  : stack(Container()) {}
394  explicit stack(const Container& cont)
395  : backing(cont) {}
396 
397  template <typename Alloc,
398  typename std::enable_if<
399  std::uses_allocator<container_type, Alloc>::value, int>::type
400  = 0>
401  explicit stack(const Alloc& alloc);
402  template <typename Alloc,
403  typename std::enable_if<
404  std::uses_allocator<container_type, Alloc>::value, int>::type
405  = 0>
406  stack(const Container& cont, const Alloc& alloc);
407  template <typename Alloc,
408  typename std::enable_if<
409  std::uses_allocator<container_type, Alloc>::value, int>::type
410  = 0>
411  stack(Container && cont, const Alloc& alloc);
412  template <typename Alloc,
413  typename std::enable_if<
414  std::uses_allocator<container_type, Alloc>::value, int>::type
415  = 0>
416  stack(const stack& cont, const Alloc& alloc);
417  template <typename Alloc,
418  typename std::enable_if<
419  std::uses_allocator<container_type, Alloc>::value, int>::type
420  = 0>
421  stack(stack && cont, const Alloc& alloc);
422 
423  // Element access
424 
425  KBLIB_NODISCARD auto top()& noexcept(noexcept(backing.back()))->reference {
426  return backing.back();
427  }
428  KBLIB_NODISCARD auto top() const& noexcept(noexcept(backing.back()))
429  ->const_reference {
430  return backing.back();
431  }
432 
433  // Capacity
434 
435  KBLIB_NODISCARD auto empty() const noexcept->bool { return backing.empty(); }
436  KBLIB_NODISCARD auto size() const noexcept->size_type {
437  return backing.size();
438  }
439 
440  // Modifiers
441 
442  auto push(const value_type& value)->decltype(auto) {
443  return backing.push_back(value);
444  }
445  auto push(value_type && value)->decltype(auto) {
446  return backing.push_back(std::move(value));
447  }
448 
449  template <typename... Args>
450  auto emplace(Args && ... args)&->decltype(auto) {
451  return backing.emplace_back(std::forward<Args>(args)...);
452  }
453 
454  auto pop() noexcept(noexcept(backing.pop_back()))->void {
455  backing.pop_back();
456  return;
457  }
458  auto clear() noexcept(noexcept(backing.clear()))->void {
459  backing.clear();
460  return;
461  }
462 
463  auto swap(stack
465  ->void {
466  using std::swap;
467  swap(backing, other.backing);
468  return;
469  }
470 
471  // Container access
472 
473  KBLIB_NODISCARD auto container() const&->container_type& { return backing; }
474  KBLIB_NODISCARD auto container()&->container_type& { return backing; }
475 
476  KBLIB_NODISCARD auto container()&&->container_type {
477  return std::move(backing);
478  }
479 };
480 
481 } // namespace kblib
482 
483 #endif // KBLIB_CONTAINERS_H
auto base() noexcept(std::is_nothrow_move_constructible< Container >::value) -> Container
Definition: containers.h:246
auto operator++(int) -> build_iterator &
Advance to the next element.
Definition: containers.h:275
constexpr friend auto operator!=(const build_iterator< Container > &it1, const build_iterator< Container > &it2) noexcept -> bool
Definition: containers.h:308
auto operator*() const noexcept -> decltype(auto)
Definition: containers.h:258
constexpr auto size() const noexcept -> std::size_t
Definition: containers.h:281
constexpr friend auto operator!=(const build_iterator< Container > &it, build_end_t) noexcept -> bool
Definition: containers.h:289
constexpr friend auto operator==(build_end_t, const build_iterator< Container > &it) noexcept -> bool
Definition: containers.h:294
auto operator++() -> build_iterator &
Advance to the next element.
Definition: containers.h:268
constexpr friend auto operator==(const build_iterator< Container > &it, build_end_t) noexcept -> bool
Definition: containers.h:285
constexpr friend auto operator==(const build_iterator< Container > &it1, const build_iterator< Container > &it2) noexcept -> bool
Definition: containers.h:303
auto operator->() const noexcept -> auto *
Definition: containers.h:261
constexpr friend auto operator!=(build_end_t, const build_iterator< Container > &it) noexcept -> bool
Definition: containers.h:298
std::output_iterator_tag iterator_category
Definition: containers.h:236
constexpr auto operator++(int) -> build_iterator &
A no-op.
Definition: containers.h:216
build_iterator(Args &&... args)
Definition: containers.h:179
constexpr auto base() noexcept(std::is_nothrow_move_constructible< Container >::value) -> Container
Definition: containers.h:182
constexpr auto operator++() -> build_iterator &
A no-op.
Definition: containers.h:210
constexpr auto operator*() const noexcept(noexcept(*std::back_inserter(*range))) -> decltype(auto)
Creates a temporary std::back_insert_iterator for the range and returns it.
Definition: containers.h:202
std::output_iterator_tag iterator_category
Definition: containers.h:176
auto push(value_type &&value) -> decltype(auto)
Definition: containers.h:445
stack(Container &&cont, const Alloc &alloc)
stack(stack &&cont, const Alloc &alloc)
typename Container::reference reference
Definition: containers.h:380
auto swap(stack &other) noexcept(fakestd::is_nothrow_swappable< Container >::value) -> void
Definition: containers.h:463
stack(const stack &cont, const Alloc &alloc)
auto container() const &-> container_type &
Definition: containers.h:473
auto top() &noexcept(noexcept(backing.back())) -> reference
Definition: containers.h:425
auto clear() noexcept(noexcept(backing.clear())) -> void
Definition: containers.h:458
auto pop() noexcept(noexcept(backing.pop_back())) -> void
Definition: containers.h:454
typename Container::size_type size_type
Definition: containers.h:379
stack(const Container &cont)
Definition: containers.h:394
auto size() const noexcept -> size_type
Definition: containers.h:436
auto container() &-> container_type &
Definition: containers.h:474
typename Container::const_reference const_reference
Definition: containers.h:381
auto container() &&-> container_type
Definition: containers.h:476
auto top() const &noexcept(noexcept(backing.back())) -> const_reference
Definition: containers.h:428
auto push(const value_type &value) -> decltype(auto)
Definition: containers.h:442
auto empty() const noexcept -> bool
Definition: containers.h:435
stack(const Alloc &alloc)
auto emplace(Args &&... args) &-> decltype(auto)
Definition: containers.h:450
typename Container::value_type value_type
Definition: containers.h:378
stack(const Container &cont, const Alloc &alloc)
Container container_type
Definition: containers.h:377
This header provides some features of C++17 <type_traits> and other headers for C++14,...
This file provides some iterators, ranges, iterator/range adapters, and operations that can be perfor...
The main namespace in which all entities from kblib are defined.
Definition: algorithm.h:44
auto force_shrink_to_fit(V &vec) -> void
std::vector::shrink_to_fit is non-binding, which means that there is no guaranteed way to shrink a ve...
Definition: containers.h:116
constexpr auto size(const C &c) -> decltype(c.size())
Definition: fakestd.h:1069
auto map(F f, T &&... t) noexcept(noexcept(std::tuple{ kblib::apply(f, std::forward< T >(t))...})) -> enable_if_t< not any_void< decltype(kblib::apply(f, std::forward< T >(t)))... >, decltype(std::tuple{kblib::apply(f, std::forward< T >(t))...})>
Definition: simple.h:75
constexpr auto to_pointer(P &&p) noexcept -> auto *
Gets a raw pointer out of any smart pointer or iterator you might pass in, without dereferencing it o...
Definition: iterators.h:71
constexpr auto a(const std::initializer_list< T > &a) -> auto
Index an array literal without naming its type.
Definition: simple.h:255
constexpr auto get_or(const C &m, const K &key, const V &defval) -> typename C::mapped_type
Definition: containers.h:57
struct kblib::@0 swap
constexpr auto construct_from_range(Range &&r) -> Container
Allows for constructing a container of a specified type from a range object. Copy elision means that ...
Definition: containers.h:152
auto try_reserve(C &c, std::size_t s) noexcept(noexcept(c.reserve(s))) -> void
Attempt to reserve capacity in a container. No-op if unsupported.
Definition: traits.h:239
constexpr auto range(Value min, Value max, Delta step=0) -> range_t< Value, Delta >
Constructs a range from beginning, end, and step amount. The range is half-open, that is min is in th...
Definition: iterators.h:620
constexpr struct kblib::build_end_t build_end
constexpr auto try_get(Map &map, Key &&key) -> copy_const_t< Map, typename Map::mapped_type > *
Definition: containers.h:67
constexpr auto pop(C &s) -> typename C::value_type
Definition: containers.h:50
constexpr auto get_check(M &&m, const K &key) noexcept(noexcept(m.find(key) !=m.end())) -> exists_t< decltype(m.find(key))>
Definition: containers.h:94
typename copy_const< C, V >::type copy_const_t
Definition: fakestd.h:870
Definition: bits.h:714
constexpr static auto make() -> C
Definition: containers.h:136
constexpr static auto make() -> C
Definition: containers.h:131
constexpr static auto impl(T value, I incr) -> Container
Definition: containers.h:360
iterator it
Definition: containers.h:78
constexpr auto operator->() const noexcept -> iterator
Definition: containers.h:85
constexpr auto addr() const noexcept -> auto *
Definition: containers.h:88
constexpr auto operator*() const noexcept(noexcept(*it)) -> decltype(*it)
Definition: containers.h:81
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_UNUSED
This internal macro is used to provide a fallback for [[maybe_unused]] in C++14.
Definition: tdecl.h:92
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:81
Contains some type traits not in the standard library that are useful in the implementation of kblib.