Dynamic String in array

[lost110]

So I have to input a sentence from the user. Each word should be stored in a 2d array whose columns vary in size and each row stores one word as a null-terminated string!
e.g:
|H|o|w|NULL|
|a|r|e|NULL|
|y|o|u|?|NULL
So how can I do this dynamically? Because the user is not gonna tell me that how long his sentence is gonna be!

[Ganado]

A bit roundabout way of doing it:

// Example program
#include <iostream>
#include <string>
#include <sstream>

void add_word(char**& arr, int& arr_size, const std::string& word)
{
    char** new_arr = new char*[arr_size + 1];
    for (int i = 0; i < arr_size; i++)
    {
        new_arr[i] = arr[i];
    }
    
    new_arr[arr_size] = new char[word.length() + 1]; // +1 for null terminator
    for (size_t i = 0; i < word.length(); i++)
    {
        new_arr[arr_size][i] = word[i];
    }
    new_arr[arr_size][word.length()] = '\0';

    delete[] arr;
    arr = new_arr;
    arr_size += 1;
}

void destroy(char** arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        delete[] arr[i];
    }
    delete[] arr;
}

int main()
{
    std::string sentence;
    std::cout << "Enter sentence: ";
    std::getline(std::cin, sentence);
    
    char** arr = nullptr;
    int num_words = 0;

    // I use a stringstream to extract each word from the sentence.
    std::istringstream iss(sentence);
    std::string word;
    while (iss >> word)
    {
        add_word(arr, num_words, word);
    }

    for (int i = 0; i < num_words; i++)
    {
        std::cout << arr[i] << '\n';   
    }
    
    destroy(arr, num_words);
}

This might be what code would look like if you were doing it sanely in modern C++:

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

int main()
{
    std::string sentence;
    std::cout << "Enter sentence: ";
    std::getline(std::cin, sentence);

    std::istringstream iss(sentence);
    
    std::vector<std::string> words;
    
    // I use a stringstream to extract each word from the sentence.
    std::string temp_word;
    while (iss >> temp_word)
    {
        words.push_back(temp_word);
    }
    
    for (const std::string& word : words)
    {
        std::cout << word << '\n';
    }
}

[Duthomhas]

By “dynamically” I assume you mean dynamically-allocated char* strings? And not std::string and std::vector?

There are several basic possibilities for structure here (and multiple ways to accomplish one of them), and your post is not sufficiently specific to distinguish them. I suspect that what is wanted, though, is explained here:
(How do I declare a 2d array in C++ using new?|https://stackoverflow.com/a/936702/2706707)


The trick, then, is to read the individual words and put them in the array.

Again, there are multiple ways to accomplish this. I suggest a two-pass approach:

(1) Count the number of words. Allocate the pointer array.
(2) Read each word and allocate the sub-arrays (strings).

This presumes an additional 1D array used to obtain the entire string (all words at once) from the user before collecting it into individual pieces.

If you must read one word at a time, you can assume a smaller input array for reading from the user (50 characters should suffice for Basic Latin-1 text), then dynamically resize your pointer array each time you get a new word.


Both of these methods are really inefficient, and I would not use them if requirements did not specify it. Yours appear to, sadly.

Hope this helps.

[lastchance]

Put the words in a linked list.
When you complete the sentence, create an array and copy the words into that.

[lost110]

Ganado! Can you do it without sstream! I cannot use this library.

[lost110]

I did this Lol! But this is just for a specific sentence like " Hello How are you? " . But I am not understanding how will I do it dynamically so that no extra memory is used! all the words end with a null character.

#include<iostream>
#include<string>
using namespace std;
int main()
{
	char **P = new char*[4];
	P[0] = new char[5];
	P[1] = new char[3];
	P[2] = new char[3];
	P[3] = new char[4];
	cout << "Enter sentence:";
	for (int i = 0; i < 5; i++)
	{
		cin >> P[0][i];
	}
	for (int i = 0; i < 3; i++)
	{
		cin >> P[1][i];
	}
	
	for (int i = 0; i < 3; i++)
	{
		cin >> P[2][i];
	}
	
	for (int i = 0; i < 4; i++)
	{
		cin >> P[3][i];
	}
	for (int i = 0; i < 5; i++)
	{
		cout << P[0][i];
	}
	cout << endl;
	for (int i = 0; i < 3; i++)
	{
		cout << P[1][i];
	}
	cout << endl;
	for (int i = 0; i < 3; i++)
	{
		cout << P[2][i];
	}
	cout << endl;
	for (int i = 0; i < 4; i++)
	{
		cout << P[3][i];
	}
	cout << endl;


	system("pause");

}

[poteto]

If you can't use sstream just manually look for the spaces in a loop... You can't solve this with just cin >> since cin >> doesn't care about newlines.

Also your solution is the equivalent to using fixed sized arrays but you also get memory leaks, and you aren't using null terminated arrays since you are printing letter by letter.

If your teacher hasn't taught you how to use dynamically allocated arrays (since you aren't properly freeing your memory...), perhaps the solution is to not use dynamically allocated arrays, and just assume every word is going to be at less than X letters and every sentence is going to be at less than Y words, naive but it is either that, or Ganado has the right solution.

