Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> |
2 | <html> | |
3 | <head> | |
4 | <link rel="STYLESHEET" href="lib.css" type='text/css' /> | |
5 | <link rel="SHORTCUT ICON" href="../icons/pyfav.png" type="image/png" /> | |
6 | <link rel='start' href='../index.html' title='Python Documentation Index' /> | |
7 | <link rel="first" href="lib.html" title='Python Library Reference' /> | |
8 | <link rel='contents' href='contents.html' title="Contents" /> | |
9 | <link rel='index' href='genindex.html' title='Index' /> | |
10 | <link rel='last' href='about.html' title='About this document...' /> | |
11 | <link rel='help' href='about.html' title='About this document...' /> | |
12 | <link rel="next" href="module-heapq.html" /> | |
13 | <link rel="prev" href="module-bisect.html" /> | |
14 | <link rel="parent" href="misc.html" /> | |
15 | <link rel="next" href="deque-recipes.html" /> | |
16 | <meta name='aesop' content='information' /> | |
17 | <title>5.12 collections -- High-performance container datatypes</title> | |
18 | </head> | |
19 | <body> | |
20 | <DIV CLASS="navigation"> | |
21 | <div id='top-navigation-panel' xml:id='top-navigation-panel'> | |
22 | <table align="center" width="100%" cellpadding="0" cellspacing="2"> | |
23 | <tr> | |
24 | <td class='online-navigation'><a rel="prev" title="5.11.1 Examples" | |
25 | href="bisect-example.html"><img src='../icons/previous.png' | |
26 | border='0' height='32' alt='Previous Page' width='32' /></A></td> | |
27 | <td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services" | |
28 | href="misc.html"><img src='../icons/up.png' | |
29 | border='0' height='32' alt='Up One Level' width='32' /></A></td> | |
30 | <td class='online-navigation'><a rel="next" title="5.12.1 Recipes" | |
31 | href="deque-recipes.html"><img src='../icons/next.png' | |
32 | border='0' height='32' alt='Next Page' width='32' /></A></td> | |
33 | <td align="center" width="100%">Python Library Reference</td> | |
34 | <td class='online-navigation'><a rel="contents" title="Table of Contents" | |
35 | href="contents.html"><img src='../icons/contents.png' | |
36 | border='0' height='32' alt='Contents' width='32' /></A></td> | |
37 | <td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png' | |
38 | border='0' height='32' alt='Module Index' width='32' /></a></td> | |
39 | <td class='online-navigation'><a rel="index" title="Index" | |
40 | href="genindex.html"><img src='../icons/index.png' | |
41 | border='0' height='32' alt='Index' width='32' /></A></td> | |
42 | </tr></table> | |
43 | <div class='online-navigation'> | |
44 | <b class="navlabel">Previous:</b> | |
45 | <a class="sectref" rel="prev" href="bisect-example.html">5.11.1 Examples</A> | |
46 | <b class="navlabel">Up:</b> | |
47 | <a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A> | |
48 | <b class="navlabel">Next:</b> | |
49 | <a class="sectref" rel="next" href="deque-recipes.html">5.12.1 Recipes</A> | |
50 | </div> | |
51 | <hr /></div> | |
52 | </DIV> | |
53 | <!--End of Navigation Panel--> | |
54 | ||
55 | <H1><A NAME="SECTION0071200000000000000000"> | |
56 | 5.12 <tt class="module">collections</tt> -- | |
57 | High-performance container datatypes</A> | |
58 | </H1> | |
59 | ||
60 | <P> | |
61 | <A NAME="module-collections"></A> | |
62 | ||
63 | <span class="versionnote">New in version 2.4.</span> | |
64 | ||
65 | <P> | |
66 | This module implements high-performance container datatypes. Currently, the | |
67 | only datatype is a deque. Future additions may include B-trees | |
68 | and Fibonacci heaps. | |
69 | ||
70 | <P> | |
71 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
72 | <td><nobr><b><tt id='l2h-1337' xml:id='l2h-1337' class="function">deque</tt></b>(</nobr></td> | |
73 | <td><var></var><big>[</big><var>iterable</var><big>]</big><var></var>)</td></tr></table></dt> | |
74 | <dd> | |
75 | Returns a new deque objected initialized left-to-right (using | |
76 | <tt class="method">append()</tt>) with data from <var>iterable</var>. If <var>iterable</var> | |
77 | is not specified, the new deque is empty. | |
78 | ||
79 | <P> | |
80 | Deques are a generalization of stacks and queues (the name is pronounced | |
81 | ``deck'' and is short for ``double-ended queue''). Deques support | |
82 | thread-safe, memory efficient appends and pops from either side of the deque | |
83 | with approximately the same <code>O(1)</code> performance in either direction. | |
84 | ||
85 | <P> | |
86 | Though <tt class="class">list</tt> objects support similar operations, they are optimized | |
87 | for fast fixed-length operations and incur <code>O(n)</code> memory movement costs | |
88 | for "<tt class="samp">pop(0)</tt>" and "<tt class="samp">insert(0, v)</tt>" operations which change both the | |
89 | size and position of the underlying data representation. | |
90 | ||
91 | <span class="versionnote">New in version 2.4.</span> | |
92 | ||
93 | </dl> | |
94 | ||
95 | <P> | |
96 | Deque objects support the following methods: | |
97 | ||
98 | <P> | |
99 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
100 | <td><nobr><b><tt id='l2h-1338' xml:id='l2h-1338' class="method">append</tt></b>(</nobr></td> | |
101 | <td><var>x</var>)</td></tr></table></dt> | |
102 | <dd> | |
103 | Add <var>x</var> to the right side of the deque. | |
104 | </dl> | |
105 | ||
106 | <P> | |
107 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
108 | <td><nobr><b><tt id='l2h-1339' xml:id='l2h-1339' class="method">appendleft</tt></b>(</nobr></td> | |
109 | <td><var>x</var>)</td></tr></table></dt> | |
110 | <dd> | |
111 | Add <var>x</var> to the left side of the deque. | |
112 | </dl> | |
113 | ||
114 | <P> | |
115 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
116 | <td><nobr><b><tt id='l2h-1340' xml:id='l2h-1340' class="method">clear</tt></b>(</nobr></td> | |
117 | <td><var></var>)</td></tr></table></dt> | |
118 | <dd> | |
119 | Remove all elements from the deque leaving it with length 0. | |
120 | </dl> | |
121 | ||
122 | <P> | |
123 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
124 | <td><nobr><b><tt id='l2h-1341' xml:id='l2h-1341' class="method">extend</tt></b>(</nobr></td> | |
125 | <td><var>iterable</var>)</td></tr></table></dt> | |
126 | <dd> | |
127 | Extend the right side of the deque by appending elements from | |
128 | the iterable argument. | |
129 | </dl> | |
130 | ||
131 | <P> | |
132 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
133 | <td><nobr><b><tt id='l2h-1342' xml:id='l2h-1342' class="method">extendleft</tt></b>(</nobr></td> | |
134 | <td><var>iterable</var>)</td></tr></table></dt> | |
135 | <dd> | |
136 | Extend the left side of the deque by appending elements from | |
137 | <var>iterable</var>. Note, the series of left appends results in | |
138 | reversing the order of elements in the iterable argument. | |
139 | </dl> | |
140 | ||
141 | <P> | |
142 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
143 | <td><nobr><b><tt id='l2h-1343' xml:id='l2h-1343' class="method">pop</tt></b>(</nobr></td> | |
144 | <td><var></var>)</td></tr></table></dt> | |
145 | <dd> | |
146 | Remove and return an element from the right side of the deque. | |
147 | If no elements are present, raises a <tt class="exception">IndexError</tt>. | |
148 | </dl> | |
149 | ||
150 | <P> | |
151 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
152 | <td><nobr><b><tt id='l2h-1344' xml:id='l2h-1344' class="method">popleft</tt></b>(</nobr></td> | |
153 | <td><var></var>)</td></tr></table></dt> | |
154 | <dd> | |
155 | Remove and return an element from the left side of the deque. | |
156 | If no elements are present, raises a <tt class="exception">IndexError</tt>. | |
157 | </dl> | |
158 | ||
159 | <P> | |
160 | <dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline"> | |
161 | <td><nobr><b><tt id='l2h-1345' xml:id='l2h-1345' class="method">rotate</tt></b>(</nobr></td> | |
162 | <td><var>n</var>)</td></tr></table></dt> | |
163 | <dd> | |
164 | Rotate the deque <var>n</var> steps to the right. If <var>n</var> is | |
165 | negative, rotate to the left. Rotating one step to the right | |
166 | is equivalent to: "<tt class="samp">d.appendleft(d.pop())</tt>". | |
167 | </dl> | |
168 | ||
169 | <P> | |
170 | In addition to the above, deques support iteration, pickling, "<tt class="samp">len(d)</tt>", | |
171 | "<tt class="samp">reversed(d)</tt>", "<tt class="samp">copy.copy(d)</tt>", "<tt class="samp">copy.deepcopy(d)</tt>", | |
172 | membership testing with the <tt class="keyword">in</tt> operator, and subscript references | |
173 | such as "<tt class="samp">d[-1]</tt>". | |
174 | ||
175 | <P> | |
176 | Example: | |
177 | ||
178 | <P> | |
179 | <div class="verbatim"><pre> | |
180 | >>> from collections import deque | |
181 | >>> d = deque('ghi') # make a new deque with three items | |
182 | >>> for elem in d: # iterate over the deque's elements | |
183 | ... print elem.upper() | |
184 | G | |
185 | H | |
186 | I | |
187 | ||
188 | >>> d.append('j') # add a new entry to the right side | |
189 | >>> d.appendleft('f') # add a new entry to the left side | |
190 | >>> d # show the representation of the deque | |
191 | deque(['f', 'g', 'h', 'i', 'j']) | |
192 | ||
193 | >>> d.pop() # return and remove the rightmost item | |
194 | 'j' | |
195 | >>> d.popleft() # return and remove the leftmost item | |
196 | 'f' | |
197 | >>> list(d) # list the contents of the deque | |
198 | ['g', 'h', 'i'] | |
199 | >>> d[0] # peek at leftmost item | |
200 | 'g' | |
201 | >>> d[-1] # peek at rightmost item | |
202 | 'i' | |
203 | ||
204 | >>> list(reversed(d)) # list the contents of a deque in reverse | |
205 | ['i', 'h', 'g'] | |
206 | >>> 'h' in d # search the deque | |
207 | True | |
208 | >>> d.extend('jkl') # add multiple elements at once | |
209 | >>> d | |
210 | deque(['g', 'h', 'i', 'j', 'k', 'l']) | |
211 | >>> d.rotate(1) # right rotation | |
212 | >>> d | |
213 | deque(['l', 'g', 'h', 'i', 'j', 'k']) | |
214 | >>> d.rotate(-1) # left rotation | |
215 | >>> d | |
216 | deque(['g', 'h', 'i', 'j', 'k', 'l']) | |
217 | ||
218 | >>> deque(reversed(d)) # make a new deque in reverse order | |
219 | deque(['l', 'k', 'j', 'i', 'h', 'g']) | |
220 | >>> d.clear() # empty the deque | |
221 | >>> d.pop() # cannot pop from an empty deque | |
222 | Traceback (most recent call last): | |
223 | File "<pyshell#6>", line 1, in -toplevel- | |
224 | d.pop() | |
225 | IndexError: pop from an empty deque | |
226 | ||
227 | >>> d.extendleft('abc') # extendleft() reverses the input order | |
228 | >>> d | |
229 | deque(['c', 'b', 'a']) | |
230 | </pre></div> | |
231 | ||
232 | <P> | |
233 | ||
234 | <p><br /></p><hr class='online-navigation' /> | |
235 | <div class='online-navigation'> | |
236 | <!--Table of Child-Links--> | |
237 | <A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a> | |
238 | ||
239 | <UL CLASS="ChildLinks"> | |
240 | <LI><A href="deque-recipes.html">5.12.1 Recipes</a> | |
241 | </ul> | |
242 | <!--End of Table of Child-Links--> | |
243 | </div> | |
244 | ||
245 | <DIV CLASS="navigation"> | |
246 | <div class='online-navigation'> | |
247 | <p></p><hr /> | |
248 | <table align="center" width="100%" cellpadding="0" cellspacing="2"> | |
249 | <tr> | |
250 | <td class='online-navigation'><a rel="prev" title="5.11.1 Examples" | |
251 | href="bisect-example.html"><img src='../icons/previous.png' | |
252 | border='0' height='32' alt='Previous Page' width='32' /></A></td> | |
253 | <td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services" | |
254 | href="misc.html"><img src='../icons/up.png' | |
255 | border='0' height='32' alt='Up One Level' width='32' /></A></td> | |
256 | <td class='online-navigation'><a rel="next" title="5.12.1 Recipes" | |
257 | href="deque-recipes.html"><img src='../icons/next.png' | |
258 | border='0' height='32' alt='Next Page' width='32' /></A></td> | |
259 | <td align="center" width="100%">Python Library Reference</td> | |
260 | <td class='online-navigation'><a rel="contents" title="Table of Contents" | |
261 | href="contents.html"><img src='../icons/contents.png' | |
262 | border='0' height='32' alt='Contents' width='32' /></A></td> | |
263 | <td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png' | |
264 | border='0' height='32' alt='Module Index' width='32' /></a></td> | |
265 | <td class='online-navigation'><a rel="index" title="Index" | |
266 | href="genindex.html"><img src='../icons/index.png' | |
267 | border='0' height='32' alt='Index' width='32' /></A></td> | |
268 | </tr></table> | |
269 | <div class='online-navigation'> | |
270 | <b class="navlabel">Previous:</b> | |
271 | <a class="sectref" rel="prev" href="bisect-example.html">5.11.1 Examples</A> | |
272 | <b class="navlabel">Up:</b> | |
273 | <a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A> | |
274 | <b class="navlabel">Next:</b> | |
275 | <a class="sectref" rel="next" href="deque-recipes.html">5.12.1 Recipes</A> | |
276 | </div> | |
277 | </div> | |
278 | <hr /> | |
279 | <span class="release-info">Release 2.4.2, documentation updated on 28 September 2005.</span> | |
280 | </DIV> | |
281 | <!--End of Navigation Panel--> | |
282 | <ADDRESS> | |
283 | See <i><a href="about.html">About this document...</a></i> for information on suggesting changes. | |
284 | </ADDRESS> | |
285 | </BODY> | |
286 | </HTML> |