STL Rope – when and where to use

by

Ropes 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, ropes are a
reasonable representation for very
long strings such as edit buffers or
mail messages.

Advantages:

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

  2. Potentially much better space
    performance. Minor modifications of a
    rope can share memory with the
    original. Ropes are allocated in small
    chunks, significantly reducing memory
    fragmentation problems introduced by
    large blocks

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

  4. 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.)

https://wayback.archive.org/web/20130102093702/https://www.sgi.com/tech/stl/Rope.html

More Related Contents:

  1. c++ push reference node to stl list
  2. Erasing elements from a vector
  3. Why can’t I make a vector of references?
  4. Concise explanation of reference collapsing rules requested: (1) A& & -> A& , (2) A& && -> A& , (3) A&& & -> A& , and (4) A&& && -> A&&
  5. Why are Standard iterator ranges [begin, end) instead of [begin, end]?
  6. Why do I get the same sequence for every run with std::random_device with mingw gcc4.8.1?
  7. Using custom std::set comparator
  8. When vectors are allocated, do they use memory on the heap or the stack?
  9. Nice way to append a vector to itself
  10. In STL maps, is it better to use map::insert than []?
  11. Where can I get a “useful” C++ binary search algorithm?
  12. Relative performance of std::vector vs. std::list vs. std::slist?
  13. Is std::vector copying the objects with a push_back?
  14. how-to initialize ‘const std::vector’ like a c array
  15. Is hash_map part of the STL?
  16. How to use std::sort with a vector of structures and compare function?
  17. Why does storing references (not pointers) in containers in C++ not work?
  18. Can std::begin work with array parameters and if so, how?
  19. Checking if an iterator is valid
  20. Iterate keys in a C++ map
  21. How can I use Standard Library (STL) classes in my dll interface or ABI?
  22. Does boost have a datatype for set operations that is simpler than the STL?
  23. How can i estimate memory usage of std::map?
  24. Memory allocation and deallocation across dll boundaries
  25. STL deque accessing by index is O(1)?
  26. Incrementing iterators: Is ++it more efficient than it++? [duplicate]
  27. Can std::vector emplace_back copy construct from an element of the vector itself?
  28. what does `using std::swap` inside the body of a class method implementation mean?
  29. error for hash function of pair of ints
  30. Why does (i|o)fstream take a const char* parameter for a file name?

Leave a Comment