Thread: best container to hold a text buffer?

  1. #1
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877

    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 ☺

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,068
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    Quote Originally Posted by Salem View Post
    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.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,068
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    Registered User
    Join Date
    Apr 2010
    Posts
    88
    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.
    Last edited by Ocifer; 08-22-2014 at 07:16 PM.
    W7, Ubuntu -- mingw, gcc, g++, code::blocks, emacs, notepad++

  7. #7
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    @ 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.

  8. #8
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,226
    +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.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The ideal for a text editor is the rope data structure.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    Quote Originally Posted by iMalc View Post
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function in a text buffer
    By wellsper in forum C Programming
    Replies: 5
    Last Post: 04-15-2010, 11:00 PM
  2. What is a text buffer ?
    By JFonseka in forum C Programming
    Replies: 5
    Last Post: 04-07-2008, 05:11 AM
  3. List or container to hold types
    By tony_chestnut in forum C++ Programming
    Replies: 6
    Last Post: 04-21-2006, 11:46 AM
  4. Scrolling in a text buffer
    By Kode Kid in forum C Programming
    Replies: 3
    Last Post: 07-17-2005, 03:35 PM
  5. Replies: 4
    Last Post: 03-21-2004, 03:34 PM