Stack Overflow
Stack Overflow

Questions tagged [ropes]

A rope is a data structure used for storing and manipulating strings.

A rope (sometimes called a cord) uses binary trees to store strings.

When compared to a large character array, they allow for faster insertion and deletion of text compared to using a large array, and their memory does not need to be contiguous. However, the total memory requirements can be larger (because of the additional space required to store the tree) and additional complexity of code necessary to manage it.

References

Ropes on Wikipedia

25 questions
41
votes
5 answers

STL Rope - when and where to use

I was wondering under what circumstances you would use a rope over another STL container?
Konrad
  • 39,751
  • 32
  • 78
  • 114
26
votes
5 answers

Is there any scenario where the Rope data structure is more efficient than a string builder

Related to this question, based on a comment of user Eric Lippert. Is there any scenario where the Rope data structure is more efficient than a string builder? It is some people's opinion that rope data structures are almost never better in…
luvieere
  • 37,065
  • 18
  • 127
  • 179
12
votes
4 answers

Public implementation of ropes in C#?

Is there a public implementation of the Rope data structure in C#?
luvieere
  • 37,065
  • 18
  • 127
  • 179
10
votes
1 answer

The rope data structure

I was reading about the rope data structure.I am interested in building a text editor using C++ and Qt. My question is: Does built-in string manipulating functions in programming languages like C++ use the rope data structure? Or do I need to write…
sudeepdino008
  • 3,194
  • 5
  • 39
  • 73
9
votes
3 answers

Insert character in Scala String

For any given String, for instance val s = "abde" how to insert a character c: Char at position 2, after b ? Update Which Scala collection to consider for multiple efficient insertions and deletions at random positions ? (Assuming that a String…
elm
  • 20,117
  • 14
  • 67
  • 113
9
votes
2 answers

Does Python have a rope data structure?

In writing some Python code, I came upon a need for a string-like data structure that offers fast insertion into, access to, and deletion from arbitrary positions. The first data structure that came to mind was a rope. Does Python have a rope data…
icktoofay
  • 126,289
  • 21
  • 250
  • 231
7
votes
1 answer

What is the concatenation complexity of balanced ropes?

I've looked at different papers and here is the information that I've gathered: SGI implementation and C cords neither guarantee O(1) time concatenation for long ropes nor ~log N depth for shorter ones. Different sources contradict each other.…
Yakov Galka
  • 70,775
  • 16
  • 139
  • 220
6
votes
1 answer

Efficient re-hashing of a rope

Given a rope, let's say we need to know its hash (by passing the concatenation of all leaves through some hash function). Now, when one rope leaf changes, what's an efficient way to recalculate the hash of the entire rope again? I.e. something like…
Vladimir Panteleev
  • 24,651
  • 6
  • 70
  • 114
5
votes
2 answers

SGI STL Rope in g++?

It seems that there is a implementation of rope in my /usr/include/c++/4.5.1/ext/rope (and ropeimpl.h). I compared it with SGI STL and the code seems to be pretty much the same codebase. I'm not aware of its status or if its functional or not. Nor i…
lurscher
  • 25,930
  • 29
  • 122
  • 185
5
votes
1 answer

String representations: improvements over ropes?

I want a representation for strings with fast concatenation and editing operations. I have read the paper "Ropes: an Alternative to Strings", but have there been any significant improvements in this area since 1995? EDIT: One possibility I've…
Alexey Romanov
  • 167,066
  • 35
  • 309
  • 487
4
votes
1 answer

Rope data structure & Lines

I'm using a Rope to store a large amount (GB's) of text. The text can be tens of millions of lines long. The rope itself is extremely fast inserting at any position, and is also fast getting a character at a specific position. However, how would I…
WowThere
  • 51
  • 3
4
votes
2 answers

StringBuilder vs Ropes

Good morning, I am writing a language parser, and am looking for the best structure to use for a rollback cache which currently does the following: When requesting a new character from the stream, the character is added to the cache, in case a…
Darkzaelus
  • 2,059
  • 1
  • 15
  • 31
4
votes
2 answers

Using rope in text editors

I was reading up on how I would go about making a text editor from scratch. I came across various different data structures like gap buffers, piece tables, and rope. I can understand how the others would work in practice, and I understand the…
Austin Ewens
  • 148
  • 2
  • 9
3
votes
1 answer

Split operation on rope data structures

I am working on implementing the Rope data structure in C++ for completely abstract objects. The problem I am having is that I can't figure out the implementation of the critical "split" operation. The Wikipedia page is helpful, but vague and highly…
lushr
  • 417
  • 3
  • 10
3
votes
0 answers

How to manipulate a string (move substring to other part of string) in O(log n) using a rope or an order statistics splay tree

Two weeks ago I've finished an implementation of a splay tree that allows basic functions, like insert, delete, find key and and obtain the sum of a range of elements of the three. You can find this implementation here as reference for this question…
Nooblhu
  • 552
  • 15
  • 33
1
2