How to split a string into a linked list? (C++ question)

cabeca · 11-28-2009, 01:49 AM

My first post~~!!! Ahem... but i digress...

I'm writing a simple text editor and I've run into a little problem. The function will receive a string (in form of const void*) and must separate the string by new lines.

An example string that will be passed up is this:

Code:

char* example = 
"This is a line\nThis is a second line\nThis is the third line

My solution to this is to make a linked list and store every mini-string inside it. That way, when it comes to the actual text editing, it'll be easy to scroll through the various lines.

So this is what I have so far:

Code:

void IO_TextEdit::set(const void *str) {
  char* temp = new char[strlen((char *)str)];
  temp = (char *)str;
  int i, j, k;

  k = 0;

  while(temp[k] && (k < (signed)strlen(temp))) {
    char lineHolder[_IO_TEXT_ALLOCATION_LINE_SIZE];
    for(i = k; temp[i] != '\n' && temp[i] != '\0'; i++); //determining the size of the first line
    for(j = k; j < i; j++) //copy the first line into the lineHolder
     lineHolder[j-k] = temp[j];
    lineHolder[i-k] = '\0';

    _textLines.add(lineHolder); //This is the linked list adding the new entry

    k = i + 1;
  }
}

SO, my problem lies in how I'm adding to the linked list. Because lineHolder is essentially a pointer, the data stored in the node contained it _textLines will always point to the same address that lineHolder last pointed to.

So, if I passed a string that contains 3 lines overall, the linked list will contain 3 nodes containing only the last line of the string passed.

I know my solution lies with pre-allocating memory, but I'm not exactly sure how I can do this. I've tried using malloc(), but I'm not quite sure if I'm using it correctly.

Sorry if this was lengthy, but I wanted to be as descriptive as possible. Any help would be highly appreciated!

exscape · 11-28-2009, 05:25 AM

Looks more like C than C++!
The C++ way would be to store the strings as std::strings and use a std::vector<std::string> to store the split ones, rather than operating on a low level of pointers and linked lists.
See sector 7.3 here: http://www.oopweb.com/CPP/Documents/...g-HOWTO-7.html

neonsignal · 11-28-2009, 08:07 AM

Yes, there is a some confusion in the code.

You are allocating space for a temp string at the start, but then overwriting the pointer (which will cause a memory leak).

Code:

char* temp = new char[strlen((char *)str)];
temp = (char *)str;

Then later on, you are copying the partial strings to a lineHolder buffer that has only been allocated on the stack.

Code:

char lineHolder[_IO_TEXT_ALLOCATION_LINE_SIZE];
...
_textLines.add(lineHolder);

When the function exits, not only will the pointers in _textLines all be the same, but they will be pointing to memory that will be overwritten as the stack is used.

Instead, use the new[] to allocate the lineHolder buffer each time around the loop (after calculating the size), so that each line buffer is on the heap.

Code:

char *lineHolder = new char[i-k+1];

Better still, take exscape's suggestion and use the standard template library strings, which will hide a lot of the issues to do with memory allocation.

If you intend to write a significant amount of C++ code, it is worth also being aware of the boost libraries, which can handle some of these basic algorithms. For example, splitting up the string into a list container becomes:

Code:

#include <string>
#include <list>
#include <boost/algorithm/string.hpp>
...
std::string str("This is a line\nThis is a second line\nThis is the third line");
std::list<boost::iterator_range<std::string::iterator> > list;
boost::split(list, str, boost::is_any_of("\n"));

cabeca · 11-28-2009, 09:09 AM

Funny thing is, I actually started with new[].. I can't remember, but I think my problem was actually how I organized it... i think i did something like:

Code:

set() {
  char* lineHolder
  ..
  ..
  while(){
    lineHolder = new char[];
  }

Which did the exact same thing I was doing with the code provided. But, yeah, new[] definitely works, thanks!!! I'm still a new programmer, so I'm not familiar with everything that's available to use, but I will definitely take a look into those libraries---they're probably a helluva lot more effective than me writing on my own.