Standard Template Library Programmer's Guide
Здесь есть возможность читать онлайн «Standard Template Library Programmer's Guide» весь текст электронной книги совершенно бесплатно (целиком полную версию без сокращений). В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Жанр: Программирование, Справочники, на английском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.
- Название:Standard Template Library Programmer's Guide
- Автор:
- Жанр:
- Год:неизвестен
- ISBN:нет данных
- Рейтинг книги:4 / 5. Голосов: 1
-
Избранное:Добавить в избранное
- Отзывы:
-
Ваша оценка:
- 80
- 1
- 2
- 3
- 4
- 5
Standard Template Library Programmer's Guide: краткое содержание, описание и аннотация
Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Standard Template Library Programmer's Guide»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.
Standard Template Library Programmer's Guide — читать онлайн бесплатно полную книгу (весь текст) целиком
Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Standard Template Library Programmer's Guide», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.
Интервал:
Закладка:
rope
Category: containers
Component type: tye
Rope 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, rope s are a reasonable representation for very long strings such as edit buffers or mail messages. [1]
Though rope s can be treated as Containers of characters, and are almost Sequences, this is rarely the most efficient way to accomplish a task. Replacing an individual character in a rope is slow: each character replacement essentially consists of two substring operations followed by two concatenation operations. Rope s primarily target a more functional programming style.
They differ from vector or reference-counted string implementations in the following ways.
Advantages:
• 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, e.g. 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 be viewed as constant for most applications. It is perfectly reasonable to use a rope as the representation of a file inside a text editor.
• Potentially much better space performance. Minor modifications of a rope can share memory with the original. Rope s are allocated in small chunks, significantly reducing memory fragmentation problems introduced by large blocks.
• 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, e.g. in an edit history.
• It is possible to view a function producing characters as a rope . 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.)
Disadvantages:
• Single character replacements in a rope 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.
• A rope can be examined a character at a time through a const_iterator in amortized constant time, as for vector . However this is slower than for vector 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.)
• 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.)
Experience with previous implementations for other programming languages suggests that rope 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 vector , in places that are particularly sensitive to the performance of traversals or in-place updates. But the use of rope s minimizes the number of cases in which program running times become intolerable due to unexpectedly long string inputs.
A rope is almost, but not quite, a Sequence. 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.
In order to discourage accidental use of expensive operations, the begin and end member functions on ropes return const_iterator . If non-const iterators are desired, the member functions mutable_begin and mutable_end should be used.
Any modification of a rope invalidates const iterators referring to the rope. Mutable iterators refer to the same position in the same rope 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 rope .
Defined in the header rope, and in the backward-compatibility header rope.h. The rope class, and the rope header, are SGI extensions; they are not part of the C++ standard.
crope r(1000000, 'x'); // crope is rope. wrope is rope
// 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; fast
crope 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.
Parameter | Description | Default |
---|---|---|
T |
The rope 's value type: usually char or wchar_t . [2] | |
Alloc |
The rope 's allocator, used for all internal memory management. | alloc |
Random Access Container. Almost, but not quite, a model of Front Insertion Sequence and Back Insertion Sequence.
None, except for those imposed by the requirements of Random Access Container.
None.
Member | Where defined | Description |
---|---|---|
value_type |
Container | The rope 's value type T , usually char or wchar_t . |
difference_type |
Container | A signed integral type. |
size_type |
Container | An unsigned integral type. |
reference | Container | Reference to a rope element. [3] |
const_reference |
Container | Const reference to T . [3] |
pointer |
Container | Pointer to T . [3] |
const_pointer |
Container | Const pointer to T . [3] |
const_reverse_iterator |
Reversible | Container Const iterator used to iterate backwards through a rope . |
reverse_iterator |
Reversible | Container Mutable iterator used to iterate backwards through a rope . |
iterator |
Container | Mutable random access iterator used to iterate through a rope . |
const_iterator |
Container | Const random access iterator used to iterate through a rope . |
rope(const charT* s) |
rope |
Constructs a rope from a C string. |
rope(const charT* s, size_t n) |
rope |
Constructs a rope from a (not necessarily null-terminated) array of charT . |
rope(const const_iterator& f, const const_iterator& l) |
Sequence | Creates a rope with a copy of a range. |
rope(const iterator& f, const iterator& l) |
Sequence | Creates a rope with a copy of a range. |
rope(const charT* f, const charT* l) |
Sequence | Creates a rope with a copy of a range. |
rope(charT c) |
rope |
Single-character constructor. |
rope() |
Container | Default constructor. |
rope(char_producer*, size_t, bool) |
rope |
See below. |
rope(const rope& x) |
Container | The copy constructor. |
~rope() |
Container | The destructor. |
rope& operator=(const rope&x) |
Container | The assignment operator. |
void swap(rope& x) |
Container | Swaps the contents of two rope s. |
size_type size() const |
Container | Returns the size of the rope . |
size_type length() const |
rope |
Same as size |
size_type max_size() const | Container | Size of longest rope guaranteed to be representable. |
bool empty() const |
Container | Equivalent to size() == 0 . |
const_iterator begin() const |
Container | Returns an const_iterator pointing to the beginning of the rope . |
const_iterator end() const |
Container | Returns an const_iterator pointing to the end of the rope . |
iterator mutable_begin() |
rope |
Returns an iterator pointing to the beginning of the rope . |
iterator mutable_end() |
rope |
Returns an iterator pointing to the end of the rope . |
const_reverse_iterator rbegin() const |
Reversible Container | Returns a const_reverse_iterator pointing to the beginning of the reversed rope |
const_reverse_iterator rend() const |
Reversible Container | Returns a const_reverse_iterator pointing to the end of the reversed rope |
iterator mutable_rbegin() |
rope |
Returns a reverse_iterator pointing to the beginning of the reversed rope . |
iterator mutable_rend() |
rope |
Returns a reverse_iterator pointing to the end of the reversed rope . |
charT operator[](size_type n) const |
Random Access | Container Returns the n 'th element. |
charT at(size_type pos) const |
Random Access | Container Returns the n 'th element. |
reference mutable_reference_at(size_type n) |
rope |
Returns a reference to the n th element. |
int compare(const rope&) const |
rope |
Three-way comparison. See below. |
charT front() const |
Sequence | Returns the first element. |
charT back() const |
Back Insertion Sequence | Returns the last element. |
void push_front() |
Front Insertion Sequence | Inserts a new element at the front. |
void push_back(charT) |
Back Insertion Sequence | Inserts a new element at the end. |
void pop_front() |
Front Insertion Sequence | Removes the first element. |
void pop_back() |
Back Insertion Sequence | Removes the last element. |
iterator insert(const iterator& p, const rope& x) |
rope |
Inserts the contents of x before p . |
iterator insert(const iterator& p, charT c) |
Sequence | Inserts c before p . |
iterator insert(const iterator& p) |
Sequence | Inserts charT() before p . |
iterator insert(const iterator& p, size_t n, charT c) |
Sequence | Inserts n copies of c before p . |
iterator insert(const iterator& p, const charT* s) |
rope | Inserts a C string before p . |
iterator insert(const iterator& p, const charT* s, size_t n) |
rope |
Inserts a (not necessarily null-terminated) array of charT before p . |
iterator insert(const iterator& p, const charT* f, const char* l) |
Sequence | Inserts the range [f, l) before p . |
iterator insert(const iterator& p, const const_iterator& f, const const_iterator& l) |
Sequence | Inserts the range [f, l) before p . |
iterator insert(const iterator& p, const iterator& f, const iterator& l) |
Sequence | Inserts the range [f, l) before p . |
void insert(size_t i, const rope& x) |
rope |
Inserts the contents of x before the i th element. |
void insert(size_t i, charT c) |
rope |
Inserts the character c before the i th element. |
void insert(size_t i) |
rope |
Inserts the character charT() before the i th element. |
void insert(size_t i, size_t n, charT c) |
rope |
Inserts n copies of c before the i th element. |
void insert(size_t i, const charT* s) |
rope |
Inserts a C string before the i th element. |
void insert(size_t i, const charT* s, size_t n) |
rope |
Inserts a (not necessarily null-terminated) array of charT before the i th element. |
void insert(size_t i, const charT* f, const charT* l) |
rope |
Inserts the range [f, l) before the i th element. |
void insert(size_t i, const const_iterator& f, const const_iterator& l) |
rope |
Inserts the range [f, l) before the i th element. |
void insert(size_t i, const iterator& f, const iterator& l) |
rope |
Inserts the range [f, l) before the i th element. |
void erase(const iterator& p) |
Sequence | Erases the element pointed to by p . |
void erase(const iterator& f, const iterator& l) |
Sequence | Erases the range [f, l) . |
void erase(size_t i, size_t n) |
rope |
Erases n elements, starting with the i th element. |
append(const charT* s) |
rope |
Appends a C string. |
append(const charT* s, size_t) |
rope |
Appends a (not necessarily null-terminated) array of charT . |
append(const charT* f, const charT* l) |
rope |
Appends a range. |
append(charT c) |
rope |
Appends the character c . |
append() |
rope |
Appends the character charT() . |
append(size_t n, charT c) |
rope |
Appends n copies of c . |
append(const rope& x) |
rope |
Appends the rope x . |
void replace(const iterator& f, const iterator& l, const rope&) |
rope |
See below. |
void replace(const iterator& f, const iterator& l, charT) |
rope |
See below. |
void replace(const iterator& f, const iterator& l, const charT* s) |
rope |
See below. |
void replace(const iterator& f, const iterator& l, const charT* s, size_t n) |
rope |
See below. |
void replace(const iterator& f1, const iterator& l1, const charT* f2, const charT* l2) |
rope |
See below. |
void replace(const iterator& f1, const iterator& l1, const const_iterator& f2, const const_iterator& l2) |
rope |
See below. |
void replace(const iterator& f1, const iterator& l1, const iterator& f2, const iterator& l2) |
rope |
See below. |
void replace(const iterator& p, const rope& x) |
rope |
See below. |
void replace(const iterator& p, charT c) |
rope |
See below. |
void replace(const iterator& p, const charT* s) |
rope |
See below. |
void replace(const iterator& p, const charT* s, size_t n) |
rope |
See below. |
void replace(const iterator& p, const charT* f, const charT* l) |
rope |
See below. |
void replace(const iterator& p, const_iterator f, const_iterator l) |
rope |
See below. |
void replace(const iterator& p, iterator f, iterator l) |
rope |
See below. |
void replace(size_t i, size_t n, const rope& x) |
rope |
See below. |
void replace(size_t i, size_t n, const charT* s, size_t n) |
rope |
See below. |
void replace(size_t i, size_t n, charT c) |
rope |
See below. |
void replace(size_t i, size_t n, const charT* s) |
rope |
See below. |
void replace(size_t i, size_t n, const charT* f, const charT* l) |
rope |
See below. |
void replace(size_t i, size_t n, const const_iterator& f, const const_iterator& l) |
rope |
See below. |
void replace(size_t i, size_t n, const iterator& f, const iterator& l) |
rope |
See below. |
void replace(size_t i, charT c) |
rope |
See below. |
void replace(size_t i, const rope& x) |
rope |
See below. |
void replace(size_t i, const charT* s) |
rope |
See below. |
void replace(size_t i, const charT* s, size_t n) |
rope |
See below. |
void replace(size_t i, const charT* f, const charT* l) |
rope |
See below. |
void replace(size_t i, const const_iterator& f, const const_iterator& l) |
rope |
See below. |
void replace(size_t i, const iterator& f, const iterator& l) |
rope |
See below. |
rope substr(iterator f) const |
rope |
See below. |
rope substr(const_iterator f) const |
rope |
See below. |
rope substr(iterator f, iterator l) const |
rope |
See below. |
rope substr(const_iterator f, const_iterator l) const |
rope |
See below. |
rope substr(size_t i, size_t n = 1) const |
rope |
See below. |
void copy(charT* buf) const |
rope |
Copies a rope into an array of charT . |
size_type copy(size_type pos, size_type n, charT* buf) |
rope |
Copies a rope into an array of charT . |
const charT* c_str() const |
rope |
See below. |
void delete_c_str() |
rope |
See below. |
rope operator+(const rope& L, const rope&R) |
rope |
Concatenates L and R . This is a global function, not a member function. |
rope& operator+=(rope& L, const rope& R) |
rope |
Appends R to L . This is a global function, not a member function. |
rope operator+(const rope& L, const charT* s) |
rope |
Concatenates L and s . This is a global function, not a member function. |
rope& operator+=(rope& L, const charT* s) |
rope |
Appends s to L . This is a global function, not a member function. |
rope operator+(const rope& L, charT c) |
rope |
Concatenates L and c . This is a global function, not a member function. |
rope& operator+=(rope& L, charT c) |
rope |
Appends c to L . This is a global function, not a member function. |
bool operator<(const rope&, const rope&) |
Forward Container | Lexicographical comparison. This is a global function, not a member function. |
bool operator==(const rope&, const rope*) |
Forward Container | Tests two rope s for equality. This is a global function, not a member function. |
ostream& operator<<(ostream& os, rope x) |
rope |
Outputs x to the stream os . This is a global function, not a member function. |
These members are not defined in the Random Access Container requirements, but are specific to rope :
Читать дальшеИнтервал:
Закладка:
Похожие книги на «Standard Template Library Programmer's Guide»
Представляем Вашему вниманию похожие книги на «Standard Template Library Programmer's Guide» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.
Обсуждение, отзывы о книге «Standard Template Library Programmer's Guide» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.