best container to hold a text buffer?

Hello all,

I've recently been writing a text input field with SDL, It is nearly complete now, but I was hoping I could have your opinion on this one particular aspect.

I am currently using a std::vector<string> to hold input data from the keyboard (text). Basically the way it works is that every index of the vector represents a singular line.

However the requirements for this container make it difficult to choose if another container for the strings would be more efficient. The function that is called when a lines wrap is needed, and also when the user presses enter/return, must use a vector::emplace() (which I understand is inefficient when you have many elements that come after).

Under these conditions, is a vector the best choice? I know a list would be more efficient for inserting elements into the middle of, but also most of the string elements added will probably be added to the end.

I know the general usages for the container types in the STL, but the requirements for this are such that it seems like I'm giving up something whichever way I go.

What do you think? Thanks ☺

I suggest you start with

Code:

---

class paragraph {
  private:
    std::vector<string>  mLines;
  public:
    // methods
};

---

Where you add methods to add, insert, delete, split lines as necessary.

This separates the program logic from your internal data structure choices. If you later decide to change std::vector<string> to something else, the impact on the rest of the system will be minimal.

Quote:

---

Originally Posted by Salem

I suggest you start with

Code:

---

class paragraph {
  private:
    std::vector<string>  mLines;
  public:
    // methods
};

---

Where you add methods to add, insert, delete, split lines as necessary.

This separates the program logic from your internal data structure choices. If you later decide to change std::vector<string> to something else, the impact on the rest of the system will be minimal.

---

Thanks Salem. I was mostly curious to know if using a vector was ok for this task, so it's a relief seeing you recommend it. I've gotten the class written out and it has been a lot of fun figuring it all out (especially all the highlighting stuff!). I'm going to keep working on it but I've definitely got many things I can use.

> so it's a relief seeing you recommend it.
It wasn't a recommendation - it was just the last thing you mentioned.

The whole point of the post was to show you that things marked 'private' can be changed at will without messing up the rest of the code.

If you design your class API (the public methods) properly, then it would be simple to change
std::vector<string> mLines;
to say
std::list<string> mLines;
if (after some testing) you believed that lists would give you an overall performance advantage over vectors.

I'd suggest working out all the operations you want to do to a set of lines, and which (if any) of those operations would be done most frequently.

Without that, you have no basis for optimisation (e.g. picking different containers). There is no point optimising for merging strings, if the most common thing you need to do is sort them.

If you can't do the analysis, keep it simple (e.g. a vector<string>). Get it working right (in the sense of the output needed). Then do profiling with some representative inputs to work out where performance holes are.

I was recently working on something that required a container of VERY non-POD data. I started off using the std::vector< T > container, but noticed a huge improvement in performance when I switched to std::list< T >. In particular, the program was doing a lot of deleting / inserting at indices which were specified at run-time. Your mileage may vary, depending on the size() of the container, and how often you are inserting/deleting. Use profiler software to double check if you're not sure.

The one thing to note is that the std::list does not have a random-access iterator. What this boils down to is you lose the at() method of std::vector.

EDIT: I should point out that the container size I was working with was around 60,000. You should decide based on profiling your program. When I compared execution times of my program using the two containers, std::list was faster by about 15 seconds. So worth it in that case.

EDIT 2: And to OP, yes, there are trade-offs. The first thing you should do is ensure you have the basic functionality and then play with containers. If you find that you really do need some specialized containers, and you are comfortable with incorporating newer aspects of C++, try custom containers. http://seanmiddleditch.com/journal/2...ainers-in-c11/

EDIT 3: In general C++11 has some useful new features like move semantics to optimize performance.

@ Ocifer - Thanks for the advice, and especially the article. One of the favorite things about the book where I learned C++ was that the author took you through building a few custom containers (Thinking in C++), and I can tell it will be interesting to see how it's done using C++11.

I think a vector should suffice for what I'm currently using the text editor for, which is really just to display/edit XML elements where the size is fairly small. I'll take a look at it if I go to re-use it with something else though.

Thanks again, Alpo.

+1 for profiling first.

Just design your code in a way that makes swapping containers easy (like what Salem suggested), then pick a container and stick with it.

Then, if you run into performance problems, profile the code to see if it's in container operations. If so, now you can actually see what operations are most common, and pick a more appropriate container for it.

A lot of times programmers spend way too much time optimizing things that don't matter at all anyways, because it will only end up taking something like 0.1% of the total run time (I am guilty of this myself, all the time).

Always keep your code flexible so that future optimizations are possible, but don't actually spend effort optimizing until there is a performance problem and profiling showed that this is the bottleneck.

The ideal for a text editor is the rope data structure.

Quote:

---

Originally Posted by iMalc

The ideal for a text editor is the rope data structure.

---

That does look really clever. It might take a little while to get the hang of it, but I'll definitely give it a shot. Thanks!