libstdc++
stl_pair.h
Go to the documentation of this file.
1// Pair implementation -*- C++ -*-
2
3// Copyright (C) 2001-2020 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#endif
67
68namespace std _GLIBCXX_VISIBILITY(default)
69{
70_GLIBCXX_BEGIN_NAMESPACE_VERSION
71
72 /**
73 * @addtogroup utilities
74 * @{
75 */
76
77#if __cplusplus >= 201103L
78 /// Tag type for piecewise construction of std::pair objects.
79 struct piecewise_construct_t { explicit piecewise_construct_t() = default; };
80
81 /// Tag for piecewise construction of std::pair objects.
82 _GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct =
84
85 /// @cond undocumented
86
87 // Forward declarations.
88 template<typename...>
89 class tuple;
90
91 template<std::size_t...>
92 struct _Index_tuple;
93
94 // Concept utility functions, reused in conditionally-explicit
95 // constructors.
96 // See PR 70437, don't look at is_constructible or
97 // is_convertible if the types are the same to
98 // avoid querying those properties for incomplete types.
99 template <bool, typename _T1, typename _T2>
100 struct _PCC
101 {
102 template <typename _U1, typename _U2>
103 static constexpr bool _ConstructiblePair()
104 {
105 return __and_<is_constructible<_T1, const _U1&>,
107 }
108
109 template <typename _U1, typename _U2>
110 static constexpr bool _ImplicitlyConvertiblePair()
111 {
112 return __and_<is_convertible<const _U1&, _T1>,
113 is_convertible<const _U2&, _T2>>::value;
114 }
115
116 template <typename _U1, typename _U2>
117 static constexpr bool _MoveConstructiblePair()
118 {
119 return __and_<is_constructible<_T1, _U1&&>,
120 is_constructible<_T2, _U2&&>>::value;
121 }
122
123 template <typename _U1, typename _U2>
124 static constexpr bool _ImplicitlyMoveConvertiblePair()
125 {
126 return __and_<is_convertible<_U1&&, _T1>,
127 is_convertible<_U2&&, _T2>>::value;
128 }
129
130 template <bool __implicit, typename _U1, typename _U2>
131 static constexpr bool _CopyMovePair()
132 {
133 using __do_converts = __and_<is_convertible<const _U1&, _T1>,
134 is_convertible<_U2&&, _T2>>;
135 using __converts = typename conditional<__implicit,
136 __do_converts,
137 __not_<__do_converts>>::type;
138 return __and_<is_constructible<_T1, const _U1&>,
139 is_constructible<_T2, _U2&&>,
140 __converts
141 >::value;
142 }
143
144 template <bool __implicit, typename _U1, typename _U2>
145 static constexpr bool _MoveCopyPair()
146 {
147 using __do_converts = __and_<is_convertible<_U1&&, _T1>,
148 is_convertible<const _U2&, _T2>>;
149 using __converts = typename conditional<__implicit,
150 __do_converts,
151 __not_<__do_converts>>::type;
152 return __and_<is_constructible<_T1, _U1&&>,
153 is_constructible<_T2, const _U2&&>,
154 __converts
155 >::value;
156 }
157 };
158
159 template <typename _T1, typename _T2>
160 struct _PCC<false, _T1, _T2>
161 {
162 template <typename _U1, typename _U2>
163 static constexpr bool _ConstructiblePair()
164 {
165 return false;
166 }
167
168 template <typename _U1, typename _U2>
169 static constexpr bool _ImplicitlyConvertiblePair()
170 {
171 return false;
172 }
173
174 template <typename _U1, typename _U2>
175 static constexpr bool _MoveConstructiblePair()
176 {
177 return false;
178 }
179
180 template <typename _U1, typename _U2>
181 static constexpr bool _ImplicitlyMoveConvertiblePair()
182 {
183 return false;
184 }
185 };
186#endif // C++11
187
188 template<typename _U1, typename _U2> class __pair_base
189 {
190#if __cplusplus >= 201103L
191 template<typename _T1, typename _T2> friend struct pair;
192 __pair_base() = default;
193 ~__pair_base() = default;
194 __pair_base(const __pair_base&) = default;
195 __pair_base& operator=(const __pair_base&) = delete;
196#endif // C++11
197 };
198
199 /// @endcond
200
201 /**
202 * @brief Struct holding two objects of arbitrary type.
203 *
204 * @tparam _T1 Type of first object.
205 * @tparam _T2 Type of second object.
206 *
207 * <https://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html>
208 */
209 template<typename _T1, typename _T2>
210 struct pair
211 : private __pair_base<_T1, _T2>
212 {
213 typedef _T1 first_type; ///< The type of the `first` member
214 typedef _T2 second_type; ///< The type of the `second` member
215
216 _T1 first; ///< The first member
217 _T2 second; ///< The second member
218
219 // _GLIBCXX_RESOLVE_LIB_DEFECTS
220 // 265. std::pair::pair() effects overly restrictive
221 /** The default constructor creates @c first and @c second using their
222 * respective default constructors. */
223#if __cplusplus >= 201103L
224 template <typename _U1 = _T1,
225 typename _U2 = _T2,
226 typename enable_if<__and_<
227 __is_implicitly_default_constructible<_U1>,
228 __is_implicitly_default_constructible<_U2>>
229 ::value, bool>::type = true>
230#endif
231 _GLIBCXX_CONSTEXPR pair()
232 : first(), second() { }
233
234#if __cplusplus >= 201103L
235 template <typename _U1 = _T1,
236 typename _U2 = _T2,
237 typename enable_if<__and_<
240 __not_<
241 __and_<__is_implicitly_default_constructible<_U1>,
242 __is_implicitly_default_constructible<_U2>>>>
243 ::value, bool>::type = false>
244 explicit constexpr pair()
245 : first(), second() { }
246#endif
247
248#if __cplusplus < 201103L
249 /// Two objects may be passed to a @c pair constructor to be copied.
250 pair(const _T1& __a, const _T2& __b)
251 : first(__a), second(__b) { }
252#else
253 // Shortcut for constraining the templates that don't take pairs.
254 /// @cond undocumented
255 using _PCCP = _PCC<true, _T1, _T2>;
256 /// @endcond
257
258 /// Construct from two const lvalues, allowing implicit conversions.
259 template<typename _U1 = _T1, typename _U2=_T2, typename
260 enable_if<_PCCP::template
261 _ConstructiblePair<_U1, _U2>()
262 && _PCCP::template
263 _ImplicitlyConvertiblePair<_U1, _U2>(),
264 bool>::type=true>
265 constexpr pair(const _T1& __a, const _T2& __b)
266 : first(__a), second(__b) { }
267
268 /// Construct from two const lvalues, disallowing implicit conversions.
269 template<typename _U1 = _T1, typename _U2=_T2, typename
270 enable_if<_PCCP::template
271 _ConstructiblePair<_U1, _U2>()
272 && !_PCCP::template
273 _ImplicitlyConvertiblePair<_U1, _U2>(),
274 bool>::type=false>
275 explicit constexpr pair(const _T1& __a, const _T2& __b)
276 : first(__a), second(__b) { }
277#endif
278
279#if __cplusplus < 201103L
280 /// There is also a templated constructor to convert from other pairs.
281 template<typename _U1, typename _U2>
282 pair(const pair<_U1, _U2>& __p)
283 : first(__p.first), second(__p.second) { }
284#else
285 // Shortcut for constraining the templates that take pairs.
286 /// @cond undocumented
287 template <typename _U1, typename _U2>
288 using _PCCFP = _PCC<!is_same<_T1, _U1>::value
289 || !is_same<_T2, _U2>::value,
290 _T1, _T2>;
291 /// @endcond
292
293 template<typename _U1, typename _U2, typename
294 enable_if<_PCCFP<_U1, _U2>::template
295 _ConstructiblePair<_U1, _U2>()
296 && _PCCFP<_U1, _U2>::template
297 _ImplicitlyConvertiblePair<_U1, _U2>(),
298 bool>::type=true>
299 constexpr pair(const pair<_U1, _U2>& __p)
300 : first(__p.first), second(__p.second) { }
301
302 template<typename _U1, typename _U2, typename
303 enable_if<_PCCFP<_U1, _U2>::template
304 _ConstructiblePair<_U1, _U2>()
305 && !_PCCFP<_U1, _U2>::template
306 _ImplicitlyConvertiblePair<_U1, _U2>(),
307 bool>::type=false>
308 explicit constexpr pair(const pair<_U1, _U2>& __p)
309 : first(__p.first), second(__p.second) { }
310#endif
311
312#if __cplusplus >= 201103L
313 constexpr pair(const pair&) = default; ///< Copy constructor
314 constexpr pair(pair&&) = default; ///< Move constructor
315
316 // DR 811.
317 template<typename _U1, typename
318 enable_if<_PCCP::template
319 _MoveCopyPair<true, _U1, _T2>(),
320 bool>::type=true>
321 constexpr pair(_U1&& __x, const _T2& __y)
322 : first(std::forward<_U1>(__x)), second(__y) { }
323
324 template<typename _U1, typename
325 enable_if<_PCCP::template
326 _MoveCopyPair<false, _U1, _T2>(),
327 bool>::type=false>
328 explicit constexpr pair(_U1&& __x, const _T2& __y)
329 : first(std::forward<_U1>(__x)), second(__y) { }
330
331 template<typename _U2, typename
332 enable_if<_PCCP::template
333 _CopyMovePair<true, _T1, _U2>(),
334 bool>::type=true>
335 constexpr pair(const _T1& __x, _U2&& __y)
336 : first(__x), second(std::forward<_U2>(__y)) { }
337
338 template<typename _U2, typename
339 enable_if<_PCCP::template
340 _CopyMovePair<false, _T1, _U2>(),
341 bool>::type=false>
342 explicit pair(const _T1& __x, _U2&& __y)
343 : first(__x), second(std::forward<_U2>(__y)) { }
344
345 template<typename _U1, typename _U2, typename
346 enable_if<_PCCP::template
347 _MoveConstructiblePair<_U1, _U2>()
348 && _PCCP::template
349 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
350 bool>::type=true>
351 constexpr pair(_U1&& __x, _U2&& __y)
352 : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
353
354 template<typename _U1, typename _U2, typename
355 enable_if<_PCCP::template
356 _MoveConstructiblePair<_U1, _U2>()
357 && !_PCCP::template
358 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
359 bool>::type=false>
360 explicit constexpr pair(_U1&& __x, _U2&& __y)
361 : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
362
363
364 template<typename _U1, typename _U2, typename
365 enable_if<_PCCFP<_U1, _U2>::template
366 _MoveConstructiblePair<_U1, _U2>()
367 && _PCCFP<_U1, _U2>::template
368 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
369 bool>::type=true>
370 constexpr pair(pair<_U1, _U2>&& __p)
371 : first(std::forward<_U1>(__p.first)),
372 second(std::forward<_U2>(__p.second)) { }
373
374 template<typename _U1, typename _U2, typename
375 enable_if<_PCCFP<_U1, _U2>::template
376 _MoveConstructiblePair<_U1, _U2>()
377 && !_PCCFP<_U1, _U2>::template
378 _ImplicitlyMoveConvertiblePair<_U1, _U2>(),
379 bool>::type=false>
380 explicit constexpr pair(pair<_U1, _U2>&& __p)
381 : first(std::forward<_U1>(__p.first)),
382 second(std::forward<_U2>(__p.second)) { }
383
384 template<typename... _Args1, typename... _Args2>
385 _GLIBCXX20_CONSTEXPR
386 pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
387
388 _GLIBCXX20_CONSTEXPR pair&
389 operator=(typename conditional<
390 __and_<is_copy_assignable<_T1>,
391 is_copy_assignable<_T2>>::value,
392 const pair&, const __nonesuch&>::type __p)
393 {
394 first = __p.first;
395 second = __p.second;
396 return *this;
397 }
398
399 _GLIBCXX20_CONSTEXPR pair&
400 operator=(typename conditional<
401 __and_<is_move_assignable<_T1>,
402 is_move_assignable<_T2>>::value,
403 pair&&, __nonesuch&&>::type __p)
404 noexcept(__and_<is_nothrow_move_assignable<_T1>,
405 is_nothrow_move_assignable<_T2>>::value)
406 {
407 first = std::forward<first_type>(__p.first);
408 second = std::forward<second_type>(__p.second);
409 return *this;
410 }
411
412 template<typename _U1, typename _U2>
413 _GLIBCXX20_CONSTEXPR
414 typename enable_if<__and_<is_assignable<_T1&, const _U1&>,
415 is_assignable<_T2&, const _U2&>>::value,
416 pair&>::type
417 operator=(const pair<_U1, _U2>& __p)
418 {
419 first = __p.first;
420 second = __p.second;
421 return *this;
422 }
423
424 template<typename _U1, typename _U2>
425 _GLIBCXX20_CONSTEXPR
426 typename enable_if<__and_<is_assignable<_T1&, _U1&&>,
427 is_assignable<_T2&, _U2&&>>::value,
428 pair&>::type
429 operator=(pair<_U1, _U2>&& __p)
430 {
431 first = std::forward<_U1>(__p.first);
432 second = std::forward<_U2>(__p.second);
433 return *this;
434 }
435
436 /// Swap the first members and then the second members.
437 _GLIBCXX20_CONSTEXPR void
438 swap(pair& __p)
439 noexcept(__and_<__is_nothrow_swappable<_T1>,
440 __is_nothrow_swappable<_T2>>::value)
441 {
442 using std::swap;
443 swap(first, __p.first);
444 swap(second, __p.second);
445 }
446
447 private:
448 template<typename... _Args1, std::size_t... _Indexes1,
449 typename... _Args2, std::size_t... _Indexes2>
450 _GLIBCXX20_CONSTEXPR
452 _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
453#endif // C++11
454 };
455
456 /// @relates pair @{
457
458#if __cpp_deduction_guides >= 201606
459 template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>;
460#endif
461
462 /// Two pairs of the same type are equal iff their members are equal.
463 template<typename _T1, typename _T2>
464 inline _GLIBCXX_CONSTEXPR bool
466 { return __x.first == __y.first && __x.second == __y.second; }
467
468#if __cpp_lib_three_way_comparison && __cpp_lib_concepts
469 template<typename _T1, typename _T2>
470 constexpr common_comparison_category_t<__detail::__synth3way_t<_T1>,
471 __detail::__synth3way_t<_T2>>
472 operator<=>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
473 {
474 if (auto __c = __detail::__synth3way(__x.first, __y.first); __c != 0)
475 return __c;
476 return __detail::__synth3way(__x.second, __y.second);
477 }
478#else
479 /** Defines a lexicographical order for pairs.
480 *
481 * For two pairs of the same type, `P` is ordered before `Q` if
482 * `P.first` is less than `Q.first`, or if `P.first` and `Q.first`
483 * are equivalent (neither is less than the other) and `P.second` is less
484 * than `Q.second`.
485 */
486 template<typename _T1, typename _T2>
487 inline _GLIBCXX_CONSTEXPR bool
488 operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
489 { return __x.first < __y.first
490 || (!(__y.first < __x.first) && __x.second < __y.second); }
491
492 /// Uses @c operator== to find the result.
493 template<typename _T1, typename _T2>
494 inline _GLIBCXX_CONSTEXPR bool
496 { return !(__x == __y); }
497
498 /// Uses @c operator< to find the result.
499 template<typename _T1, typename _T2>
500 inline _GLIBCXX_CONSTEXPR bool
502 { return __y < __x; }
503
504 /// Uses @c operator< to find the result.
505 template<typename _T1, typename _T2>
506 inline _GLIBCXX_CONSTEXPR bool
507 operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
508 { return !(__y < __x); }
509
510 /// Uses @c operator< to find the result.
511 template<typename _T1, typename _T2>
512 inline _GLIBCXX_CONSTEXPR bool
514 { return !(__x < __y); }
515#endif // !(three_way_comparison && concepts)
516
517#if __cplusplus >= 201103L
518 /** Swap overload for pairs. Calls std::pair::swap().
519 *
520 * @note This std::swap overload is not declared in C++03 mode,
521 * which has performance implications, e.g. see https://gcc.gnu.org/PR38466
522 */
523 template<typename _T1, typename _T2>
524 _GLIBCXX20_CONSTEXPR inline
525#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
526 // Constrained free swap overload, see p0185r1
528 __is_swappable<_T2>>::value>::type
529#else
530 void
531#endif
533 noexcept(noexcept(__x.swap(__y)))
534 { __x.swap(__y); }
535
536#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
537 template<typename _T1, typename _T2>
539 __is_swappable<_T2>>::value>::type
540 swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
541#endif
542#endif // __cplusplus >= 201103L
543
544 // @} relates pair
545
546 /**
547 * @brief A convenience wrapper for creating a pair from two objects.
548 * @param __x The first object.
549 * @param __y The second object.
550 * @return A newly-constructed pair<> object of the appropriate type.
551 *
552 * The C++98 standard says the objects are passed by reference-to-const,
553 * but C++03 says they are passed by value (this was LWG issue #181).
554 *
555 * Since C++11 they have been passed by forwarding reference and then
556 * forwarded to the new members of the pair. To create a pair with a
557 * member of reference type, pass a `reference_wrapper` to this function.
558 */
559 // _GLIBCXX_RESOLVE_LIB_DEFECTS
560 // 181. make_pair() unintended behavior
561#if __cplusplus >= 201103L
562 // NB: DR 706.
563 template<typename _T1, typename _T2>
565 typename __decay_and_strip<_T2>::__type>
566 make_pair(_T1&& __x, _T2&& __y)
567 {
568 typedef typename __decay_and_strip<_T1>::__type __ds_type1;
569 typedef typename __decay_and_strip<_T2>::__type __ds_type2;
570 typedef pair<__ds_type1, __ds_type2> __pair_type;
571 return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));
572 }
573#else
574 template<typename _T1, typename _T2>
575 inline pair<_T1, _T2>
576 make_pair(_T1 __x, _T2 __y)
577 { return pair<_T1, _T2>(__x, __y); }
578#endif
579
580 /// @}
581
582_GLIBCXX_END_NAMESPACE_VERSION
583} // namespace std
584
585#endif /* _STL_PAIR_H */
constexpr pair(const _T1 &__a, const _T2 &__b)
Construct from two const lvalues, allowing implicit conversions.
Definition: stl_pair.h:265
_T1 first
The first member.
Definition: stl_pair.h:216
constexpr bool operator>(const pair< _T1, _T2 > &__x, const pair< _T1, _T2 > &__y)
Uses operator< to find the result.
Definition: stl_pair.h:501
_T1 first_type
The type of the first member.
Definition: stl_pair.h:213
constexpr bool operator!=(const pair< _T1, _T2 > &__x, const pair< _T1, _T2 > &__y)
Uses operator== to find the result.
Definition: stl_pair.h:495
constexpr void swap(pair &__p) noexcept(__and_< __is_nothrow_swappable< _T1 >, __is_nothrow_swappable< _T2 > >::value)
Swap the first members and then the second members.
Definition: stl_pair.h:438
constexpr bool operator==(const pair< _T1, _T2 > &__x, const pair< _T1, _T2 > &__y)
Definition: stl_pair.h:465
constexpr bool operator>=(const pair< _T1, _T2 > &__x, const pair< _T1, _T2 > &__y)
Uses operator< to find the result.
Definition: stl_pair.h:513
constexpr pair(const pair &)=default
Copy constructor.
constexpr pair()
Definition: stl_pair.h:231
_T2 second_type
The type of the second member.
Definition: stl_pair.h:214
constexpr pair(pair &&)=default
Move constructor.
constexpr enable_if< __and_< __is_swappable< _T1 >, __is_swappable< _T2 > >::value >::type swap(pair< _T1, _T2 > &__x, pair< _T1, _T2 > &__y) noexcept(noexcept(__x.swap(__y)))
Definition: stl_pair.h:532
_T2 second
The second member.
Definition: stl_pair.h:217
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
Definition: stl_pair.h:82
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:566
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:76
ISO C++ entities toplevel namespace is std.
Primary class template, tuple.
Definition: tuple:516
is_constructible
Definition: type_traits:908
is_default_constructible
Definition: type_traits:917
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:2170
Tag type for piecewise construction of std::pair objects.
Definition: stl_pair.h:79
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:212
constexpr pair(const _T1 &__a, const _T2 &__b)
Construct from two const lvalues, disallowing implicit conversions.
Definition: stl_pair.h:275