Of course there are 100 ways to accomplish the same solution using things like linked lists, or you could loop through the sentence twice just to find the size before hand, or allocate the memory into C++ data and make C reference that data (why not just use C++ then?).

[Duthomhas]

I’m beginning to lose steam.

People come asking for handouts, and instead of taking the effort to understand the problem, they unfailingly take the most difficult, least comprehensive way through, because it doesn’t involve doing something like clicking a link and learning a basic pattern.

I’m not picking on this particular OP; it is a recurring pattern.


Personally, if I were forbidden to use standard C++ library objects like vector and string, I would be inclined to use a linked list and a dynamic string input function. But that involves overhead that (1) I don’t think will help OP in keeping his assignment simple, and (2) is specifically not an array, which is what the OP said his assignment asked for. Usually, when you are told to use an “array”, professor does not expect to see linked lists or other fancy structures.


For variable-length input you are not going to get it any simpler than the two-pass approach I suggested.
Every other approach requires extra effort in terms of structure and for dealing with corner cases.

Good luck.

[lastchance]

#include <iostream>
#include <sstream>
#include <cstring>
using namespace std;

class Node
{
public:
   char *word;
   Node *next = nullptr;

   Node( const char *inword )
   {
      word = new char[ strlen( inword ) + 1 ];
      strcpy( word, inword );
   }
};


int main()
{ 
   stringstream in( "Youth is happy because it has the ability to see beauty   "
                    "Anyone who keeps the ability to see beauty never grows old" );
// istream &in = cin;

   // For handling words
   char wordBuffer[80];
   int pos = 0;
   bool insideWord = false;

   // Create linked list
   Node *head = nullptr;
   Node *tail = nullptr;
   int size = 0;
   while ( true )
   {
      char c;
      if ( !in.get( c ) || isspace( c ) )
      {
         if ( insideWord )            // need to end word
         {
            wordBuffer[pos] = '\0';   pos = 0;
            Node *n = new Node( wordBuffer );
            if ( !head ) head = n;
            if ( tail ) tail->next = n;
            tail = n;
            size++;
         }
         insideWord = false;
      }
      else                             // begin, or continue, word
      {
         wordBuffer[pos++] = c;
         insideWord = true;
      }
      
      if ( !in ) break;                // for stringstream input
//    if ( c == '\n' ) break;          // for terminal input
   }

   // Build an array (and delete linked list)
   char **Array = new char *[size];
   for ( int i = 0; i < size; i++ )
   {
      Array[i] = new char[ strlen( head->word ) + 1 ];
      strcpy( Array[i], head->word );
      delete head->word;
      Node *temp = head;   head = head->next;   delete temp;
   }

   // Write array
   for ( int i = 0; i < size; i++ ) cout << Array[i] << '\n';
}

