sorting the input

[arnuld]

A program that asks user to input words and then prints them in
alphabetical order. I have used vectors to accomplish task. That left me
wondering with 2 questions:

1) whether list will be a good idea. I am basically concerned about CPU
efficiency.

2) Is the program is a C++ program or C program written in C++.



/* A program that will ask user for input and then will print them
* in an alphabetical order
*
* VERSION 1.0
*
*/


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void ask_input( std::vector<std::string>& );
void print_vector( const std::vector<std::string>& );

int main()
{
std::vector<std::string> svec;
std::vector<std::string>& r_svec = svec;

ask_input( r_svec );

// sort the input
std::sort( r_svec.begin(), r_svec.end() );

std::cout << "--------------------------------"
<< std::endl;

print_vector( r_svec );

return 0;
}



void ask_input( std::vector<std::string>& svec )
{
std::string str;

while( std::cin >> str )
{
svec.push_back( str );
}
}


void print_vector( const std::vector<std::string>& svec )
{
std::vector<std::string>::const_iterator iter = svec.begin();

for( ; iter != svec.end(); ++iter )
{
std::cout << *iter << std::endl;
}
}

 

[书呆彭]

arnuld 写é“:

A program that asks user to input words and then prints them in
alphabetical order. I have used vectors to accomplish task. That left me
wondering with 2 questions:

1) whether list will be a good idea. I am basically concerned about CPU
efficiency.

2) Is the program is a C++ program or C program written in C++.

you wrote nice code of STL style, but i think use typedef to redefine some iterator type is better to read.

in my point of view,the std::sort works better with std::vector than std::list,

but, the std::vector<typename T>:ush_back is less efficient than std::list<>::insert.

so i suggest use list as container of strings.

individual opinion,may be not correct.

 

[James Kanze]

arnuld ??:

It might be better to worry about whether the code works or not.

you wrote nice code of STL style, but i think use typedef to
redefine some iterator type is better to read.

Question of taste. I find that a lot of such typedef's actually
make the code harder to read. I know exactly what an

in my point of view,the std::sort works better with
std::vector than std::list,

That's putting it mildly. Calling std::sort with iterators from
an std::list is undefined behavior, and I suspect that it will
fail to compile with most compilers. std::list does have a sort
member function, however.

but, the std::vector<typename T>:ush_back is less efficient
than std::list<>::insert.

Are you sure about that? I'm not. In the few times I've
actually measured, std::vector<>push_back has turned out to be
faster than std::list<>:ush_back.

About the only time you would want to use std::list<> is when
you need to insert and/or erase somewhere in the middle of the
sequence. And even then, only if the sequence is long, and the
objects expensive to copy.

 

[red floyd]

A program that asks user to input words and then prints them in
alphabetical order. I have used vectors to accomplish task. That left me
wondering with 2 questions:

  1) whether list will be a good idea. I am basically concerned about CPU
  efficiency.

  2) Is the program is a C++ program or C program written in C++.

/* A program that will ask user for input and then will print them
 * in an alphabetical order
 *
 * VERSION 1.0
 *
 */

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void ask_input( std::vector<std::string>& );
void print_vector( const std::vector<std::string>& );

int main()
{
  std::vector<std::string>  svec;
  std::vector<std::string>& r_svec = svec;

  ask_input( r_svec );

  // sort the input
  std::sort( r_svec.begin(), r_svec.end() );

  std::cout << "--------------------------------"
            << std::endl;

  print_vector( r_svec );

  return 0;

}

void ask_input( std::vector<std::string>& svec )
{
  std::string str;

  while( std::cin >> str )
    {
      svec.push_back( str );
    }

}

void print_vector( const std::vector<std::string>& svec )
{
  std::vector<std::string>::const_iterator iter = svec.begin();

  for( ; iter != svec.end(); ++iter )
    {
      std::cout << *iter << std::endl;
    }

}

std::sort is slower on list iterators because they aren't random
access.

 

[Kai-Uwe Bux]

red floyd wrote:

[snip]

std::sort is slower on list iterators because they aren't random
access.

std::sort on list iterator does not meet the conceptual requirements of
std::sort [25.3.1.1]. As a quality of implementation issue, I would expect
a diagnostic message.


Best

Kai-Uwe Bux

 

[Erik Wikström]

arnuld 写é“:

you wrote nice code of STL style, but i think use typedef to redefine
some iterator type is better to read.

in my point of view,the std::sort works better with std::vector than
std::list,

but, the std::vector<typename T>:ush_back is less efficient than
std::list<>::insert.

Unless you have an idea about how many elements you'll end up with. If
you do you can use the vector's reserve() to pre-allocate memory in
which case inserts will be in O(1).

so i suggest use list as container of strings.

I would use a vector until the profiler tells me otherwise.

 

[Erik Wikström]

