Movatterモバイル変換

[0]ホーム
URL:

Google Git
Sign in
chromium /chromium /src /refs/heads/main /. /base /stl_util.h
blob: 3c2d97c7b17fb0691524bece86f78703868d534f [file] [log] [blame]
Avi Drissmane4622aa2022-09-08 20:36:06[diff] [blame]1// Copyright 2011 The Chromium Authors
dilmah@chromium.org7286e3fc2011-07-19 22:13:24[diff] [blame]2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Derived from google3/util/gtl/stl_util.h
6
7#ifndef BASE_STL_UTIL_H_
8#define BASE_STL_UTIL_H_
dilmah@chromium.org7286e3fc2011-07-19 22:13:24[diff] [blame]9
kalman@chromium.org1dea7572012-12-05 21:40:27[diff] [blame]10#include<algorithm>
mostynb@opera.comc014f2b32013-09-03 23:29:12[diff] [blame]11#include<iterator>
dilmah@chromium.org7286e3fc2011-07-19 22:13:24[diff] [blame]12
Hans Wennborg7b533712020-06-22 20:52:27[diff] [blame]13#include"base/check.h"
kalman@chromium.org1dea7572012-12-05 21:40:27[diff] [blame]14
skyostil68be7152016-08-09 22:18:00[diff] [blame]15namespacebase{
16
Dan Sanders97c13742018-05-17 23:12:32[diff] [blame]17// Returns a const reference to the underlying container of a container adapter.
18// Works for std::priority_queue, std::queue, and std::stack.
19template<class A>
20consttypename A::container_type&GetUnderlyingContainer(const A& adapter){
21structExposedAdapter: A{
22using A::c;
23};
24return adapter.*&ExposedAdapter::c;
25}
26
tfarina@chromium.org6ee951a2012-06-26 17:24:05[diff] [blame]27// Clears internal memory of an STL object.
dilmah@chromium.org7286e3fc2011-07-19 22:13:24[diff] [blame]28// STL clear()/reserve(0) does not always free internal memory allocated
29// This function uses swap/destructor to ensure the internal memory is freed.
Peter Kasting134ef9af2024-12-28 02:30:09[diff] [blame]30template<class T>
tfarina@chromium.org6ee951a2012-06-26 17:24:05[diff] [blame]31voidSTLClearObject(T* obj){
dilmah@chromium.org7286e3fc2011-07-19 22:13:24[diff] [blame]32 T tmp;
33 tmp.swap(*obj);
34// Sometimes "T tmp" allocates objects with memory (arena implementation?).
35// Hence using additional reserve(0) even if it doesn't always work.
36 obj->reserve(0);
37}
38
kalman@chromium.org1dea7572012-12-05 21:40:27[diff] [blame]39// Returns a new ResultType containing the difference of two sorted containers.
40template<typenameResultType,typenameArg1,typenameArg2>
41ResultTypeSTLSetDifference(constArg1& a1,constArg2& a2){
Peter Kasting025a94252025-01-29 21:28:37[diff] [blame]42 DCHECK(std::ranges::is_sorted(a1));
43 DCHECK(std::ranges::is_sorted(a2));
kalman@chromium.org1dea7572012-12-05 21:40:27[diff] [blame]44ResultType difference;
Peter Kasting134ef9af2024-12-28 02:30:09[diff] [blame]45 std::set_difference(a1.begin(), a1.end(), a2.begin(), a2.end(),
kalman@chromium.org1dea7572012-12-05 21:40:27[diff] [blame]46 std::inserter(difference, difference.end()));
47return difference;
48}
49
rpaquay@chromium.org9a53ade2014-01-29 17:13:27[diff] [blame]50// Returns a new ResultType containing the union of two sorted containers.
51template<typenameResultType,typenameArg1,typenameArg2>
52ResultTypeSTLSetUnion(constArg1& a1,constArg2& a2){
Peter Kasting025a94252025-01-29 21:28:37[diff] [blame]53 DCHECK(std::ranges::is_sorted(a1));
54 DCHECK(std::ranges::is_sorted(a2));
rpaquay@chromium.org9a53ade2014-01-29 17:13:27[diff] [blame]55ResultType result;
Peter Kasting134ef9af2024-12-28 02:30:09[diff] [blame]56 std::set_union(a1.begin(), a1.end(), a2.begin(), a2.end(),
rpaquay@chromium.org9a53ade2014-01-29 17:13:27[diff] [blame]57 std::inserter(result, result.end()));
58return result;
59}
60
61// Returns a new ResultType containing the intersection of two sorted
62// containers.
63template<typenameResultType,typenameArg1,typenameArg2>
64ResultTypeSTLSetIntersection(constArg1& a1,constArg2& a2){
Peter Kasting025a94252025-01-29 21:28:37[diff] [blame]65 DCHECK(std::ranges::is_sorted(a1));
66 DCHECK(std::ranges::is_sorted(a2));
rpaquay@chromium.org9a53ade2014-01-29 17:13:27[diff] [blame]67ResultType result;
Peter Kasting134ef9af2024-12-28 02:30:09[diff] [blame]68 std::set_intersection(a1.begin(), a1.end(), a2.begin(), a2.end(),
rpaquay@chromium.org9a53ade2014-01-29 17:13:27[diff] [blame]69 std::inserter(result, result.end()));
70return result;
71}
72
Kevin Bailey156ff6d2017-10-26 17:36:00[diff] [blame]73// A helper class to be used as the predicate with |EraseIf| to implement
74// in-place set intersection. Helps implement the algorithm of going through
75// each container an element at a time, erasing elements from the first
76// container if they aren't in the second container. Requires each container be
77// sorted. Note that the logic below appears inverted since it is returning
78// whether an element should be erased.
79template<classCollection>
80classIsNotIn{
81public:
82explicitIsNotIn(constCollection& collection)
Lei Zhang56887e22024-11-21 18:48:06[diff] [blame]83: it_(collection.begin()), end_(collection.end()){}
Kevin Bailey156ff6d2017-10-26 17:36:00[diff] [blame]84
85booloperator()(consttypenameCollection::value_type& x){
Lei Zhang56887e22024-11-21 18:48:06[diff] [blame]86while(it_!= end_&&*it_< x){
87++it_;
Kevin Bailey156ff6d2017-10-26 17:36:00[diff] [blame]88}
Lei Zhang56887e22024-11-21 18:48:06[diff] [blame]89if(it_== end_||*it_!= x){
90returntrue;
91}
92++it_;
93returnfalse;
Kevin Bailey156ff6d2017-10-26 17:36:00[diff] [blame]94}
95
96private:
Lei Zhang56887e22024-11-21 18:48:06[diff] [blame]97typenameCollection::const_iterator it_;
Kevin Bailey156ff6d2017-10-26 17:36:00[diff] [blame]98consttypenameCollection::const_iterator end_;
99};
100
kalman@chromium.org1dea7572012-12-05 21:40:27[diff] [blame]101}// namespace base
102
dilmah@chromium.org7286e3fc2011-07-19 22:13:24[diff] [blame]103#endif// BASE_STL_UTIL_H_
[8]ページ先頭
©2009-2025 Movatter.jp