Are std::strings good at random insertion / random erasing?

I want to make a simple text editor using std::strings. If my text is 500,000 chara开发者_如何转开发cters and I want to insert or remove at the 253,000th character, will this be slow, or will it be just as fast as if my text contained 10 characters? Otherwise I'm not sure what I'll do to fix it (unless I use a linked list but then reading is slow and it is sort of reinventing the wheel.

Thanks

I've never used it myself, but I believe this is what rope is for.

It will likely be slow since it has to copy the memory. It depends on the internal implementation of your operating system/processor and its memory operations.

In practice, it will probably be "fast enough". However, I'd still write a EditBuffer class, encapsulating it, and giving this new class an interface tuned to my application. That way, the fact that I'm using std::string, and not something else, becomes an implementation detail of EditBuffer, which can be changed at any time. (You might want to try std::vector as well. And one common optimization is maintaining a hole at the cursor: the text behind the cursor is at the end of the buffer. Advancing the cursor means moving one character, but insertion is normally in constant time.)

It's likely to be slow, though whether or not it is slow enough to be an issue is something you'll have to test. One alternate implementation is to use a list of strings, one per line of text.

This is the wrong type.

Insertion (not at the end) on a std::string has a complexity of O(n).

You want a structure that has average complexity for insertion/deletion/modification of O(1).

ie. the cost of insertion should not be related to the size of the data.

Considering that memory bandwidth is given in GB/s

http://en.wikipedia.org/wiki/DDR3_SDRAM

how long would you estimate copying 256k would take?

I'd seriously consider storing the text not as a single large string, but as individual lines. std::list<std::string> or std::vector<std::string> would seem appropriate. Such an approac would effectively distribute your large string over multiple smaller ones, and reallocations upon modification would only ever occur to the individual line, or to the array of lines in itself. The only tradeoff you'd have to choose is between std::vector and std::list, although I'd tend to prefer std::list here.

Another advantage of line-wise approach is when reading files, you can easily read line by line with std::getline and won't have to care about read buffers yourself.