TLA Line data Source code
1 : //
2 : // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // Official repository: https://github.com/boostorg/json
8 : //
9 :
10 : #ifndef BOOST_JSON_OBJECT_HPP
11 : #define BOOST_JSON_OBJECT_HPP
12 :
13 : #include <boost/json/detail/config.hpp>
14 : #include <boost/json/detail/object.hpp>
15 : #include <boost/json/detail/value.hpp>
16 : #include <boost/json/kind.hpp>
17 : #include <boost/json/pilfer.hpp>
18 : #include <boost/system/result.hpp>
19 : #include <boost/json/storage_ptr.hpp>
20 : #include <boost/json/string_view.hpp>
21 : #include <cstdlib>
22 : #include <initializer_list>
23 : #include <iterator>
24 : #include <type_traits>
25 : #include <utility>
26 :
27 : namespace boost {
28 : namespace json {
29 :
30 : class value;
31 : class value_ref;
32 : class key_value_pair;
33 :
34 : /** A dynamically sized associative container of JSON key/value pairs.
35 :
36 : This is an associative container whose elements are key/value pairs with
37 : unique keys.
38 :
39 : The elements are stored contiguously; iterators are ordinary pointers,
40 : allowing random access pointer arithmetic for retrieving elements. In
41 : addition, the container maintains an internal index to speed up find
42 : operations, reducing the average complexity for most lookups and
43 : insertions.
44 :
45 : Reallocations are usually costly operations in terms of performance, as
46 : elements are copied and the internal index must be rebuilt. The @ref
47 : reserve function can be used to eliminate reallocations if the number of
48 : elements is known beforehand.
49 :
50 : @par Allocators
51 : All elements stored in the container, and their children if any, will use
52 : the same memory resource that was used to construct the container.
53 :
54 : @par Thread Safety
55 : Non-const member functions may not be called concurrently with any other
56 : member functions.
57 :
58 : @par Satisfies
59 : [ContiguousContainer](https://en.cppreference.com/w/cpp/named_req/ContiguousContainer),
60 : [ReversibleContainer](https://en.cppreference.com/w/cpp/named_req/ReversibleContainer), and
61 : {req_SequenceContainer}.
62 : */
63 : class object
64 : {
65 : struct table;
66 : class revert_construct;
67 : class revert_insert;
68 : friend class value;
69 : friend class object_test;
70 : using access = detail::access;
71 : using index_t = std::uint32_t;
72 : static index_t constexpr null_index_ =
73 : std::uint32_t(-1);
74 :
75 : storage_ptr sp_; // must come first
76 : kind k_ = kind::object; // must come second
77 : table* t_;
78 :
79 : BOOST_JSON_DECL
80 : static table empty_;
81 :
82 : template<class T>
83 : using is_inputit = typename std::enable_if<
84 : std::is_constructible<key_value_pair,
85 : typename std::iterator_traits<T>::reference
86 : >::value>::type;
87 :
88 : BOOST_JSON_DECL
89 : explicit
90 : object(detail::unchecked_object&& uo);
91 :
92 : public:
93 : /// Associated [Allocator](https://en.cppreference.com/w/cpp/named_req/Allocator)
94 : using allocator_type = container::pmr::polymorphic_allocator<value>;
95 :
96 : /** The type of keys.
97 :
98 : The function @ref string::max_size returns the
99 : maximum allowed size of strings used as keys.
100 : */
101 : using key_type = string_view;
102 :
103 : /// The type of mapped values
104 : using mapped_type = value;
105 :
106 : /// The element type
107 : using value_type = key_value_pair;
108 :
109 : /// The type used to represent unsigned integers
110 : using size_type = std::size_t;
111 :
112 : /// The type used to represent signed integers
113 : using difference_type = std::ptrdiff_t;
114 :
115 : /// A reference to an element
116 : using reference = value_type&;
117 :
118 : /// A const reference to an element
119 : using const_reference = value_type const&;
120 :
121 : /// A pointer to an element
122 : using pointer = value_type*;
123 :
124 : /// A const pointer to an element
125 : using const_pointer = value_type const*;
126 :
127 : /// A random access iterator to an element
128 : using iterator = value_type*;
129 :
130 : /// A const random access iterator to an element
131 : using const_iterator = value_type const*;
132 :
133 : /// A reverse random access iterator to an element
134 : using reverse_iterator =
135 : std::reverse_iterator<iterator>;
136 :
137 : /// A const reverse random access iterator to an element
138 : using const_reverse_iterator =
139 : std::reverse_iterator<const_iterator>;
140 :
141 : //------------------------------------------------------
142 :
143 : /** Destructor.
144 :
145 : The destructor for each element is called if needed, any used memory is
146 : deallocated, and shared ownership of the
147 : @ref boost::container::pmr::memory_resource is released.
148 :
149 : @par Complexity
150 : Constant, or linear in @ref size().
151 :
152 : @par Exception Safety
153 : No-throw guarantee.
154 : */
155 : BOOST_JSON_DECL
156 : ~object() noexcept;
157 :
158 : //------------------------------------------------------
159 :
160 : /** Constructors.
161 :
162 : Constructs an object.
163 :
164 : @li **(1)**--**(3)** the object is empty.
165 :
166 : @li **(4)** the object is filled with values in the range
167 : `[first, last)`.
168 :
169 : @li **(5)**, **(6)** the object is filled with copies of the values in
170 : `init`.
171 :
172 : @li **(7)**, **(8)** the object is filled with copies of the elements
173 : of `other`.
174 :
175 : @li **(9)** the object acquires ownership of the contents of `other`.
176 :
177 : @li **(10)** equivalent to **(9)** if `*sp == *other.storage()`;
178 : otherwise equivalent to **(8)**.
179 :
180 : @li **(11)** the object acquires ownership of the contents of `other`
181 : using pilfer semantics. This is more efficient than move
182 : construction, when it is known that the moved-from object will be
183 : immediately destroyed afterwards.
184 :
185 : Upon construction, @ref capacity() will be large enough to store the
186 : object's elements. In addition, with **(3)**, **(4)**, and **(6)** the
187 : capacity will not be smaller than `min_capacity`.
188 :
189 : With **(2)**--**(6)**, **(8)**, **(10)** the constructed object uses
190 : memory resource of `sp`. With **(7)**, **(9)**, **(11)** it uses
191 : `other`'s memory resource. In either case the object will share the
192 : ownership of the memory resource. With **(1)** it uses the
193 : \<\<default_memory_resource,default memory resource\>\>.
194 :
195 : After **(9)** `other` behaves as if newly constructed with its current
196 : storage pointer.
197 :
198 : After **(11)** `other` is not in a usable state and may only be
199 : destroyed.
200 :
201 : If `init` or `[first, last)` have elements with duplicate keys, only
202 : the first of those equivalent elements will be inserted.
203 :
204 : @par Constraints
205 : @code
206 : std::is_constructible_v<
207 : key_value_pair,
208 : std::iterator_traits<InputIt>::reference>
209 : @endcode
210 :
211 : @par Complexity
212 : @li **(1)**--**(3)**, **(9)**, **(11)** constant.
213 : @li **(4)** linear in `std::distance(first, last)`.
214 : @li **(5)**, **(6)** linear in `init.size()`.
215 : @li **(7)**, **(8)** linear in `other.size()`.
216 : @li **(10)** constant if `*sp == *other.storage()`; otherwise linear in
217 : `other.size()`.
218 :
219 : @par Exception Safety
220 : @li **(1)**, **(2)**, **(9)**, **(11)** no-throw guarantee.
221 : @li **(3)**, **(5)**, **(6)**--**(8)**, **(10)** strong guarantee.
222 : @li **(4)** strong guarantee if `InputIt` satisfies
223 : {req_ForwardIterator}, basic guarantee otherwise.
224 :
225 : Calls to `memory_resource::allocate` may throw.
226 :
227 : @see @ref pilfer,
228 : [Valueless Variants Considered Harmful](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0308r0.html).
229 :
230 : @{
231 : */
232 HIT 77 : object() noexcept
233 77 : : t_(&empty_)
234 : {
235 77 : }
236 :
237 : /** Overload
238 :
239 : @param sp A pointer to the @ref boost::container::pmr::memory_resource
240 : to use.
241 : */
242 : explicit
243 487 : object(storage_ptr sp) noexcept
244 487 : : sp_(std::move(sp))
245 487 : , t_(&empty_)
246 : {
247 487 : }
248 :
249 : /** Overload
250 :
251 : @param min_capacity The minimum number of elements for which capacity
252 : is guaranteed without a subsequent reallocation.
253 : @param sp
254 : */
255 : BOOST_JSON_DECL
256 : object(
257 : std::size_t min_capacity,
258 : storage_ptr sp = {});
259 :
260 : /** Overload
261 :
262 : @param first An input iterator pointing to the first element to insert,
263 : or pointing to the end of the range.
264 : @param last An input iterator pointing to the end of the range.
265 : @param min_capacity
266 : @param sp
267 :
268 : @tparam InputIt a type satisfying the requirements of
269 : {req_InputIterator}.
270 : */
271 : template<
272 : class InputIt
273 : #ifndef BOOST_JSON_DOCS
274 : ,class = is_inputit<InputIt>
275 : #endif
276 : >
277 160 : object(
278 : InputIt first,
279 : InputIt last,
280 : std::size_t min_capacity = 0,
281 : storage_ptr sp = {})
282 160 : : sp_(std::move(sp))
283 160 : , t_(&empty_)
284 : {
285 160 : construct(
286 : first, last,
287 : min_capacity,
288 : typename std::iterator_traits<
289 : InputIt>::iterator_category{});
290 160 : }
291 :
292 : /** Overload
293 :
294 : @param init The initializer list to insert.
295 : @param sp
296 : */
297 339 : object(
298 : std::initializer_list<
299 : std::pair<string_view, value_ref>> init,
300 : storage_ptr sp = {})
301 339 : : object(init, 0, std::move(sp))
302 : {
303 246 : }
304 :
305 : /** Overload
306 :
307 : @param init
308 : @param min_capacity
309 : @param sp
310 : */
311 : BOOST_JSON_DECL
312 : object(
313 : std::initializer_list<
314 : std::pair<string_view, value_ref>> init,
315 : std::size_t min_capacity,
316 : storage_ptr sp = {});
317 :
318 : /** Overload
319 :
320 : @param other Another object.
321 : */
322 13 : object(
323 : object const& other)
324 13 : : object(other, other.sp_)
325 : {
326 13 : }
327 :
328 : /** Overload
329 :
330 : @param other
331 : @param sp
332 : */
333 : BOOST_JSON_DECL
334 : object(
335 : object const& other,
336 : storage_ptr sp);
337 :
338 : /** Overload
339 :
340 : @param other
341 : */
342 : BOOST_JSON_DECL
343 : object(object&& other) noexcept;
344 :
345 : /** Overload
346 :
347 : @param other
348 : @param sp
349 : */
350 : BOOST_JSON_DECL
351 : object(
352 : object&& other,
353 : storage_ptr sp);
354 :
355 : /** Overload
356 :
357 : @param other
358 : */
359 17 : object(pilfered<object> other) noexcept
360 17 : : sp_(std::move(other.get().sp_))
361 34 : , t_(detail::exchange(
362 17 : other.get().t_, &empty_))
363 : {
364 17 : }
365 : /// @}
366 :
367 : //------------------------------------------------------
368 : //
369 : // Assignment
370 : //
371 : //------------------------------------------------------
372 :
373 : /** Assignment operators.
374 :
375 : Replaces the contents of this object.
376 :
377 : @li **(1)** replaces with the copies of the elements of `other`.
378 : @li **(2)** takes ownership of `other`'s element storage if
379 : `*storage() == *other.storage()`; otherwise equivalent to **(1)**.
380 : @li **(3)** replaces with the elements of `init`.
381 :
382 : @par Complexity
383 : @li **(1)** linear in `size() + other.size()`.
384 : @li **(2)** constant if `*storage() == *other.storage()`; otherwise
385 : linear in `size() + other.size()`.
386 : @li **(3)** average case linear in `size() + init.size()`, worst case
387 : quadratic in `init.size()`.
388 :
389 : @par Exception Safety
390 : @li **(1)**, **(3)** strong guarantee.
391 : @li **(2)** no-throw guarantee if `*storage() == *other.storage()`;
392 : otherwise strong guarantee.
393 :
394 : Calls to `memory_resource::allocate` may throw.
395 :
396 : @par Complexity
397 :
398 : @param other Another object.
399 :
400 : @{
401 : */
402 : BOOST_JSON_DECL
403 : object&
404 : operator=(object const& other);
405 :
406 : BOOST_JSON_DECL
407 : object&
408 : operator=(object&& other);
409 :
410 : /** Overload
411 :
412 : @param init The initializer list to copy.
413 : */
414 : BOOST_JSON_DECL
415 : object&
416 : operator=(std::initializer_list<
417 : std::pair<string_view, value_ref>> init);
418 : /// @}
419 :
420 : //------------------------------------------------------
421 :
422 : /** Return the associated memory resource.
423 :
424 : This function returns a smart pointer to the
425 : @ref boost::container::pmr::memory_resource used by the container.
426 :
427 : @par Complexity
428 : Constant.
429 :
430 : @par Exception Safety
431 : No-throw guarantee.
432 : */
433 : storage_ptr const&
434 683 : storage() const noexcept
435 : {
436 683 : return sp_;
437 : }
438 :
439 : /** Return the associated allocator.
440 :
441 : This function returns an instance of @ref allocator_type constructed
442 : from the associated @ref boost::container::pmr::memory_resource.
443 :
444 : @par Complexity
445 : Constant.
446 :
447 : @par Exception Safety
448 : No-throw guarantee.
449 : */
450 : allocator_type
451 1 : get_allocator() const noexcept
452 : {
453 1 : return sp_.get();
454 : }
455 :
456 : //------------------------------------------------------
457 : //
458 : // Iterators
459 : //
460 : //------------------------------------------------------
461 :
462 : /** Return an iterator to the first element.
463 :
464 : If the container is empty, @ref end() is returned.
465 :
466 : @par Complexity
467 : Constant.
468 :
469 : @par Exception Safety
470 : No-throw guarantee.
471 :
472 : @{
473 : */
474 : inline
475 : iterator
476 : begin() noexcept;
477 :
478 : inline
479 : const_iterator
480 : begin() const noexcept;
481 : /// @}
482 :
483 : /** Return a const iterator to the first element.
484 :
485 : If the container is empty, @ref cend() is returned.
486 :
487 : @par Complexity
488 : Constant.
489 :
490 : @par Exception Safety
491 : No-throw guarantee.
492 : */
493 : inline
494 : const_iterator
495 : cbegin() const noexcept;
496 :
497 : /** Return an iterator to the element following the last element.
498 :
499 : The element acts as a placeholder; attempting
500 : to access it results in undefined behavior.
501 :
502 : @par Complexity
503 : Constant.
504 :
505 : @par Exception Safety
506 : No-throw guarantee.
507 :
508 : @{
509 : */
510 : inline
511 : iterator
512 : end() noexcept;
513 :
514 : inline
515 : const_iterator
516 : end() const noexcept;
517 : /// @}
518 :
519 : /** Return a const iterator to the element following the last element.
520 :
521 : The element acts as a placeholder; attempting
522 : to access it results in undefined behavior.
523 :
524 : @par Complexity
525 : Constant.
526 :
527 : @par Exception Safety
528 : No-throw guarantee.
529 : */
530 : inline
531 : const_iterator
532 : cend() const noexcept;
533 :
534 : /** Return a reverse iterator to the first element of the reversed container.
535 :
536 : The pointed-to element corresponds to the last element of the
537 : non-reversed container. If the container is empty, @ref rend() is
538 : returned.
539 :
540 : @par Complexity
541 : Constant.
542 :
543 : @par Exception Safety
544 : No-throw guarantee.
545 :
546 : @{
547 : */
548 : inline
549 : reverse_iterator
550 : rbegin() noexcept;
551 :
552 : inline
553 : const_reverse_iterator
554 : rbegin() const noexcept;
555 : /// @}
556 :
557 : /** Return a const reverse iterator to the first element of the reversed container.
558 :
559 : The pointed-to element corresponds to the
560 : last element of the non-reversed container.
561 : If the container is empty, @ref crend() is returned.
562 :
563 : @par Complexity
564 : Constant.
565 :
566 : @par Exception Safety
567 : No-throw guarantee.
568 : */
569 : inline
570 : const_reverse_iterator
571 : crbegin() const noexcept;
572 :
573 : /** Return a reverse iterator to the element following the last element of the reversed container.
574 :
575 : The pointed-to element corresponds to the element preceding the first
576 : element of the non-reversed container. The returned iterator only acts
577 : as a sentinel. Dereferencing it results in undefined behavior.
578 :
579 : @par Complexity
580 : Constant.
581 :
582 : @par Exception Safety
583 : No-throw guarantee.
584 :
585 : @{
586 : */
587 : inline
588 : reverse_iterator
589 : rend() noexcept;
590 :
591 : inline
592 : const_reverse_iterator
593 : rend() const noexcept;
594 : /// @}
595 :
596 : /** Return a const reverse iterator to the element following the last element of the reversed container.
597 :
598 : The pointed-to element corresponds to the element preceding the first
599 : element of the non-reversed container. The returned iterator only acts
600 : as a sentinel. Dereferencing it results in undefined behavior.
601 :
602 : @par Complexity
603 : Constant.
604 :
605 : @par Exception Safety
606 : No-throw guarantee.
607 : */
608 : inline
609 : const_reverse_iterator
610 : crend() const noexcept;
611 :
612 : //------------------------------------------------------
613 : //
614 : // Capacity
615 : //
616 : //------------------------------------------------------
617 :
618 : /** Return whether there are no elements.
619 :
620 : Returns `true` if there are no elements in
621 : the container, i.e. @ref size() returns 0.
622 :
623 : @par Complexity
624 : Constant.
625 :
626 : @par Exception Safety
627 : No-throw guarantee.
628 : */
629 : inline
630 : bool
631 : empty() const noexcept;
632 :
633 : /** Return the number of elements.
634 :
635 : This returns the number of elements in the container.
636 :
637 : @par Complexity
638 : Constant.
639 :
640 : @par Exception Safety
641 : No-throw guarantee.
642 : */
643 : inline
644 : std::size_t
645 : size() const noexcept;
646 :
647 : /** The maximum number of elements an object can hold.
648 :
649 : The maximum is an implementation-defined number dependent on system or
650 : library implementation. This value is a theoretical limit; at runtime,
651 : the actual maximum size may be less due to resource limits.
652 :
653 : @par Complexity
654 : Constant.
655 :
656 : @par Exception Safety
657 : No-throw guarantee.
658 : */
659 : static
660 : constexpr
661 : std::size_t
662 : max_size() noexcept;
663 :
664 : /** Return the number of elements that can be held in currently allocated memory.
665 :
666 : Returns the number of elements that the container has currently
667 : allocated space for. This number is never smaller than the value
668 : returned by @ref size().
669 :
670 : @par Complexity
671 : Constant.
672 :
673 : @par Exception Safety
674 : No-throw guarantee.
675 : */
676 : inline
677 : std::size_t
678 : capacity() const noexcept;
679 :
680 : /** Increase the capacity to at least a certain amount.
681 :
682 : This increases the @ref capacity() to a value that is greater than or
683 : equal to `new_capacity`. If `new_capacity > capacity()`, new memory is
684 : allocated. Otherwise, the call has no effect. The number of elements
685 : and therefore the @ref size() of the container is not changed.
686 :
687 : If new memory is allocated, all iterators including any past-the-end
688 : iterators, and all references to the elements are invalidated.
689 : Otherwise, no iterators or references are invalidated.
690 :
691 : @par Complexity
692 : Constant if no reallocation occurs. Otherwise, average case linear in
693 : @ref size(), worst case quadratic in @ref size().
694 :
695 : @par Exception Safety
696 : Strong guarantee. Calls to `memory_resource::allocate` may throw.
697 :
698 : @param new_capacity The new minimum capacity.
699 :
700 : @throw boost::system::system_error `new_capacity >` @ref max_size().
701 : */
702 : inline
703 : void
704 : reserve(std::size_t new_capacity);
705 :
706 : //------------------------------------------------------
707 : //
708 : // Modifiers
709 : //
710 : //------------------------------------------------------
711 :
712 : /** Erase all elements.
713 :
714 : Erases all elements from the container. After this call, @ref size()
715 : returns zero but @ref capacity() is unchanged. All references,
716 : pointers, and iterators are invalidated.
717 :
718 : @par Complexity
719 : Linear in @ref size().
720 :
721 : @par Exception Safety
722 : No-throw guarantee.
723 : */
724 : BOOST_JSON_DECL
725 : void
726 : clear() noexcept;
727 :
728 : /** Insert elements.
729 :
730 : @li **(1)** inserts a new element constructed as if via
731 : `value_type( std::forward<P>(p) )`.
732 : @li **(2)** the elements in the range `[first, last)` are inserted one
733 : at a time, in order.
734 : @li **(3)** the elements in the initializer list are inserted one at a
735 : time, in order.
736 :
737 : Any element with key that is a duplicate of a key already present in
738 : container will be skipped. This also means, that if there are two keys
739 : within the inserted range that are equal to each other, only the
740 : first will be inserted.
741 :
742 : If an insertion would result in the new number of elements exceeding
743 : @ref capacity(), a reallocation and a rehashing occur. In that case all
744 : iterators and references are invalidated. Otherwise, they are not
745 : affected.
746 :
747 : @pre
748 : `first` and `last` are not iterators into `*this`. `first` and `last`
749 : form a valid range.
750 :
751 : @par Constraints
752 : @code
753 : std::is_constructible_v<value_type, P>
754 : std::is_constructible_v<value_type, std::iterator_traits<InputIt>::reference>
755 : @endcode
756 :
757 : @par Complexity
758 : @li **(1)** constant on average, worst case linear in @ref size().
759 : @li **(2)** linear in `std::distance(first, last)`.
760 : @li **(3)** linear in `init.size()`.
761 :
762 : @par Exception Safety
763 : @li **(1)** strong guarantee.
764 : @li **(2)** strong guarantee if `InputIt` satisfies
765 : {req_ForwardIterator}, basic guarantee otherwise.
766 : @li **(3)** basic guarantee.
767 :
768 : Calls to `memory_resource::allocate` may throw.
769 :
770 : @param p The value to insert.
771 :
772 : @throw boost::system::system_error The size of a key would exceed
773 : @ref string::max_size.
774 : @throw `boost::system::system_error` @ref size() >= @ref max_size().
775 :
776 : @return **(1)** returns a @ref std::pair where `first` is an iterator
777 : to the existing or inserted element, and `second` is `true` if the
778 : insertion took place or `false` otherwise. **(2)** returns `void`.
779 :
780 : @{
781 : */
782 : template<class P
783 : #ifndef BOOST_JSON_DOCS
784 : ,class = typename std::enable_if<
785 : std::is_constructible<key_value_pair,
786 : P, storage_ptr>::value>::type
787 : #endif
788 : >
789 : std::pair<iterator, bool>
790 : insert(P&& p);
791 :
792 : /** Overload
793 :
794 : @param first An input iterator pointing to the first element to insert,
795 : or pointing to the end of the range.
796 :
797 : @param last An input iterator pointing to the end of the range.
798 :
799 : @tparam InputIt a type satisfying the requirements
800 : of {req_InputIterator}.
801 : */
802 : template<
803 : class InputIt
804 : #ifndef BOOST_JSON_DOCS
805 : ,class = is_inputit<InputIt>
806 : #endif
807 : >
808 : void
809 174 : insert(InputIt first, InputIt last)
810 : {
811 174 : insert(first, last, typename
812 : std::iterator_traits<InputIt
813 : >::iterator_category{});
814 8 : }
815 :
816 : /** Overload
817 :
818 : @param init The initializer list to insert.
819 : */
820 : BOOST_JSON_DECL
821 : void
822 : insert(std::initializer_list<
823 : std::pair<string_view, value_ref>> init);
824 : /// @}
825 :
826 : /** Insert an element or assign to an existing element.
827 :
828 : If the key equal to `key` already exists in the container, assigns
829 : `std::forward<M>(m)` to the @ref mapped_type corresponding to that key.
830 : Otherwise, inserts the as if by @ref insert, constructing it using
831 : `value_type(key, std::forward<M>(m))`.
832 :
833 : If insertion would result in the new number of elements exceeding
834 : @ref capacity(), a reallocation and a rehashing occur. In that case all
835 : iterators and references are invalidated. Otherwise, they are not
836 : affected.
837 :
838 : @par Complexity
839 : Constant on average, worst case linear in @ref size().
840 :
841 : @par Exception Safety
842 : Strong guarantee. Calls to `memory_resource::allocate` may throw.
843 :
844 : @return A @ref std::pair where `first` is an iterator to the existing
845 : or inserted element, and `second` is `true` if the insertion took place
846 : or `false` if the assignment took place.
847 :
848 : @param key The key used for lookup and insertion.
849 : @param m The value to insert or assign.
850 :
851 : @throw boost::system::system_error The size of a key would exceed
852 : @ref string::max_size.
853 : */
854 : template<class M>
855 : std::pair<iterator, bool>
856 : insert_or_assign(
857 : string_view key, M&& m);
858 :
859 : /** Construct an element in-place.
860 :
861 : Inserts a new element into the container constructed
862 : in-place with the given argument if there is no
863 : element with the `key` in the container.
864 :
865 : If the insertion occurs and results in a rehashing of the container,
866 : all iterators and references are invalidated. Otherwise, they are not
867 : affected. Rehashing occurs only if the new number of elements is
868 : greater than @ref capacity().
869 :
870 : @par Complexity
871 : Constant on average, worst case linear in @ref size().
872 :
873 : @par Exception Safety
874 : Strong guarantee.
875 : Calls to `memory_resource::allocate` may throw.
876 :
877 : @return A @ref std::pair where `first` is an iterator
878 : to the existing or inserted element, and `second`
879 : is `true` if the insertion took place or `false` otherwise.
880 :
881 : @param key The key used for lookup and insertion.
882 :
883 : @param arg The argument used to construct the value.
884 : This will be passed as `std::forward<Arg>(arg)` to
885 : the @ref value constructor.
886 :
887 : @throw boost::system::system_error The size of the key would exceed
888 : @ref string::max_size.
889 :
890 : */
891 : template<class Arg>
892 : std::pair<iterator, bool>
893 : emplace(string_view key, Arg&& arg);
894 :
895 : /** Remove an element.
896 :
897 : @li **(1)** the element at `pos` is removed.
898 : @li **(2)** the element with the key `key` is removed, if it exists.
899 :
900 : `pos` must be valid and dereferenceable. References and iterators to
901 : the erased element are invalidated. Other iterators and references are
902 : not invalidated.
903 :
904 : @attention The @ref end() iterator (which is valid but cannot be
905 : dereferenced) cannot be used as a value for `pos`.
906 :
907 : @par Complexity
908 : Constant on average, worst case linear in @ref size().
909 :
910 : @par Exception Safety
911 : No-throw guarantee.
912 :
913 : @return
914 : @li **(1)** an iterator following the removed element.
915 : @li **(2)** the number of elements removed, which will be either
916 : 0 or 1.
917 :
918 : @param pos An iterator pointing to the element to be removed.
919 :
920 : @{
921 : */
922 : BOOST_JSON_DECL
923 : iterator
924 : erase(const_iterator pos) noexcept;
925 :
926 : /** Overload
927 :
928 : @param key The key to match.
929 : */
930 : BOOST_JSON_DECL
931 : std::size_t
932 : erase(string_view key) noexcept;
933 : /// @}
934 :
935 : /** Erase an element preserving order.
936 :
937 : @li **(1)** Remove the element pointed to by `pos`, which must be valid
938 : and dereferenceable. References and iterators from `pos` to @ref end(),
939 : both included, are invalidated. Other iterators and references are not
940 : invalidated.
941 : @li **(2)** Remove the element which matches `key`, if it exists. All
942 : references and iterators are invalidated.
943 :
944 : The relative order of remaining elements is preserved.
945 :
946 : @attention The @ref end() iterator (which is valid but cannot be
947 : dereferenced) cannot be used as a value for `pos`.
948 :
949 : @par Complexity
950 : Linear in @ref size().
951 :
952 : @par Exception Safety
953 : No-throw guarantee.
954 :
955 : @return
956 : @li An iterator following the removed element.
957 : @li The number of elements removed, which will be either 0 or 1.
958 :
959 : @param pos An iterator pointing to the element to be
960 : removed.
961 :
962 : @{
963 : */
964 : BOOST_JSON_DECL
965 : iterator
966 : stable_erase(const_iterator pos) noexcept;
967 :
968 : /** Overload
969 :
970 : @param key The key to match.
971 : */
972 : BOOST_JSON_DECL
973 : std::size_t
974 : stable_erase(string_view key) noexcept;
975 : /// @}
976 :
977 : /** Swap two objects.
978 :
979 : Exchanges the contents of this object with another object. Ownership of
980 : the respective @ref boost::container::pmr::memory_resource objects is
981 : not transferred. If `this == &other`, this function call has no effect.
982 :
983 : @li If `*storage() == *other.storage()` all iterators and references
984 : remain valid.
985 :
986 : @li Otherwise, the contents are logically swapped by making copies,
987 : which can throw. In this case all iterators and references are
988 : invalidated.
989 :
990 : @par Complexity
991 : If `*storage() == *other.storage()`, then constant; otherwise linear in
992 : `size() + other.size()`.
993 :
994 : @par Exception Safety
995 : No-throw guarantee if `*storage() == *other.storage()`. Otherwise
996 : strong guarantee. Calls to `memory_resource::allocate` may throw.
997 :
998 : @param other The object to swap with.
999 : */
1000 : BOOST_JSON_DECL
1001 : void
1002 : swap(object& other);
1003 :
1004 : /** Swap two objects.
1005 :
1006 : Exchanges the contents of the object `lhs` with another object `rhs`.
1007 : Ownership of the respective @ref boost::container::pmr::memory_resource
1008 : objects is not transferred. If `&lhs == &rhs`, this function call has
1009 : no effect.
1010 :
1011 : @li If `*lhs.storage() == *rhs.storage()` all iterators and references
1012 : remain valid.
1013 :
1014 : @li Otherwise, the contents are logically swapped by making copies,
1015 : which can throw. In this case all iterators and references are
1016 : invalidated.
1017 :
1018 : @par Complexity
1019 : If `*lhs.storage() == *rhs.storage()`, then constant; otherwise linear
1020 : in `lhs.size() + rhs.size()`.
1021 :
1022 : @par Exception Safety
1023 : No-throw guarantee if `*lhs.storage() == *rhs.storage()`. Otherwise
1024 : strong guarantee. Calls to `memory_resource::allocate` may throw.
1025 :
1026 : @param lhs The object to exchange.
1027 :
1028 : @param rhs The object to exchange.
1029 :
1030 : @see @ref object::swap
1031 : */
1032 : friend
1033 : void
1034 11 : swap(object& lhs, object& rhs)
1035 : {
1036 11 : lhs.swap(rhs);
1037 3 : }
1038 :
1039 : //------------------------------------------------------
1040 : //
1041 : // Lookup
1042 : //
1043 : //------------------------------------------------------
1044 :
1045 : /** Access the specified element, with bounds checking.
1046 :
1047 : Returns @ref boost::system::result containing a reference to the
1048 : mapped value of the element that matches `key`. Otherwise the result
1049 : contains an `error_code`.
1050 :
1051 : @par Exception Safety
1052 : No-throw guarantee.
1053 :
1054 : @param key The key of the element to find.
1055 :
1056 : @par Complexity
1057 : Constant on average, worst case linear in @ref size().
1058 :
1059 : @{
1060 : */
1061 : BOOST_JSON_DECL
1062 : system::result<value&>
1063 : try_at(string_view key) noexcept;
1064 :
1065 : BOOST_JSON_DECL
1066 : system::result<value const&>
1067 : try_at(string_view key) const noexcept;
1068 : /// @}
1069 :
1070 : /** Access the specified element, with bounds checking.
1071 :
1072 : Returns a reference to the mapped value of the element that matches
1073 : `key`, otherwise throws.
1074 :
1075 : @par Complexity
1076 : Constant on average, worst case linear in @ref size().
1077 :
1078 : @par Exception Safety
1079 : Strong guarantee.
1080 :
1081 : @return A reference to the mapped value.
1082 :
1083 : @param key The key of the element to find.
1084 : @param loc @ref boost::source_location to use in thrown exception; the
1085 : source location of the call site by default.
1086 :
1087 : @throw `boost::system::system_error` if no such element exists.
1088 :
1089 : @see @ref operator[], @ref try_at.
1090 :
1091 : @{
1092 : */
1093 : inline
1094 : value&
1095 : at(
1096 : string_view key,
1097 : source_location const& loc = BOOST_CURRENT_LOCATION) &;
1098 :
1099 : inline
1100 : value&&
1101 : at(
1102 : string_view key,
1103 : source_location const& loc = BOOST_CURRENT_LOCATION) &&;
1104 :
1105 : BOOST_JSON_DECL
1106 : value const&
1107 : at(
1108 : string_view key,
1109 : source_location const& loc = BOOST_CURRENT_LOCATION) const&;
1110 : /// @}
1111 :
1112 : /** Access or insert an element.
1113 :
1114 : Returns a reference to the value that is mapped to `key`. If such value
1115 : does not already exist, performs an insertion of a null value.
1116 :
1117 : If an insertion occurs and results in a rehashing of the container, all
1118 : iterators including any past-the-end iterators, and all references to
1119 : the elements are invalidated. Otherwise, no iterators or references are
1120 : invalidated.
1121 :
1122 : @par Complexity
1123 : Constant on average, worst case linear in @ref size().
1124 :
1125 : @par Exception Safety
1126 : Strong guarantee. Calls to `memory_resource::allocate` may throw.
1127 :
1128 : @return A reference to the mapped value.
1129 :
1130 : @param key The key of the element to find.
1131 : */
1132 : BOOST_JSON_DECL
1133 : value&
1134 : operator[](string_view key);
1135 :
1136 : /** Count the number of elements with a specific key.
1137 :
1138 : Returns the number of elements with keys equal to `key`. The only
1139 : possible return values are 0 and 1.
1140 :
1141 : @par Complexity
1142 : Constant on average, worst case linear in @ref size().
1143 :
1144 : @par Exception Safety
1145 : No-throw guarantee.
1146 :
1147 : @param key The key of the element to find.
1148 : */
1149 : BOOST_JSON_DECL
1150 : std::size_t
1151 : count(string_view key) const noexcept;
1152 :
1153 : /** Find an element with a specific key.
1154 :
1155 : This function returns an iterator to the element
1156 : matching `key` if it exists, otherwise returns
1157 : @ref end().
1158 :
1159 : @par Complexity
1160 : Constant on average, worst case linear in @ref size().
1161 :
1162 : @par Exception Safety
1163 : No-throw guarantee.
1164 :
1165 : @param key The key of the element to find.
1166 :
1167 : @{
1168 : */
1169 : BOOST_JSON_DECL
1170 : iterator
1171 : find(string_view key) noexcept;
1172 :
1173 : BOOST_JSON_DECL
1174 : const_iterator
1175 : find(string_view key) const noexcept;
1176 : /// @}
1177 :
1178 : /** Return `true` if the key is found.
1179 :
1180 : Checks if there is an element with key equal to `key`.
1181 :
1182 : @par Effects
1183 : @code
1184 : return find(key) != end();
1185 : @endcode
1186 :
1187 : @par Complexity
1188 : Constant on average, worst case linear in @ref size().
1189 :
1190 : @par Exception Safety
1191 : No-throw guarantee.
1192 :
1193 : @param key The key of the element to find.
1194 :
1195 : @see @ref find.
1196 : */
1197 : BOOST_JSON_DECL
1198 : bool
1199 : contains(string_view key) const noexcept;
1200 :
1201 : /** Return a pointer to the value if the key is found, or null
1202 :
1203 : This function searches for a value with the given
1204 : key, and returns a pointer to it if found. Otherwise
1205 : it returns null.
1206 :
1207 : @par Example
1208 : @code
1209 : if( auto p = obj.if_contains( "key" ) )
1210 : std::cout << *p;
1211 : @endcode
1212 :
1213 : @par Complexity
1214 : Constant on average, worst case linear in @ref size().
1215 :
1216 : @par Exception Safety
1217 : No-throw guarantee.
1218 :
1219 : @param key The key of the element to find.
1220 :
1221 : @see @ref find.
1222 :
1223 : @{
1224 : */
1225 : BOOST_JSON_DECL
1226 : value const*
1227 : if_contains(string_view key) const noexcept;
1228 :
1229 : BOOST_JSON_DECL
1230 : value*
1231 : if_contains(string_view key) noexcept;
1232 : /// @}
1233 :
1234 : /** Compare two objects for equality.
1235 :
1236 : Objects are equal when their sizes are the same,
1237 : and when for each key in `lhs` there is a matching
1238 : key in `rhs` with the same value.
1239 :
1240 : @par Complexity
1241 : Average case linear and worst case quadratic in `lhs.size()`.
1242 :
1243 : @par Exception Safety
1244 : No-throw guarantee.
1245 : */
1246 : // inline friend speeds up overload resolution
1247 : friend
1248 : bool
1249 75 : operator==(
1250 : object const& lhs,
1251 : object const& rhs) noexcept
1252 : {
1253 75 : return lhs.equal(rhs);
1254 : }
1255 :
1256 : /** Compare two objects for inequality.
1257 :
1258 : Objects are equal when their sizes are the same, and when for each key
1259 : in `lhs` there is a matching key in `rhs` with the same value.
1260 :
1261 : @par Complexity
1262 : Average casee linear and worst case quadratic in `lhs.size()`.
1263 :
1264 : @par Exception Safety
1265 : No-throw guarantee.
1266 : */
1267 : // inline friend speeds up overload resolution
1268 : friend
1269 : bool
1270 6 : operator!=(
1271 : object const& lhs,
1272 : object const& rhs) noexcept
1273 : {
1274 6 : return ! (lhs == rhs);
1275 : }
1276 :
1277 : /** Serialize to an output stream.
1278 :
1279 : This function serializes an `object` as JSON into the output stream.
1280 :
1281 : @return Reference to `os`.
1282 :
1283 : @par Complexity
1284 : Constant or linear in the size of `obj`.
1285 :
1286 : @par Exception Safety
1287 : Strong guarantee.
1288 : Calls to `memory_resource::allocate` may throw.
1289 :
1290 : @param os The output stream to serialize to.
1291 :
1292 : @param obj The value to serialize.
1293 : */
1294 : BOOST_JSON_DECL
1295 : friend
1296 : std::ostream&
1297 : operator<<(
1298 : std::ostream& os,
1299 : object const& obj);
1300 : private:
1301 : #ifndef BOOST_JSON_DOCS
1302 : // VFALCO friending a detail function makes it public
1303 : template<class CharRange>
1304 : friend
1305 : std::pair<key_value_pair*, std::size_t>
1306 : detail::find_in_object(
1307 : object const& obj,
1308 : CharRange key) noexcept;
1309 : #endif
1310 :
1311 : template<class InputIt>
1312 : void
1313 : construct(
1314 : InputIt first,
1315 : InputIt last,
1316 : std::size_t min_capacity,
1317 : std::input_iterator_tag);
1318 :
1319 : template<class InputIt>
1320 : void
1321 : construct(
1322 : InputIt first,
1323 : InputIt last,
1324 : std::size_t min_capacity,
1325 : std::forward_iterator_tag);
1326 :
1327 : template<class InputIt>
1328 : void
1329 : insert(
1330 : InputIt first,
1331 : InputIt last,
1332 : std::input_iterator_tag);
1333 :
1334 : template<class InputIt>
1335 : void
1336 : insert(
1337 : InputIt first,
1338 : InputIt last,
1339 : std::forward_iterator_tag);
1340 :
1341 : template< class... Args >
1342 : std::pair<iterator, bool>
1343 : emplace_impl(string_view key, Args&& ... args );
1344 :
1345 : BOOST_JSON_DECL
1346 : key_value_pair*
1347 : insert_impl(
1348 : pilfered<key_value_pair> p,
1349 : std::size_t hash);
1350 :
1351 : BOOST_JSON_DECL
1352 : table*
1353 : reserve_impl(std::size_t new_capacity);
1354 :
1355 : BOOST_JSON_DECL
1356 : bool
1357 : equal(object const& other) const noexcept;
1358 :
1359 : inline
1360 : std::size_t
1361 : growth(
1362 : std::size_t new_size) const;
1363 :
1364 : inline
1365 : void
1366 : remove(
1367 : index_t& head,
1368 : key_value_pair& p) noexcept;
1369 :
1370 : inline
1371 : void
1372 : destroy() noexcept;
1373 :
1374 : inline
1375 : void
1376 : destroy(
1377 : key_value_pair* first,
1378 : key_value_pair* last) noexcept;
1379 :
1380 : template<class FS, class FB>
1381 : auto
1382 : do_erase(
1383 : const_iterator pos,
1384 : FS small_reloc,
1385 : FB big_reloc) noexcept
1386 : -> iterator;
1387 :
1388 : inline
1389 : void
1390 : reindex_relocate(
1391 : key_value_pair* src,
1392 : key_value_pair* dst) noexcept;
1393 : };
1394 :
1395 : } // namespace json
1396 : } // namespace boost
1397 :
1398 : #ifndef BOOST_JSON_DOCS
1399 : // boost::hash trait
1400 : namespace boost
1401 : {
1402 : namespace container_hash
1403 : {
1404 :
1405 : template< class T > struct is_unordered_range;
1406 :
1407 : template<>
1408 : struct is_unordered_range< json::object >
1409 : : std::true_type
1410 : {};
1411 :
1412 : } // namespace container_hash
1413 : } // namespace boost
1414 :
1415 : // std::hash specialization
1416 : namespace std {
1417 : template <>
1418 : struct hash< ::boost::json::object > {
1419 : BOOST_JSON_DECL
1420 : std::size_t
1421 : operator()(::boost::json::object const& jo) const noexcept;
1422 : };
1423 : } // std
1424 : #endif
1425 :
1426 :
1427 : // Must be included here for this file to stand alone
1428 : #include <boost/json/value.hpp>
1429 :
1430 : // includes are at the bottom of <boost/json/value.hpp>
1431 :
1432 : #endif
|