Youth
is
happy
because
it
has
the
ability
to
see
beauty
Anyone
who
keeps
the
ability
to
see
beauty
never
grows
old

Or to keep @Duthomas happy:

#include <iostream>
#include <cstring>
using namespace std;

int main()
{ 
   // For handling words
   const int MAXLENGTH = 1000;
   char sentenceBuffer[MAXLENGTH];                            // Remember: short is beautiful!
   cout << "Enter a sentence: ";
   cin.getline( sentenceBuffer, MAXLENGTH, '\n' );

   char wordBuffer[80];                                       // Ditto
   bool insideWord = false;
   int size;

   char **Array;

   for ( int pass = 1; pass <= 2; pass++ )
   {
      size = 0;
      for ( int n = 0, i = 0, pos = 0; n <= strlen( sentenceBuffer ); n++ )   // Deliberately want '\0' as well
      {
         char c = sentenceBuffer[n];
         if ( !c || isspace( c ) )
         {
            if ( insideWord ) size++;
            if ( pass == 2 )
            {
               wordBuffer[pos] = '\0';   pos = 0;
               Array[i] = new char[ strlen( wordBuffer ) + 1 ];
               strcpy( Array[i], wordBuffer );   i++;
            }
            insideWord = false;
         }
         else
         {
            if ( pass == 2 ) wordBuffer[pos++] = c;
            insideWord = true;
         }
      }
      if ( pass == 1 ) Array = new char *[size];
   }

   for ( int i = 0; i < size; i++ ) cout << Array[i] << '\n';
}

Enter a sentence: Someone had blundered; theirs not to make reply; theirs not to reason why; theirs but to do and die.
Someone
had
blundered;
theirs
not
to
make
reply;
theirs
not
to
reason
why;
theirs
but
to
do
and
die.

[Enoizat]

Even if I love the beautiful codes I’ve seen so far, I’m afraid lost110’s teacher could be a std::strtok fan who craves seeing it playing…
I may be wrong, of course.

[Ganado]

Makes me want to bang my head on the table that someone is allowed to use strtok but not stringstreams... especially when strtok is arguably more error-prone, but essentially does the same exact thing.

lost110 wrote:

Can you do it without sstream! I

Given a sentence "This is a sentence", do you know how to break it up into 4x strings, "this" "is" "a" "sentence"? Focus on a program that solely does this. Try it yourself.

[lastchance]

I’m afraid lost110’s teacher could be a std::strtok fan who craves seeing it playing…

#include <iostream>
#include <cstring>
using namespace std;

int main()
{ 
   // For handling words
   const int MAXLENGTH = 1000;
   char buffer[MAXLENGTH], buffer2[MAXLENGTH];
   cout << "Enter a sentence: ";
   cin.getline( buffer, MAXLENGTH - 1, '\n' );

   int size = 0;

   strcpy( buffer2, buffer );
   char *p = strtok( buffer, " " );
   while ( p )
   {
      size++;
      p = strtok( nullptr, " " );
   }
   
   char **Array = new char *[size];
   strcpy( buffer, buffer2 );
   int i = 0;
   p = strtok( buffer, " " );
   while ( p )
   {
      Array[i] = new char[ strlen( p ) + 1 ];
      strcpy( Array[i++], p );
      p = strtok( nullptr, " " );
   }

   for ( int i = 0; i < size; i++ ) cout << Array[i] << '\n';
}

Yuk!

[Enoizat]

How does it work, lastchance? When pass == 1 you count the numbers of tokens, and when pass == 2 you actually add them to Array? Am I right?
That’s a pretty intricate code for me.

[lastchance]

Hi @Enoizat, yes you are right. A lot of commands were common to the two passes so I tried looping on pass. You can't set the outer size of the array until you've counted the entire number of words.

