⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 rope.html

📁 指导程序员合理、高效的进行标准模板库编程。
💻 HTML
📖 第 1 页 / 共 4 页
字号:
🔍
1234 
<HTML>
<HEAD>
   <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
   <META NAME="Author" CONTENT="Zafir Anjum">
   <TITLE>MFC Programmer's SourceBook : STL Programmer's Guide</TITLE>
    <META name="description" 
     content="A freely available implementation 
     of the C++ Standard Template Library, including 
     hypertext documentation.">
	<META name="keywords" 
	content="generic programming, STL, standard template library">
</HEAD>

<SCRIPT LANGUAGE="JavaScript"><!--
var adcategory = "cpp";
// -->
</SCRIPT>
<body background="../../fancyhome/back.gif" bgcolor="#FFFFFF" >
<SCRIPT LANGUAGE="JavaScript"><!--
var nfrm = location.href.indexOf("_nfrm_");
var validframes = (top.frames.length > 0 && top.frames['ad'] && top.frames['logo'] );
var random = Math.random();

if( !validframes && nfrm == -1 )
{
	var dclkPage = "www.codeguru.com/";
	if( self.adcategory )
		dclkPage += adcategory;
	else
		dclkPage += "mfc";
	document.write('<nolayer><center>');
	document.write('<iframe src="http://ad.doubleclick.net/adi/' + dclkPage + ';ord='
	 + random + '" width=470 height=62 marginwidth=0 marginheight=0 hspace=0 vspace=0 '
	 + 'frameborder=0 scrolling=no bordercolor="#000000">');
	document.write('<a href="http://ad.doubleclick.net/jump/' + dclkPage + ';ord='
	 + random + '">');
	document.write('<img src="http://ad.doubleclick.net/ad/' + dclkPage + ';ord='
	 + random + '" height=60 width=468>' + '</a>');
	document.write('</iframe>');
	document.write('</center></nolayer>');
	document.write('<layer  src="http://ad.doubleclick.net/adl/' + dclkPage + 
	 ';ord=' + random + '"></layer>');
	document.write('<ilayer visibility=hide width=468 height=83></ilayer>');
}


//		top.location = "/show.cgi?" + adcategory + "=" + location.pathname;


// -->
</SCRIPT>
<noscript>
<p align="center">
<a href="http://ad.doubleclick.net/jump/www.codeguru.com/cpp;ord=NupaYdFCY34AAHfhhwI">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=NupaYdFCY34AAHfhhwI"></a>
</p>
</noscript>





<BR Clear>
<H1>rope&lt;T, Alloc&gt;</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 = "39" ></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 designed
for efficient operation that involve the string as a whole.  Operations
such as assignment, concatenation, and substring take time that is
nearly independent of the length of the string.  Unlike C strings,
<tt>rope</tt>s are a reasonable representation for very long strings such as
edit 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 are
almost <A href="Sequence.html">Sequence</A>s, this is rarely the most efficient way to
accomplish a task.  Replacing an individual character in a <tt>rope</tt> is
slow: each character replacement essentially consists of two substring
operations followed by two concatenation operations.  <tt>Rope</tt>s
primarily target a more functional programming style.
<P>
They differ from <tt><A href="Vector.html">vector</A>&lt;char&gt;</tt> or reference-counted string
implementations in the following ways.
<P>
Advantages:
<UL>
<LI>
Much faster concatenation and substring operations involving long
strings.  Inserting a character in the middle of a 10 megabyte rope
should take on the order of 10s of microseconds, even if a copy of the
original 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 &quot;flat&quot;
string representation.  The time required for concatenation can be
viewed as constant for most applications.  It is perfectly reasonable
to 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 small
chunks, significantly reducing memory fragmentation problems introduced
by large blocks.
<LI>
Assignment is simply a (possibly reference counted) pointer
assignment.  Unlike reference-counted copy-on-write implementations,
this remains largely true even if one of the copies is subsequently
slightly modified. It is very inexpensive to checkpoint old versions
of 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>.  Thus
a piece of a rope may be a 100MByte file, which is read only when that section
of the string is examined.  Concatenating a string to the end of such a file
does not involve reading the file.  (Currently the implementation of this
facility is incomplete.)
</UL>
Disadvantages:
<UL>
<LI>
Single character replacements in a <tt>rope</tt> are expensive.  A character
update requires time roughly logarithmic in the length of the string.
It is implemented as two substring operations followed by two
concatenations.
<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>&lt;char&gt;</tt>.  However this is slower than for
<tt><A href="Vector.html">vector</A>&lt;char&gt;</tt> by a significant constant factor (roughly a factor
of 5 or 10 if little processing is done on each character and the
string is long).  Nonconst iterators involve additional checking, and
are hence a bit slower still.  (We expect that eventually some common
algorithms will be specialized so that this cost is not encountered.
Currently only output, conversion to a C string, and the
single-character find member function are treated in this way.)
<LI>
Iterators are on the order of a dozen words in size.  This means that
copying them, though not tremendously expensive, is not a trivial
operation.  Avoid postincrementing iterators; use preincrement
whenever possible. (The interface also provides primitives for
indexing into a string using integer character positions.  Passing
positions around is clearly much cheaper, but this makes the indexing
operation expensive, again roughly logarithmic in the length of the
rope.)
</UL>
Experience with previous implementations for other programming
languages suggests that <tt>rope</tt>s are a good choice as the normal or
default representation of strings in a program.  It will occasionally
be necessary to use some type of character array, such as
<tt><A href="Vector.html">vector</A>&lt;char&gt;</tt>, in places that are particularly sensitive to the
performance of traversals or in-place updates.  But the use of <tt>rope</tt>s
minimizes the number of cases in which program running times become
intolerable 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 random
access const_iterators.  Forward or backward traversals take constant
time per operation.  Nonconstant iterators are also provided.
However, assignment through a nonconst iterator is an expensive
operation (basically logarithmic time, but with a large constant).  It
should 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 to
the rope.  Mutable iterators refer to the same position in the same
<tt>rope</tt> after an update.  (This may be surprising if the iterators refers
to a position after an insertion point.)  They remain valid unless the
iterator refers to a position that is more than one past the end of the
resulting <tt>rope</tt>.  
<h3>Definition</h3>
Defined in <A href="rope.h">rope.h</A>.  Some of implementation is contained in the
internal file <A href="ropeimpl.h">ropeimpl.h</A>.
<h3>Example</h3>
<pre>
crope r(1000000, 'x');          // crope is rope&lt;char&gt;. wrope is rope&lt;wchar_t&gt;
                                // Builds a rope containing a million 'x's.
                                // Takes much less than a MB, since the
                                // different pieces are shared.
crope r2 = r + &quot;abc&quot; + r;       // concatenation; takes on the order of 100s
                                // of machine instructions; fast
crope r3 = r2.substr(1000000, 3);       // yields &quot;abc&quot;; 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>
&nbsp;
</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" tppabs="http://www.sgi.com/Technology/STL/BackInsertionSequence.shtml">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&amp; f, const const_iterator&amp; 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&amp; f, const iterator&amp; 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>&lt;charT&gt;*, 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&amp; 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&amp; operator=(const rope&amp;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&amp; 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>
1234

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -