📄 rope.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>rope<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>rope<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><tt>Rope</tt>s are a scalable string implementation: they are designedfor efficient operation that involve the string as a whole. Operationssuch as assignment, concatenation, and substring take time that isnearly independent of the length of the string. Unlike C strings,<tt>rope</tt>s are a reasonable representation for very long strings such asedit buffers or mail messages. <A href="#1">[1]</A><P>Though <tt>rope</tt>s can be treated as <A href="Container.html">Container</A>s of characters, and arealmost <A href="Sequence.html">Sequence</A>s, this is rarely the most efficient way toaccomplish a task. Replacing an individual character in a <tt>rope</tt> isslow: each character replacement essentially consists of two substringoperations followed by two concatenation operations. <tt>Rope</tt>sprimarily target a more functional programming style.<P>They differ from <tt><A href="Vector.html">vector</A><char></tt> or reference-counted stringimplementations in the following ways.<P>Advantages:<UL><LI>Much faster concatenation and substring operations involving longstrings. Inserting a character in the middle of a 10 megabyte ropeshould take on the order of 10s of microseconds, even if a copy of theoriginal is kept, <i>e.g.</i> as part of an edit history. In contrast,this would take on the order of a second for conventional "flat"string representation. The time required for concatenation can beviewed as constant for most applications. It is perfectly reasonableto use a <tt>rope</tt> as the representation of a file inside a text editor.<LI>Potentially much better space performance. Minor modifications of a<tt>rope</tt> can share memory with the original. <tt>Rope</tt>s are allocated in smallchunks, significantly reducing memory fragmentation problems introducedby large blocks.<LI>Assignment is simply a (possibly reference counted) pointerassignment. Unlike reference-counted copy-on-write implementations,this remains largely true even if one of the copies is subsequentlyslightly modified. It is very inexpensive to checkpoint old versionsof a string, <i>e.g.</i> in an edit history.<LI>It is possible to view a function producing characters as a <tt>rope</tt>. Thusa piece of a rope may be a 100MByte file, which is read only when that sectionof the string is examined. Concatenating a string to the end of such a filedoes not involve reading the file. (Currently the implementation of thisfacility is incomplete.)</UL>Disadvantages:<UL><LI>Single character replacements in a <tt>rope</tt> are expensive. A characterupdate requires time roughly logarithmic in the length of the string.It is implemented as two substring operations followed by twoconcatenations.<LI>A <tt>rope</tt> can be examined a character at a time through a<tt>const_iterator</tt> in amortized constant time, as for<tt><A href="Vector.html">vector</A><char></tt>. However this is slower than for<tt><A href="Vector.html">vector</A><char></tt> by a significant constant factor (roughly a factorof 5 or 10 if little processing is done on each character and thestring is long). Nonconst iterators involve additional checking, andare hence a bit slower still. (We expect that eventually some commonalgorithms will be specialized so that this cost is not encountered.Currently only output, conversion to a C string, and thesingle-character find member function are treated in this way.)<LI>Iterators are on the order of a dozen words in size. This means thatcopying them, though not tremendously expensive, is not a trivialoperation. Avoid postincrementing iterators; use preincrementwhenever possible. (The interface also provides primitives forindexing into a string using integer character positions. Passingpositions around is clearly much cheaper, but this makes the indexingoperation expensive, again roughly logarithmic in the length of therope.)</UL>Experience with previous implementations for other programminglanguages suggests that <tt>rope</tt>s are a good choice as the normal ordefault representation of strings in a program. It will occasionallybe necessary to use some type of character array, such as<tt><A href="Vector.html">vector</A><char></tt>, in places that are particularly sensitive to theperformance of traversals or in-place updates. But the use of <tt>rope</tt>sminimizes the number of cases in which program running times becomeintolerable due to unexpectedly long string inputs.<P>A <tt>rope</tt> is almost, but not quite, a <A href="Sequence.html">Sequence</A>. It supports randomaccess const_iterators. Forward or backward traversals take constanttime per operation. Nonconstant iterators are also provided.However, assignment through a nonconst iterator is an expensiveoperation (basically logarithmic time, but with a large constant). Itshould be avoided in frequently executed code.<P>In order to discourage accidental use of expensive operations,the <tt>begin</tt> and <tt>end</tt> member functions on ropes return <tt>const_iterator</tt>.If non-const iterators are desired, the member functions<tt>mutable_begin</tt> and <tt>mutable_end</tt> should be used.<P>Any modification of a <tt>rope</tt> invalidates const iterators referring tothe rope. Mutable iterators refer to the same position in the same<tt>rope</tt> after an update. (This may be surprising if the iterators refersto a position after an insertion point.) They remain valid unless theiterator refers to a position that is more than one past the end of theresulting <tt>rope</tt>. <h3>Definition</h3>Defined in the header <A href="rope">rope</A>, and in the backward-compatibilityheader <A href="rope.h">rope.h</A>. The <tt>rope</tt> class, and the <A href="rope">rope</A> header, are SGIextensions; they are not part of the C++ standard.<h3>Example</h3><pre>crope r(1000000, 'x'); // crope is rope<char>. wrope is rope<wchar_t> // Builds a rope containing a million 'x's. // Takes much less than a MB, since the // different pieces are shared.crope r2 = r + "abc" + r; // concatenation; takes on the order of 100s // of machine instructions; fastcrope r3 = r2.substr(1000000, 3); // yields "abc"; fast.crope r4 = r2.substr(1000000, 1000000); // also fast.reverse(r2.mutable_begin(), r2.mutable_end()); // correct, but slow; may take a // minute or more.</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>rope</tt>'s value type: usually <tt>char</tt> or <tt>wchar_t</tt>. <A href="#2">[2]</A></TD><TD VAlign=top> </TD></TR><TR><TD VAlign=top><tt>Alloc</tt></TD><TD VAlign=top>The <tt>rope</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="RandomAccessContainer.html">Random Access Container</A>. Almost, but not quite, a model of<A href="FrontInsertionSequence.html">Front Insertion Sequence</A> and <A href="BackInsertionSequence.html">Back Insertion Sequence</A>.<h3>Type requirements</h3>None, except for those imposed by the requirements of <A href="RandomAccessContainer.html">Random Access Container</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 <tt>rope</tt>'s value type <tt>T</tt>, usually <tt>char</tt> or <tt>wchar_t</tt>.</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>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>reference</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Reference to a <tt>rope</tt> element. <A href="#3">[3]</A></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>. <A href="#3">[3]</A></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>. <A href="#3">[3]</A></TD></TR><TR><TD VAlign=top><tt>const_pointer</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Const pointer to <tt>T</tt>. <A href="#3">[3]</A></TD></TR><TR><TD VAlign=top><tt>const_reverse_iterator</tt></TD><TD VAlign=top> <A href="ReversibleContainer.html">Reversible Container</A></TD><TD VAlign=top>Const iterator used to iterate backwards through a <tt>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>reverse_iterator</tt></TD><TD VAlign=top> <A href="ReversibleContainer.html">Reversible Container</A></TD><TD VAlign=top>Mutable iterator used to iterate backwards through a <tt>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>iterator</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Mutable <A href="RandomAccessIterator.html">random access iterator</A> used to iterate through a <tt>rope</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 <A href="RandomAccessIterator.html">random access iterator</A> used to iterate through a <tt>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>rope(const charT* s)</tt></TD><TD VAlign=top><tt>rope</tt>.</TD><TD VAlign=top>Constructs a <tt>rope</tt> from a C string.</TD></TR><TR><TD VAlign=top><tt>rope(const charT* s, size_t n)</tt></TD><TD VAlign=top><tt>rope</tt>.</TD><TD VAlign=top>Constructs a <tt>rope</tt> from a (not necessarily null-terminated) array of <tt>charT</tt>.</TD></TR><TR><TD VAlign=top><tt>rope(const const_iterator& f, const const_iterator& l)</tt></TD><TD VAlign=top> <A href="Sequence.html">Sequence</A></TD><TD VAlign=top>Creates a <tt>rope</tt> with a copy of a range.</TD></TR><TR><TD VAlign=top><tt>rope(const iterator& f, const iterator& l)</tt></TD><TD VAlign=top> <A href="Sequence.html">Sequence</A></TD><TD VAlign=top>Creates a <tt>rope</tt> with a copy of a range.</TD></TR><TR><TD VAlign=top><tt>rope(const charT* f, const charT* l)</tt></TD><TD VAlign=top> <A href="Sequence.html">Sequence</A></TD><TD VAlign=top>Creates a <tt>rope</tt> with a copy of a range.</TD></TR><TR><TD VAlign=top><tt>rope(charT c)</tt></TD><TD VAlign=top><tt>rope</tt>.</TD><TD VAlign=top>Single-character constructor.</TD></TR><TR><TD VAlign=top><tt>rope()</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Default constructor.</TD></TR><TR><TD VAlign=top><tt>rope(<A href="char_producer.html">char_producer</A><charT>*, size_t, bool)</tt></TD><TD VAlign=top><tt>rope</tt></TD><TD VAlign=top>See below.</TD></TR><TR><TD VAlign=top><tt>rope(const rope& x)</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>The copy constructor.</TD></TR><TR><TD VAlign=top><tt>~rope()</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>The destructor.</TD></TR><TR><TD VAlign=top><tt>rope& operator=(const rope&x)</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>The assignment operator.</TD></TR><TR><TD VAlign=top><tt>void swap(rope& x)</tt></TD><TD VAlign=top> <A href="Container.html">Container</A></TD><TD VAlign=top>Swaps the contents of two <tt>rope</tt>s.</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>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>size_type length() const</tt></TD><TD VAlign=top><tt>rope</tt></TD><TD VAlign=top>Same as <tt>size</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>Size of longest <tt>rope</tt> guaranteed to be representable.</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>Equivalent to <tt>size() == 0</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 an <tt>const_iterator</tt> pointing to the beginning of the <tt>rope</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 an <tt>const_iterator</tt> pointing to the end of the <tt>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>iterator mutable_begin()</tt></TD><TD VAlign=top><tt>rope</tt></TD><TD VAlign=top>Returns an <tt>iterator</tt> pointing to the beginning of the <tt>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>iterator mutable_end()</tt></TD><TD VAlign=top><tt>rope</tt></TD><TD VAlign=top>Returns an <tt>iterator</tt> pointing to the end of the <tt>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>const_reverse_iterator rbegin() const</tt></TD><TD VAlign=top> <A href="ReversibleContainer.html">Reversible Container</A></TD><TD VAlign=top>Returns a <tt>const_reverse_iterator</tt> pointing to the beginning of the reversed <tt>rope</tt></TD></TR><TR><TD VAlign=top><tt>const_reverse_iterator rend() const</tt></TD><TD VAlign=top> <A href="ReversibleContainer.html">Reversible Container</A></TD><TD VAlign=top>Returns a <tt>const_reverse_iterator</tt> pointing to the end of the reversed <tt>rope</tt></TD></TR><TR><TD VAlign=top><tt>iterator mutable_rbegin()</tt></TD><TD VAlign=top><tt>rope</tt></TD><TD VAlign=top>Returns a <tt>reverse_iterator</tt> pointing to the beginning of the reversed <tt>rope</tt>.</TD></TR><TR><TD VAlign=top><tt>iterator mutable_rend()</tt>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -