1// Pair implementation -*- C++ -*-
2
3// Copyright (C) 2001-2021 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_pair.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{utility}
54 */
55
56#ifndef _STL_PAIR_H
57#define _STL_PAIR_H 1
58
59#include <bits/move.h> // for std::move / std::forward, and std::swap
60
61#if __cplusplus >= 201103L
62# include <type_traits> // for std::__decay_and_strip, std::is_reference_v
63#endif
64#if __cplusplus > 201703L
65# include <compare>
66# define __cpp_lib_constexpr_utility 201811L
67#endif
68
69namespace std _GLIBCXX_VISIBILITY(default)
70{
71_GLIBCXX_BEGIN_NAMESPACE_VERSION
72
73 /**
74 * @addtogroup utilities
75 * @{
76 */
77
78#if __cplusplus >= 201103L
79 /// Tag type for piecewise construction of std::pair objects.
80 struct piecewise_construct_t { explicit piecewise_construct_t() = default; };
81
82 /// Tag for piecewise construction of std::pair objects.
83 _GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct =
84 piecewise_construct_t();
85
86 /// @cond undocumented
87
88 // Forward declarations.
89 template<typename...>
90 class tuple;
91
92 template<size_t...>
93 struct _Index_tuple;
94
95 // Concept utility functions, reused in conditionally-explicit
96 // constructors.
97 // See PR 70437, don't look at is_constructible or
98 // is_convertible if the types are the same to
99 // avoid querying those properties for incomplete types.
100 template <bool, typename _T1, typename _T2>
101 struct _PCC
102 {
103 template <typename _U1, typename _U2>
104 static constexpr bool _ConstructiblePair()
105 {
106 return __and_<is_constructible<_T1, const _U1&>,
107 is_constructible<_T2, const _U2&>>::value;
108 }
109
110 template <typename _U1, typename _U2>
111 static constexpr bool _ImplicitlyConvertiblePair()
112 {
113 return __and_<is_convertible<const _U1&, _T1>,
114 is_convertible<const _U2&, _T2>>::value;
115 }
116
117 template <typename _U1, typename _U2>
118 static constexpr bool _MoveConstructiblePair()
119 {
120 return __and_<is_constructible<_T1, _U1&&>,
121 is_constructible<_T2, _U2&&>>::value;
122 }
123
124 template <typename _U1, typename _U2>
125 static constexpr bool _ImplicitlyMoveConvertiblePair()
126 {
127 return __and_<is_convertible<_U1&&, _T1>,
128 is_convertible<_U2&&, _T2>>::value;
129 }
130
131 template <bool __implicit, typename _U1, typename _U2>
132 static constexpr bool _CopyMovePair()
133 {
134 using __do_converts = __and_<is_convertible<const _U1&, _T1>,
135 is_convertible<_U2&&, _T2>>;
136 using __converts = typename conditional<__implicit,
137 __do_converts,
138 __not_<__do_converts>>::type;
139 return __and_<is_constructible<_T1, const _U1&>,
140 is_constructible<_T2, _U2&&>,
141 __converts
142 >::value;
143 }
144
145 template <bool __implicit, typename _U1, typename _U2>
146 static constexpr bool _MoveCopyPair()
147 {
148 using __do_converts = __and_<is_convertible<_U1&&, _T1>,
149 is_convertible<const _U2&, _T2>>;
150 using __converts = typename conditional<__implicit,
151 __do_converts,
152 __not_<__do_converts>>::type;
153 return __and_<is_constructible<_T1, _U1&&>,
154 is_constructible<_T2, const _U2&&>,
155 __converts
156 >::value;
157 }
158 };
159
160 template <typename _T1, typename _T2>
161 struct _PCC<false, _T1, _T2>
162 {
163 template <typename _U1, typename _U2>
164 static constexpr bool _ConstructiblePair()
165 {
166 return false;
167 }
168
169 template <typename _U1, typename _U2>
170 static constexpr bool _ImplicitlyConvertiblePair()
171 {
172 return false;
173 }
174
175 template <typename _U1, typename _U2>
176 static constexpr bool _MoveConstructiblePair()
177 {
178 return false;
179 }
180
181 template <typename _U1, typename _U2>
182 static constexpr bool _ImplicitlyMoveConvertiblePair()
183 {
184 return false;
185 }
186 };
187#endif // C++11
188
189 template<typename _U1, typename _U2> class __pair_base
190 {
191#if __cplusplus >= 201103L
192 template<typename _T1, typename _T2> friend struct pair;
193 __pair_base() = default;
194 ~__pair_base() = default;
195 __pair_base(const __pair_base&) = default;
196 __pair_base& operator=(const __pair_base&) = delete;
197#endif // C++11
198 };
199
200 /// @endcond
201
202 /**
203 * @brief Struct holding two objects of arbitrary type.
204 *
205 * @tparam _T1 Type of first object.
206 * @tparam _T2 Type of second object.
207 *
208 * <https://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
209 */
210 template<typename _T1, typename _T2>
211 struct pair
212 : private __pair_base<_T1, _T2>
213 {
214 typedef _T1 first_type; ///< The type of the `first` member
215 typedef _T2 second_type; ///< The type of the `second` member
216
217 _T1 first; ///< The first member
218 _T2 second; ///< The second member
219
220 // _GLIBCXX_RESOLVE_LIB_DEFECTS
221 // 265. std::pair::pair() effects overly restrictive
222 /** The default constructor creates @c first and @c second using their
223 * respective default constructors. */
224#if __cplusplus >= 201103L
225 template <typename _U1 = _T1,
226 typename _U2 = _T2,
227 typename enable_if<__and_<
228 __is_implicitly_default_constructible<_U1>,
229 __is_implicitly_default_constructible<_U2>>
230 ::value, bool>::type = true>
231#endif
232 _GLIBCXX_CONSTEXPR pair()
233 : first(), second() { }
234
235#if __cplusplus >= 201103L
236 template <typename _U1 = _T1,
237 typename _U2 = _T2,
238 typename enable_if<__and_<
239 is_default_constructible<_U1>,
240 is_default_constructible<_U2>,
241 __not_<
242 __and_<__is_implicitly_default_constructible<_U1>,
243 __is_implicitly_default_constructible<_U2>>>>
244 ::value, bool>::type = false>
245 explicit constexpr pair()
246 : first(), second() { }
247#endif
248
249#if __cplusplus < 201103L
250 /// Two objects may be passed to a @c pair constructor to be copied.
251 pair(const _T1& __a, const _T2& __b)
252 : first(__a), second(__b) { }
253#else
254 // Shortcut for constraining the templates that don't take pairs.
255 /// @cond undocumented
256 using _PCCP = _PCC<true, _T1, _T2>;
257 /// @endcond
258
259 /// Construct from two const lvalues, allowing implicit conversions.
260 template<typename _U1 = _T1, typename _U2=_T2, typename
261 enable_if<_PCCP::template
262 _ConstructiblePair<_U1, _U2>()
263 && _PCCP::template
264 _ImplicitlyConvertiblePair<_U1, _U2>(),
265 bool>::type=true>
266 constexpr pair(const _T1& __a, const _T2& __b)
267 : first(__a), second(__b) { }
268
269 /// Construct from two const lvalues, disallowing implicit conversions.
270 template<typename _U1 = _T1, typename _U2=_T2, typename
271 enable_if<_PCCP::template
272 _ConstructiblePair<_U1, _U2>()
273 && !_PCCP::template
274 _ImplicitlyConvertiblePair<_U1, _U2>(),
275 bool>::type=false>
276 explicit constexpr pair(const _T1& __a, const _T2& __b)
277 : first(__a), second(__b) { }
278#endif
279
280#if __cplusplus < 201103L
281 /// There is also a templated constructor to convert from other pairs.
282 template<typename _U1, typename _U2>
283 pair(const pair<_U1, _U2>& __p)
284 : first(__p.first), second(__p.second) { }
285#else
286 // Shortcut for constraining the templates that take pairs.
287 /// @cond undocumented
288 template <typename _U1, typename _U2>
289 using _PCCFP = _PCC<!is_same<_T1, _U1>::value
290 || !is_same<_T2, _U2>::value,
291 _T1, _T2>;
292 /// @endcond
293
294 template<typename _U1, typename _U2, typename
295 enable_if<_PCCFP<_U1, _U2>::template
296 _ConstructiblePair<_U1, _U2>()
297 && _PCCFP<_U1, _U2>::template
298 _ImplicitlyConvertiblePair<_U1, _U2>(),
299 bool>::type=true>
300 constexpr pair(const pair<_U1, _U2>& __p)
301 : first(__p.first), second(__p.second) { }
302
303 template<typename _U1, typename _U2, typename
304 enable_if<_PCCFP<_U1, _U2>::template
305 _ConstructiblePair<_U1, _U2>()
306 && !_PCCFP<_U1, _U2>::template
307 _ImplicitlyConvertiblePair<_U1, _U2>(),
308 bool>::type=false>
309 explicit constexpr pair(const pair<_U1, _U2>& __p)
310 : first(__p.first), second(__p.second) { }
311#endif
312
313#if __cplusplus >= 201103L
314 constexpr pair(const pair&) = default; ///< Copy constructor
315 constexpr pair(pair&&) = default; ///< Move constructor
316
317 // DR 811.
318 template<typename _U1, typename
319 enable_if<_PCCP::template
320 _MoveCopyPair<true, _U1, _T2>(),
321 bool>::type=true>
322 constexpr pair(_U1&& __x, const _T2& __y)
323 : first(std::forward<_U1>(__x)), second(__y) { }
324
325 template<typename _U1, typename
326 enable_if<_PCCP::template
327 _MoveCopyPair<false, _U1, _T2>(),
328 bool>::type=false>
329 explicit constexpr pair(_U1&& __x, const _T2& __y)
330 : first(std::forward<_U1>(__x)), second(__y) { }
331
332 template<typename _U2, typename
333 enable_if<_PCCP::template
334 _CopyMovePair<true, _T1, _U2>(),
335 bool>::type=true>
336 constexpr pair(const _T1& __x, _U2&& __y)
337 : first(__x), second(std::forward<_U2>(__y)) { }
338
339 template<typename _U2, typename
340 enable_if<_PCCP::template
341 _CopyMovePair<false, _T1, _U2>(),
342 bool>::type=false>
343 explicit pair(const _T1& __x, _U2&& __y)
344 : first(__x), second(std::forward<_U2>(__y)) { }
345
346 template<typename _U1, typename _U2, typename
347 enable_if<_PCCP::template
348 _MoveConstructiblePair<_U1, _U2>()
349 && _PCCP::template
350 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
351 bool>::type=true>
352 constexpr pair(_U1&& __x, _U2&& __y)
353 : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
354
355 template<typename _U1, typename _U2, typename
356 enable_if<_PCCP::template
357 _MoveConstructiblePair<_U1, _U2>()
358 && !_PCCP::template
359 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
360 bool>::type=false>
361 explicit constexpr pair(_U1&& __x, _U2&& __y)
362 : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
363
364
365 template<typename _U1, typename _U2, typename
366 enable_if<_PCCFP<_U1, _U2>::template
367 _MoveConstructiblePair<_U1, _U2>()
368 && _PCCFP<_U1, _U2>::template
369 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
370 bool>::type=true>
371 constexpr pair(pair<_U1, _U2>&& __p)
372 : first(std::forward<_U1>(__p.first)),
373 second(std::forward<_U2>(__p.second)) { }
374
375 template<typename _U1, typename _U2, typename
376 enable_if<_PCCFP<_U1, _U2>::template
377 _MoveConstructiblePair<_U1, _U2>()
378 && !_PCCFP<_U1, _U2>::template
379 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
380 bool>::type=false>
381 explicit constexpr pair(pair<_U1, _U2>&& __p)
382 : first(std::forward<_U1>(__p.first)),
383 second(std::forward<_U2>(__p.second)) { }
384
385 template<typename... _Args1, typename... _Args2>
386 _GLIBCXX20_CONSTEXPR
387 pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
388
389 _GLIBCXX20_CONSTEXPR pair&
390 operator=(typename conditional<
391 __and_<is_copy_assignable<_T1>,
392 is_copy_assignable<_T2>>::value,
393 const pair&, const __nonesuch&>::type __p)
394 {
395 first = __p.first;
396 second = __p.second;
397 return *this;
398 }
399
400 _GLIBCXX20_CONSTEXPR pair&
401 operator=(typename conditional<
402 __and_<is_move_assignable<_T1>,
403 is_move_assignable<_T2>>::value,
404 pair&&, __nonesuch&&>::type __p)
405 noexcept(__and_<is_nothrow_move_assignable<_T1>,
406 is_nothrow_move_assignable<_T2>>::value)
407 {
408 first = std::forward<first_type>(__p.first);
409 second = std::forward<second_type>(__p.second);
410 return *this;
411 }
412
413 template<typename _U1, typename _U2>
414 _GLIBCXX20_CONSTEXPR
415 typename enable_if<__and_<is_assignable<_T1&, const _U1&>,
416 is_assignable<_T2&, const _U2&>>::value,
417 pair&>::type
418 operator=(const pair<_U1, _U2>& __p)
419 {
420 first = __p.first;
421 second = __p.second;
422 return *this;
423 }
424
425 template<typename _U1, typename _U2>
426 _GLIBCXX20_CONSTEXPR
427 typename enable_if<__and_<is_assignable<_T1&, _U1&&>,
428 is_assignable<_T2&, _U2&&>>::value,
429 pair&>::type
430 operator=(pair<_U1, _U2>&& __p)
431 {
432 first = std::forward<_U1>(__p.first);
433 second = std::forward<_U2>(__p.second);
434 return *this;
435 }
436
437 /// Swap the first members and then the second members.
438 _GLIBCXX20_CONSTEXPR void
439 swap(pair& __p)
440 noexcept(__and_<__is_nothrow_swappable<_T1>,
441 __is_nothrow_swappable<_T2>>::value)
442 {
443 using std::swap;
444 swap(first, __p.first);
445 swap(second, __p.second);
446 }
447
448 private:
449 template<typename... _Args1, size_t... _Indexes1,
450 typename... _Args2, size_t... _Indexes2>
451 _GLIBCXX20_CONSTEXPR
452 pair(tuple<_Args1...>&, tuple<_Args2...>&,
453 _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
454#endif // C++11
455 };
456
457 /// @relates pair @{
458
459#if __cpp_deduction_guides >= 201606
460 template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>;
461#endif
462
463 /// Two pairs of the same type are equal iff their members are equal.
464 template<typename _T1, typename _T2>
465 inline _GLIBCXX_CONSTEXPR bool
466 operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
467 { return __x.first == __y.first && __x.second == __y.second; }
468
469#if __cpp_lib_three_way_comparison && __cpp_lib_concepts
470 template<typename _T1, typename _T2>
471 constexpr common_comparison_category_t<__detail::__synth3way_t<_T1>,
472 __detail::__synth3way_t<_T2>>
473 operator<=>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
474 {
475 if (auto __c = __detail::__synth3way(__x.first, __y.first); __c != 0)
476 return __c;
477 return __detail::__synth3way(__x.second, __y.second);
478 }
479#else
480 /** Defines a lexicographical order for pairs.
481 *
482 * For two pairs of the same type, `P` is ordered before `Q` if
483 * `P.first` is less than `Q.first`, or if `P.first` and `Q.first`
484 * are equivalent (neither is less than the other) and `P.second` is less
485 * than `Q.second`.
486 */
487 template<typename _T1, typename _T2>
488 inline _GLIBCXX_CONSTEXPR bool
489 operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
490 { return __x.first < __y.first
491 || (!(__y.first < __x.first) && __x.second < __y.second); }
492
493 /// Uses @c operator== to find the result.
494 template<typename _T1, typename _T2>
495 inline _GLIBCXX_CONSTEXPR bool
496 operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
497 { return !(__x == __y); }
498
499 /// Uses @c operator< to find the result.
500 template<typename _T1, typename _T2>
501 inline _GLIBCXX_CONSTEXPR bool
502 operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
503 { return __y < __x; }
504
505 /// Uses @c operator< to find the result.
506 template<typename _T1, typename _T2>
507 inline _GLIBCXX_CONSTEXPR bool
508 operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
509 { return !(__y < __x); }
510
511 /// Uses @c operator< to find the result.
512 template<typename _T1, typename _T2>
513 inline _GLIBCXX_CONSTEXPR bool
514 operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
515 { return !(__x < __y); }
516#endif // !(three_way_comparison && concepts)
517
518#if __cplusplus >= 201103L
519 /** Swap overload for pairs. Calls std::pair::swap().
520 *
521 * @note This std::swap overload is not declared in C++03 mode,
522 * which has performance implications, e.g. see https://gcc.gnu.org/PR38466
523 */
524 template<typename _T1, typename _T2>
525 _GLIBCXX20_CONSTEXPR inline
526#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
527 // Constrained free swap overload, see p0185r1
528 typename enable_if<__and_<__is_swappable<_T1>,
529 __is_swappable<_T2>>::value>::type
530#else
531 void
532#endif
533 swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
534 noexcept(noexcept(__x.swap(__y)))
535 { __x.swap(__y); }
536
537#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
538 template<typename _T1, typename _T2>
539 typename enable_if<!__and_<__is_swappable<_T1>,
540 __is_swappable<_T2>>::value>::type
541 swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
542#endif
543#endif // __cplusplus >= 201103L
544
545 /// @} relates pair
546
547 /**
548 * @brief A convenience wrapper for creating a pair from two objects.
549 * @param __x The first object.
550 * @param __y The second object.
551 * @return A newly-constructed pair<> object of the appropriate type.
552 *
553 * The C++98 standard says the objects are passed by reference-to-const,
554 * but C++03 says they are passed by value (this was LWG issue #181).
555 *
556 * Since C++11 they have been passed by forwarding reference and then
557 * forwarded to the new members of the pair. To create a pair with a
558 * member of reference type, pass a `reference_wrapper` to this function.
559 */
560 // _GLIBCXX_RESOLVE_LIB_DEFECTS
561 // 181. make_pair() unintended behavior
562#if __cplusplus >= 201103L
563 // NB: DR 706.
564 template<typename _T1, typename _T2>
565 constexpr pair<typename __decay_and_strip<_T1>::__type,
566 typename __decay_and_strip<_T2>::__type>
567 make_pair(_T1&& __x, _T2&& __y)
568 {
569 typedef typename __decay_and_strip<_T1>::__type __ds_type1;
570 typedef typename __decay_and_strip<_T2>::__type __ds_type2;
571 typedef pair<__ds_type1, __ds_type2> __pair_type;
572 return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
573 }
574#else
575 template<typename _T1, typename _T2>
576 inline pair<_T1, _T2>
577 make_pair(_T1 __x, _T2 __y)
578 { return pair<_T1, _T2>(__x, __y); }
579#endif
580
581 /// @}
582
583_GLIBCXX_END_NAMESPACE_VERSION
584} // namespace std
585
586#endif /* _STL_PAIR_H */
587

source code of include/c++/11/bits/stl_pair.h