A program that asks user to input words and then prints them in
alphabetical order. I have used vectors to accomplish task. That left me
wondering with 2 questions:

1) whether list will be a good idea. I am basically concerned about CPU
efficiency.

I doubt you should worry about that, if it is a problem use the vector's
reserve() and pre-allocate space for a large number of elements, memory
is cheap these days.

2) Is the program is a C++ program or C program written in C++.

I do not quite understand the question, this is clearly a C++ program.

std::vector<std::string> svec;
std::vector<std::string>& r_svec = svec;

Drop the r_svec, it serves no purpose.

 

[arnuld]

I do not quite understand the question, this is clearly a C++ program.

I meant, are you sure I am using proper C++ design because after 6 months
of C my mind is locked on C, I can't think of C++ properly.

Like many people still keep on using C's procedural and design constructs
rather than of ISO C++.

Drop the r_svec, it serves no purpose.

but then will it not copy the vector ? rather than getting its reference ?
I am little confused on this. After removing r_svec Program works fine
though.

 

[书呆彭]

James Kanze 写é“:

It might be better to worry about whether the code works or not.



Question of taste. I find that a lot of such typedef's actually
make the code harder to read. I know exactly what an
std::vector<>::iterator is and does; I don't know what a
VectIter is or does.

I guess proper local typedef is better for me.
Maybe not everyone like that.

That's putting it mildly. and I suspect that it will
fail to compile with most compilers. std::list does have a sort
member function, however.

Oh,thanks very much. Today i finaly found why my code doesn't work right.
i did not know that alling std::sort with iterators from
an std::list was undefined behavior before.
That helped me a lot. I'd check my codes.

Are you sure about that? I'm not. In the few times I've
actually measured, std::vector<>push_back has turned out to be
faster than std::list<>:ush_back.

About the only time you would want to use std::list<> is when
you need to insert and/or erase somewhere in the middle of the
sequence. And even then, only if the sequence is long, and the
objects expensive to copy.

In fact that's just what i thought to be.
I have not been using std::list much. I mainly use std::vector in my design.
Sorry for my arbitrariness.

 

[Erik Wikström]

but then will it not copy the vector ? rather than getting its reference ?
I am little confused on this. After removing r_svec Program works fine
though.

No, since you have declared the functions to pass by reference no
copying will occur.

 

[Jorgen Grahn]

A program that asks user to input words and then prints them in
alphabetical order. I have used vectors to accomplish task. That left me
wondering with 2 questions:

1) whether list will be a good idea. I am basically concerned about CPU
efficiency.

2) Is the program is a C++ program or C program written in C++.

It's real C++. You have no need to define any classes, so you don't.
Same with many other language features.

std::cout << "--------------------------------"
<< std::endl;

I would skip the std::endl here though, and use "...---\n" instead.
std::endl is not "the thing you should use instead of '\n'" (although
many people believe it is, for some reason).

/Jorgen

 

[James Kanze]

It's real C++. You have no need to define any classes, so you
don't. Same with many other language features.

I would skip the std::endl here though, and use "...---\n" instead.

Sounds like premature optimization to me.

std::endl is not "the thing you should use instead of '\n'"
(although many people believe it is, for some reason).

Just the opposite. Most of the time, std::endl is preferable.
With '\n', you never know when your data is going to end up on
disk.

 

[Jorgen Grahn]

Sounds like premature optimization to me.

No, it's more "do not do things without a reason" or "use the simplest
construct which does what I want".

Just the opposite. Most of the time, std::endl is preferable.
With '\n', you never know when your data is going to end up on
disk.

My reasoning is the opposite of yours. Most of the time I don't care
when the data hits disk[1], and I make this clearer by not using
std::endl.

(OK, I admit I also have this suspicion -- not confirmed by
experiments -- that std::endl means a large performance hit in some
situations. I don't want my Unix pipelines to run at half the speed
because there is extensive I/O flushing somewhere along the way.)

I thought everyone reasoned like that about endl, except newbies who
used it because they thought that '\n' was somehow a less portable way
of ending a line. But I know you as an experienced and careful C++
programmer, so I clearly have to revise that opinion ...

/Jorgen

[1] Or whatever endl guarantees on my system; I assume it will at
least leave the application.

 

[Hendrik Schober]

Sounds like premature optimization to me.

No, it's more "do not do things without a reason" or "use the simplest
construct which does what I want".

Just the opposite. Most of the time, std::endl is preferable.
With '\n', you never know when your data is going to end up on
disk.

My reasoning is the opposite of yours. Most of the time I don't care
when the data hits disk[1], and I make this clearer by not using
std::endl.

(OK, I admit I also have this suspicion -- not confirmed by
experiments -- that std::endl means a large performance hit in some
situations. I don't want my Unix pipelines to run at half the speed
because there is extensive I/O flushing somewhere along the way.)

