📄 slist.html
字号:
<HTML><!-- -- Copyright (c) 1996-1999 -- Silicon Graphics Computer Systems, Inc. -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Silicon Graphics makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- -- Copyright (c) 1994 -- Hewlett-Packard Company -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Hewlett-Packard Company makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- --><Head><Title>slist<T, Alloc></Title><!-- Generated by htmldoc --></HEAD><BODY TEXT="#000000" LINK="#006600" ALINK="#003300" VLINK="#7C7F87" BGCOLOR="#FFFFFF"><A HREF="/"><IMG SRC="/images/common/sgilogo_small.gif" ALT="SGI Logo" WIDTH="80" HEIGHT="72" BORDER="0"></A><P><!--end header--><BR Clear><H1>slist<T, Alloc></H1><Table CellPadding=0 CellSpacing=0 width=100%><TR><TD Align=left><Img src = "containers.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD><TD Align=right><Img src = "type.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD></TR><TR><TD Align=left VAlign=top><b>Category</b>: containers</TD><TD Align=right VAlign=top><b>Component type</b>: type</TD></TR></Table><h3>Description</h3>An <tt>slist</tt> is a singly linked list: a list where each element islinked to the next element, but not to the previous element. <A href="#1">[1]</A> That is,it is a <A href="Sequence.html">Sequence</A> that supports forward but not backward traversal,and (amortized) constant time insertion and removal of elements.<tt>Slist</tt>s, like <tt><A href="List.html">list</A></tt>s, have the important property that insertionand splicing do not invalidate iterators to list elements, and thateven removal invalidates only the iterators that point to the elementsthat are removed. The ordering of iterators may be changed (that is,<tt>slist<T>::iterator</tt> might have a different predecessor or successorafter a list operation than it did before), but the iteratorsthemselves will not be invalidated or made to point to differentelements unless that invalidation or mutation is explicit. <A href="#2">[2]</A><P>The main difference between <tt>slist</tt> and <tt><A href="List.html">list</A></tt> is that <tt><A href="List.html">list</A></tt>'siterators are <A href="BidirectionalIterator.html">bidirectional iterators</A>, while <tt>slist</tt>'s iteratorsare <A href="ForwardIterator.html">forward iterators</A>. This means that <tt>slist</tt> is less versatilethan <tt><A href="List.html">list</A></tt>; frequently, however, <A href="BidirectionalIterator.html">bidirectional iterators</A>are unnecessary. You should usually use <tt>slist</tt> unless you actuallyneed the extra functionality of <tt><A href="List.html">list</A></tt>, because singly linkedlists are smaller and faster than double linked lists.<P><b>Important performance note</b>: like every other <A href="Sequence.html">Sequence</A>, <tt>slist</tt>defines the member functions <tt>insert</tt> and <tt>erase</tt>. Using these memberfunctions carelessly, however, can result in disastrously slowprograms. The problem is that <tt>insert</tt>'s first argument is aniterator <tt>pos</tt>, and that it inserts the new element(s) <i>before</i><tt>pos</tt>. This means that <tt>insert</tt> must find the iterator justbefore <tt>pos</tt>; this is a constant-time operation for <tt><A href="List.html">list</A></tt>, since <tt><A href="List.html">list</A></tt> has bidirectional iterators, but for <tt>slist</tt>it must find that iterator by traversing the list from the beginningup to <tt>pos</tt>. In other words: <tt>insert</tt> and <tt>erase</tt> are slow operationsanywhere but near the beginning of the <tt>slist</tt>.<P><tt>Slist</tt> provides the member functions <tt>insert_after</tt> and<tt>erase_after</tt>, which are constant time operations: you should alwaysuse <tt>insert_after</tt> and <tt>erase_after</tt> whenever possible. If you findthat <tt>insert_after</tt> and <tt>erase_after</tt> aren't adequate for your needs,and that you often need to use <tt>insert</tt> and <tt>erase</tt> in the middle ofthe list, then you should probably use <tt><A href="List.html">list</A></tt> instead of <tt>slist</tt>.<h3>Definition</h3>Defined in the header <A href="slist">slist</A>, and in the backward-compatibilityheader <A href="slist.h">slist.h</A>. The <tt>slist</tt> class, and the <A href="slist">slist</A> header, are an SGI extension;they are not part of the C++ standard.<h3>Example</h3><pre>int main() { slist<int> L; L.push_front(0); L.push_front(1); L.insert_after(L.begin(), 2); <A href="copy.html">copy</A>(L.begin(), L.end(), // The output is 1 2 0 <A href="ostream_iterator.html">ostream_iterator</A><int>(cout, " ")); cout << endl; slist<int>::iterator back = L.previous(L.end()); back = L.insert_after(back, 3); back = L.insert_after(back, 4); back = L.insert_after(back, 5); <A href="copy.html">copy</A>(L.begin(), L.end(), // The output is 1 2 0 3 4 5 <A href="ostream_iterator.html">ostream_iterator</A><int>(cout, " ")); cout << endl;}</pre><h3>Template parameters</h3><Table border><TR><TH>Parameter</TH><TH>Description</TH><TH>Default</TH></TR><TR><TD VAlign=top><tt>T</tt></TD><TD VAlign=top>The <tt>slist</tt>'s value type: the type of object that is stored in the list.</TD><TD VAlign=top> </TD></TR><TR><TD VAlign=top><tt>Alloc</tt></TD><TD VAlign=top>The <tt>slist</tt>'s allocator, used for all internal memory management.</TD><TD VAlign=top><tt><A href="Allocators.html">alloc</A></tt></TD></tr></table><h3>Model of</h3><A href="FrontInsertionSequence.html">Front Insertion Sequence</A><h3>Type requirements</h3>None, except for those imposed by the requirements of <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>.<h3>Public base classes</h3>None.<h3>Members</h3><Table border><TR><TH>Member</TH><TH>Where defined</TH><TH>Description</TH></TR><TR><TD VAlign=top><tt>value_type</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>The type of object, <tt>T</tt>, stored in the <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>pointer</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Pointer to <tt>T</tt>.</TD></TR><TR><TD VAlign=top><tt>reference</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Reference to <tt>T</tt></TD></TR><TR><TD VAlign=top><tt>const_reference</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Const reference to <tt>T</tt></TD></TR><TR><TD VAlign=top><tt>size_type</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>An unsigned integral type.</TD></TR><TR><TD VAlign=top><tt>difference_type</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>A signed integral type.</TD></TR><TR><TD VAlign=top><tt>iterator</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Iterator used to iterate through an <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>const_iterator</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Const iterator used to iterate through an <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>iterator begin()</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Returns an <tt>iterator</tt> pointing to the beginning of the <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>iterator end()</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Returns an <tt>iterator</tt> pointing to the end of the <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>const_iterator begin() const</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Returns a <tt>const_iterator</tt> pointing to the beginning of the <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>const_iterator end() const</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Returns a <tt>const_iterator</tt> pointing to the end of the <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>size_type size() const</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Returns the size of the <tt>slist</tt>. Note: you should not assume that this function is constant time. It is permitted to be <i>O(N</i>), where <i>N</i> is the number of elements in the <tt>slist</tt>. If you wish to test whether an <tt>slist</tt> is empty, you should write <tt>L.empty()</tt> rather than <tt>L.size() == 0</tt>.</TD></TR><TR><TD VAlign=top><tt>size_type max_size() const</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Returns the largest possible size of the <tt>slist</tt>.</TD></TR><TR><TD VAlign=top><tt>bool empty() const</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top><tt>true</tt> if the <tt>slist</tt>'s size is <tt>0</tt>.</TD></TR><TR><TD VAlign=top><tt>slist()</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Creates an empty slist.</TD></TR><TR><TD VAlign=top><tt>slist(size_type n)</tt></TD><TD VAlign=top> <A href="Sequence.html">Sequence</A></TD><TD VAlign=top>Creates an <tt>slist</tt> with <tt>n</tt> elements, each of which is a copy of <tt>T()</tt>.</TD></TR><TR><TD VAlign=top><tt>slist(size_type n, const T& t)</tt></TD><TD VAlign=top> <A href="Sequence.html">Sequence</A></TD><TD VAlign=top>Creates an slist with <tt>n</tt> copies of <tt>t</tt>.</TD></TR><TR><TD VAlign=top><tt>slist(const slist&)</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>The copy constructor.</TD></TR><TR><TD VAlign=top><pre>template <class InputIterator>slist(InputIterator f, InputIterator l) <A href="#3">[3]</A></pre></TD><TD VAlign=top> <A href="Sequence.html">Sequence</A></TD><TD VAlign=top>Creates an <tt>slist</tt> with a copy of a range.</TD></TR><TR><TD VAlign=top><tt>~slist()</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>The destructor.</TD></TR><TR>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -