Implementation of getline ( istream& is, string& str )

Question

My Question is very simple, how is getline(istream, string) implemented? How can you solve the problem of having fixed size char arrays like with getline (char* s, streamsize n ) ? Are they using temporary buffers and many calls to new char[length] or another neat structure?

Answer 1

@SethCarnegie is right: more than one implementation is possible. The C++ standard does not say which should be used.

However, the question is still interesting. It's a classic computer-science problem. Where, and how, does one allocate memory when one does not know in advance how much memory to allocate?

1. One solution is to record the string's characters as a linked list of individual characters. This is neither memory-efficient nor fast, but it works, is robust, and is relatively simple to program. However, a standard library is unlikely to be implemented this way.

2. A second solution is to allocate a buffer of some fixed length, such as 128 characters. When the buffer overflows, you allocate a new buffer of double length, 256 characters, then copy the old characters over to the new storage, then release the old. When the new buffer overflows, you allocate an even newer buffer of double length again, 512 characters, then repeat the process; and so on.

3. A third solution combines the first two. A linked list of character arrays is maintained. The first two members of the list store (say) 128 characters each. The third stores 256. The fourth stores 512, and so on. This requires more programming than the others, but may be preferable to either, depending on the application.

And the list of possible implementations goes on.

Regarding standard-library implementations, @SteveJessop adds that "[a] standard library's string isn't permitted to be implemented as (1), because of the complexity requirement of operator[] for strings. In C++11 it's not permitted to be implemented as (3) either, because of the contiguity requirement for strings. The C++ committee expressed the belief that no active C++ implementation did (3) at the time they added the contiguity requirement. Of course, getline can do what it likes temporarily with the characters before adding them all to the string, but the standard does say a lot about what string can do."

The addition is relevant because, although getline could temporarily store its data in any of several ways, if the data's ultimate target is a string, this may be relevant to getline's implementation. @SteveJessop further adds, "For string itself, implementations are pretty much required to be (2) except that they can choose their own rate of expansion; they don't have to double each time as long as they multiply by some constant."

Answer 2

getline(istream&, string&) is implemented in a way that it reads a line. There is no definitive implementation for it; each library probably differs from one another.

Possible implementation:

istream& getline(istream& stream, string& str)
{
  char ch;
  str.clear();
  while (stream.get(ch) && ch != '\n')
    str.push_back(ch);
  return stream;
}