In the latest incarnation I used strtok and I've just separated the counting and setting passes.

It does require you store the whole sentence (as opposed to just a word) and strtok destroys the original string, so you have to keep a copy as well.

[Enoizat]

Far easier to read for me now, lastchance.
Intricate code makes my head spin :-) I’m really terrible at pattern recognition and all that stuff.
That’s probably why I gave up trying those spoj/codechef/whatevermathbased exercises.

[Duthomhas]

Heh heh heh:

#include <stdio.h>

int main( int argc, char** argv )
{
  puts( "The sentence array is:" );
  for (int n = 1; n < argc; n++)
    puts( argv[n] );
}

:^>

[Duthomhas]

But, if to do it myself...

#include <ctype.h>
#include <iso646.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* find_word( char* s ) { while (*s and  isspace( *s )) ++s; return s; }
char* skip_word( char* s ) { while (*s and !isspace( *s )) ++s; return s; }
char* copy_word( char* s )
{
  char* p = skip_word( s );
  char* word = (char*)malloc( p - s + 1 );
  strncpy( word, s, p - s );
  word[ p - s ] = '\0';
  return word;
}

int main()
{
  // Get the sentence from the user
  char* sentence = (char*)malloc( 1000 );
  printf( "sentence? " ); 
  fflush( stdout );
  fgets( sentence, 1000, stdin );

  // Count words  
  size_t nwords = 0;
  for (char* word = find_word( sentence ); *word; word = find_word( skip_word( word ) )) 
    nwords += 1;
  
  // Create words array
  char** words = (char**)malloc( nwords * sizeof( char* ) );

  // Fill words array
  nwords = 0;
  for (char* word = find_word( sentence ); *word; word = find_word( skip_word( word ) ))
    words[nwords++] = copy_word( word );

  free( sentence );

  // Display the words
  for (size_t n = 0; n < nwords; n++) printf( "%d: %s\n", (int)(n+1), words[n] );

  // Clean up!
  for (size_t n = 0; n < nwords; n++) free( words[n] );
  free( words );

  return 0;
}

$ a
sentence? And the raven, never flitting, still is sitting, still is sitting  On the pallid bust of Pallas just above my chamber door
1: And
2: the
3: raven,
4: never
5: flitting,
6: still
7: is
8: sitting,
9: still
10: is
11: sitting
12: On
13: the
14: pallid
15: bust
16: of
17: Pallas
18: just
19: above
20: my
21: chamber
22: door

:O)

[Ganado]

Honestly much better than I was imagining. I like the find_word and skip_word helper functions.
To avoid the hardcoded 1000 limit that I think is set, one could use the function here: http://www.cplusplus.com/forum/beginner/248142/4/#msg1094161

[Duthomhas]

Do it like this:

#include <iso646.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char* readline( FILE* f, size_t n, ... ) // n == allocation granularity
{
  size_t N = n;
  char  *p, *s = (char*)malloc( n );
  if (s and fgets( s, n, f ))
  {
    p = strchr( s, '\n' );
    while (!p)
    {
      p = (char*)realloc( s, N + n );
      if (!p or !fgets( p + N - 1, n + 1, f )) return s;
      p = strchr( (s = p) + N, '\n' );
      N += n;
    }
    *p = '\0';
    return s;
  }
  free( s );
  return NULL;
}

#define readline(...) readline( __VA_ARGS__, 128 )

Use it like this:

int main()
{
  char* s = readline( stdin );
  if (s) puts( s );
  free( s );
}

Or like this:

int main()
{
  char* s = readline( stdin, 10 );
  if (s) puts( s );
  free( s );
}

Choose the granularity carefully. It should fall somewhere along in [+1 , +1.5] standard deviations on the bell curve for the expected input size. Otherwise you are just wasting memory.

[Ganado]

Very nice, I never had to use realloc before.