]>
Commit | Line | Data |
---|---|---|
36fed23c | 1 | // -*- C++ -*- |
2 | ||
f1717362 | 3 | // Copyright (C) 2005-2016 Free Software Foundation, Inc. |
36fed23c | 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 terms | |
7 | // of the GNU General Public License as published by the Free Software | |
6bc9506f | 8 | // Foundation; either version 3, or (at your option) any later |
36fed23c | 9 | // version. |
10 | ||
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. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License | |
6bc9506f | 17 | // along with this library; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. | |
36fed23c | 19 | |
36fed23c | 20 | |
21 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
22 | ||
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 | |
30 | // warranty. | |
31 | ||
32 | /** | |
33 | * @file basic_multiset_example.cpp | |
34 | * A basic example showing how to use multisets. | |
35 | */ | |
36 | ||
37 | ||
38 | // This example shows how to use "multisets". | |
39 | ||
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". | |
44 | ||
45 | // (Note that there are more efficient ways for implementing this than | |
46 | // by adapting an associative container. This is just an example for | |
47 | // "multisets".) | |
48 | ||
49 | #include <iostream> | |
50 | #include <cassert> | |
51 | #include <ext/pb_ds/assoc_container.hpp> | |
52 | ||
53 | using namespace std; | |
b34535d7 | 54 | using namespace __gnu_pbds; |
36fed23c | 55 | |
56 | // A simple priority queue that also supports an "contains" query. | |
57 | class contains_pq | |
58 | { | |
59 | public: | |
60 | // Pushes an integer. | |
61 | void | |
62 | push(int i); | |
63 | ||
64 | // Pops the largest integer and returns it. | |
65 | int | |
66 | pop(); | |
67 | ||
68 | // Returns true iff i is contained in the container. | |
69 | bool | |
70 | contains(int i) const | |
71 | { return m_tree.find(i) != m_tree.end(); } | |
72 | ||
73 | // Returns true iff empty. | |
74 | bool | |
75 | empty() const | |
76 | { return m_tree.empty(); } | |
77 | ||
78 | private: | |
79 | // This is the container type we adapt - a "multiset". | |
80 | // It maps each integer to the number of times it logically appears. | |
81 | typedef | |
82 | tree< | |
83 | int, | |
84 | size_t, | |
85 | greater< | |
86 | int> > | |
87 | tree_t; | |
88 | ||
89 | private: | |
90 | tree_t m_tree; | |
91 | }; | |
92 | ||
93 | void | |
94 | contains_pq:: | |
95 | push(int i) | |
96 | { | |
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; | |
101 | } | |
102 | ||
103 | int | |
104 | contains_pq:: | |
105 | pop() | |
106 | { | |
107 | assert(!empty()); | |
108 | ||
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(); | |
112 | ||
113 | const int i = it->first; | |
114 | ||
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) | |
118 | m_tree.erase(it); | |
119 | ||
120 | return i; | |
121 | } | |
122 | ||
123 | int main() | |
124 | { | |
125 | contains_pq cpq; | |
126 | ||
127 | // First we push some elements. | |
128 | cpq.push(4); | |
129 | cpq.push(3); | |
130 | cpq.push(2); | |
131 | cpq.push(1); | |
132 | cpq.push(4); | |
133 | ||
134 | // Note that logically, 4 appears 2 times, and each of 1, 2, and 3 | |
135 | // appear once. | |
136 | assert(cpq.contains(4)); | |
137 | assert(cpq.contains(3)); | |
138 | assert(cpq.contains(2)); | |
139 | assert(cpq.contains(1)); | |
140 | ||
141 | // Now pop the topmost element - it should be 4. | |
142 | assert(cpq.pop() == 4); | |
143 | ||
144 | // Now logically, each of 1, 2, 3, and 4 appear once. | |
145 | assert(cpq.contains(4)); | |
146 | ||
147 | // We pop the topmost element - it should be 4. | |
148 | assert(cpq.pop() == 4); | |
149 | ||
150 | // 4 should not be contained any more. | |
151 | assert(!cpq.contains(4)); | |
152 | ||
153 | assert(cpq.contains(3)); | |
154 | assert(cpq.contains(2)); | |
155 | assert(cpq.contains(1)); | |
156 | ||
157 | assert(cpq.pop() == 3); | |
158 | assert(cpq.pop() == 2); | |
159 | assert(cpq.pop() == 1); | |
160 | ||
161 | assert(cpq.empty()); | |
162 | ||
163 | return 0; | |
164 | } | |
165 |