| 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> |