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?
3 Answers
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;
}
-
So the class string uses a fixed buffer and resizes this buffer if nesseray?– mjjokerSep 4, 2012 at 17:34
-
So they probably use a neat typ of structure or are you talking of arrays which is automatically resized?– mjjokerSep 4, 2012 at 17:39
-
@mjjoker it's just dynamic arrays (
new[]
) likevector
uses internally. (This is why I say teach the C of C++ before the ++ (either that or trolling)) Sep 4, 2012 at 17:41 -
1If an exception occurs,
str
may contain a partial result - better to create a local string ingetline
, append to that and then move the local string tostr
on completion.– beerboySep 5, 2012 at 2:19 -
1If you use this implementation in a
while
loop let's say, you will still need to readline
one more time after the loop, you will not get the last item from thisgetline
inside thewhile
loop like we are used to do.– 3bdallaFeb 14, 2018 at 6:34
@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?
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.
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.
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."
-
1A standard library's
string
isn't permitted to be implemented as (1), because of the complexity requirement ofoperator[]
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 thestring
, but the standard does say a lot about whatstring
can do. Sep 4, 2012 at 18:11 -
@SteveJessop: Your comment is better than my answer. If you haven't the time or interest to edit the answer in light of your comment, then I'll edit it myself. If I understand your comment correctly, implementation (2) is the only probable one -- or is there an implementation (4) as well?– thbSep 4, 2012 at 18:16
-
1@SteveJessop he's talking about the implementation of
getline
I am thinking, not ofstring
. Also thb, for any implementation numbern
, there is always an implementationn + 1
:) Sep 4, 2012 at 18:18 -
1The reason I made it a comment is that the question asks how
getline
can be implemented, and I'm just remarking howstring
must be implemented in C++. What you say is still true of the classic computer-science problem, andgetline
could do any of the things you say, and then at the end it could copy all the characters from its own data-structure into astring
. Forstring
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. Sep 4, 2012 at 18:23 -
1So while there probably is a 4, it will look fairly 2-ish around the edges :-) For example the "small string optimization" is sometimes used, and an implementation is permitted (although I don't specifically remember hearing of any) to do implementation-specific things that will use memory more efficiently provided that
::operator new
hasn't been overridden by the user. For example, it could ask for sizes that it "just so happens" to know are convenient for the system'smalloc
implementation, so as hopefully not to waste bytes at the end of blocks. Sep 4, 2012 at 18:24
As @3bdalla said, implementation of thb doesn't work as gnu implementation. So, I wrote my own implementation, which works like gnu's one. I don't know what will be with errors in this variant, so it needs to be tested. My implementation of getline:
std::istream& getline(std::istream& is, std::string& s, char delim = '\n'){
s.clear();
char c;
std::string temp;
if(is.get(c)){
temp.push_back(c);
while((is.get(c)) && (c != delim))
temp.push_back(c);
if(!is.bad())
s = temp;
if(!is.bad() && is.eof())
is.clear(std::ios_base::eofbit);
}
return is;
}
-
Might it be more efficient to find the delimiter, then
seekg
back to the original position andreadsome
the whole thing into the output string at once, so that the output string doesn't have to dynamically resize?– nog642Apr 20 at 21:00 -
@nog642, sounds great! You can add your own variant of answer below, so everybody can see it)– Ae_McMay 16 at 12:15
char
array andstring::append
when it gets full or you get to the end of the line.