]>
git.ipfire.org Git - thirdparty/gcc.git/blob - libstdc++-v3/testsuite/ext/pb_ds/example/basic_multiset.cc
3 // Copyright (C) 2005-2023 Free Software Foundation, Inc.
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 terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
23 // Permission to use, copy, modify, sell, and distribute this software
24 // is hereby granted without fee, provided that the above copyright
25 // notice appears in all copies, and that both that copyright notice
26 // and this permission notice appear in supporting documentation. None
27 // of the above authors, nor IBM Haifa Research Laboratories, make any
28 // representation about the suitability of this software for any
29 // purpose. It is provided "as is" without express or implied
33 * @file basic_multiset_example.cpp
34 * A basic example showing how to use multisets.
38 // This example shows how to use "multisets".
40 // In this example we build a very simple priority queue that also can
41 // be queried if an entry contains (i.e., it is slightly similar to an
42 // associative container as well as a priority queue). The priority
43 // queue adapts a "multiset".
45 // (Note that there are more efficient ways for implementing this than
46 // by adapting an associative container. This is just an example for
51 #include <ext/pb_ds/assoc_container.hpp>
54 using namespace __gnu_pbds
;
56 // A simple priority queue that also supports an "contains" query.
64 // Pops the largest integer and returns it.
68 // Returns true iff i is contained in the container.
71 { return m_tree
.find(i
) != m_tree
.end(); }
73 // Returns true iff empty.
76 { return m_tree
.empty(); }
79 // This is the container type we adapt - a "multiset".
80 // It maps each integer to the number of times it logically appears.
97 // To push i, we insert to the "multiset" that i appears 0 times
98 // (which is a no-op if i already is contained), then increment the
99 // number of times i is contained by 1.
100 ++m_tree
.insert(make_pair(i
, 0)).first
->second
;
109 // The element we need to pop must be the first one, since tree_t is
110 // an ordered container.
111 tree_t::iterator it
= m_tree
.begin();
113 const int i
= it
->first
;
115 // Decrease the number of times the popped element appears in the
116 // container object. If it is 0 - we erase it.
117 if (--it
->second
== 0)
127 // First we push some elements.
134 // Note that logically, 4 appears 2 times, and each of 1, 2, and 3
136 assert(cpq
.contains(4));
137 assert(cpq
.contains(3));
138 assert(cpq
.contains(2));
139 assert(cpq
.contains(1));
141 // Now pop the topmost element - it should be 4.
142 assert(cpq
.pop() == 4);
144 // Now logically, each of 1, 2, 3, and 4 appear once.
145 assert(cpq
.contains(4));
147 // We pop the topmost element - it should be 4.
148 assert(cpq
.pop() == 4);
150 // 4 should not be contained any more.
151 assert(!cpq
.contains(4));
153 assert(cpq
.contains(3));
154 assert(cpq
.contains(2));
155 assert(cpq
.contains(1));
157 assert(cpq
.pop() == 3);
158 assert(cpq
.pop() == 2);
159 assert(cpq
.pop() == 1);