I thought everyone reasoned like that about endl, except newbies who
used it because they thought that '\n' was somehow a less portable way
of ending a line. But I know you as an experienced and careful C++
programmer, so I clearly have to revise that opinion ...

For me it's very likely also the first time I disagree with James.
I have seen someone debugging and profiling an application for a
week to no avail, until he was told to replace 'std::endl' by '\n',
which made the code he was trying to speed up (which wrote big files)
ten times faster and ended all his performance woes.
I've been hammering "use '\n' unless you /want/ to flush" into quiet
a few generations of students since...

/Jorgen

[1] Or whatever endl guarantees on my system; I assume it will at
least leave the application.

Schobi

 

[James Kanze]

No, it's more "do not do things without a reason" or "use the
simplest construct which does what I want".

And what do you want? To write data to disk, or to create
confusion when your program crashes?

My reasoning is the opposite of yours. Most of the time I
don't care when the data hits disk[1], and I make this clearer
by not using std::endl.

If you don't care when it hits the disk, the fastest solution is
not to write it in the first place. It will never hit the
disk, but since you don't care when it hits the disk...

Most of the time, I find just the opposite to be the problem; I
can't acknowledge a request until I'll sure that the data has
been physically written to the disk. Which can't be achieved
with a filebuf, so I have to use system level I/O.

Flushing a stream doesn't cause data to "hit the disk", at least
not on the systems I use (Solaris, Linux). It's basically a
memcpy to system memory, no more, no less, with a couple of
updates to control variables.

(OK, I admit I also have this suspicion -- not confirmed by
experiments -- that std::endl means a large performance hit in
some situations. I don't want my Unix pipelines to run at
half the speed because there is extensive I/O flushing
somewhere along the way.)

If you're outputting to a pipe, you almost certainly want at
least line buffering. The other side can't read it until it's
gotten to the OS. (Strictly speaking, what you actually want is
that the other side will be able to read the data "promptly".
If you're outputting a lot of data in a tight loop, and you
actually see a slow down, you might want to consider moving the
flush out of the loop. But you definitely want a flush at the
end of any isolated write.)

[...]

[1] Or whatever endl guarantees on my system; I assume it will at
least leave the application.

endl guarantees a flush. A flush guarantees that the data will
be transmitted to the host environment. I don't know what that
really means under Windows, but under Unix, it only means a
memcpy, more or less, to the system buffer. It's not free
(there is a context switch), but it's not that expensive either.
If the writes were actually synchronized, and you had to wait
for the disk, it would be a different issue. Still a question
of optimization, in a way, but at least on the systems I work
on, a synchronized write takes around 10 ms.

 

[James Kanze]

For me it's very likely also the first time I disagree with
James. I have seen someone debugging and profiling an
application for a week to no avail, until he was told to
replace 'std::endl' by '\n', which made the code he was
trying to speed up (which wrote big files) ten times faster
and ended all his performance woes.

Which is stupid too. *IF* you have a performance problem, then
it should be an obvious consideration, along the lines of making
a function inline.

If you know what you're doing, I wouldn't even oppose using '\n'
from the start in a tight loop; although it is premature
optimization, there are worse things you can do. But for most
people, as long as there is no performance problem, std::endl is
the way to go.

I've been hammering "use '\n' unless you /want/ to flush"
into quiet a few generations of students since...

Since when? That sounds like the performance problem mentionned
above took place a long time ago. Which means that the
performance difference may have (probably has) become less.

 

[Hendrik Schober]

Which is stupid too. *IF* you have a performance problem, then
it should be an obvious consideration, along the lines of making
a function inline.

If you know what you're doing, I wouldn't even oppose using '\n'
from the start in a tight loop; although it is premature
optimization, there are worse things you can do. But for most
people, as long as there is no performance problem, std::endl is
the way to go.

It took him many hours, if not a day, to consider every
appearance of 'std::endl' and change thos that needed to.

To me, using 'std::endl' instead of '\n' is like converting
an 'int' to a 'double', multiplying by two, and convert it
back, when all you want to do is a left shift: It works,
most of the time (but not always ) it comes up with the same
result[1], and it certainly takes a lot longer to do so.

I am against premature optimization, too (who wouldn't be
against anything that carries the attribute "premature" in
its name?), but I'm also against doing A+B when what you
really want is A.

Since when? That sounds like the performance problem mentionned
above took place a long time ago. Which means that the
performance difference may have (probably has) become less.

The profiler war story took place about 5 to 10 years ago.
The problem was that the file format required line breaks
on average less than every 10th char. (Or did it only allow
line breaks, but he used this permission in order to make
the files more readable? I forgot.) The files, however,
sometimes where several hundred MB big, so he had dozens of
millions of flushes.
I had used the rule "use '\n', except when you want to flush"
for myself for quite a while already then, so when he asked
me to look at the code all those 'std::endl' immediately
caught my eye.

[1] Note that a sensibly performing program can be an expected
result, too.

Schobi