sorting the input

0 views
Skip to first unread message

arnuld

unread,
Sep 10, 2008, 8:06:16 AM9/10/08
to
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;
}
}


--
www.lispmachine.wordpress.com
my email is @ the above blog.
Google Groups is Blocked. Reason: Excessive Spamming

书呆彭

unread,
Sep 10, 2008, 9:13:13 AM9/10/08
to
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>::push_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

unread,
Sep 10, 2008, 12:29:16 PM9/10/08
to
On Sep 10, 3:13 pm, ??? <lostgold...@163.com> wrote:
> 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.

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

> > 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.

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.

> 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>::push_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<>::push_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.

--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

red floyd

unread,
Sep 10, 2008, 12:31:36 PM9/10/08
to

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

Kai-Uwe Bux

unread,
Sep 10, 2008, 12:37:45 PM9/10/08
to
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

unread,
Sep 10, 2008, 12:45:38 PM9/10/08
to
On 2008-09-10 15:13, 书呆彭 wrote:
> 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,

Yes, but you can use std::list<T>::sort() to get better performance.

> but, the std::vector<typename T>::push_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

Erik Wikström

unread,
Sep 10, 2008, 12:49:56 PM9/10/08
to
On 2008-09-10 14:06, arnuld wrote:
> 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.

--
Erik Wikström

arnuld

unread,
Sep 11, 2008, 12:21:54 AM9/11/08
to
> On Wed, 10 Sep 2008 16:49:56 +0000, Erik Wikström wrote:

>> arnuld wrote:
>> 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.

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++.



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

> 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.

书呆彭

unread,
Sep 11, 2008, 1:04:47 AM9/11/08
to
James Kanze 写道:

> On Sep 10, 3:13 pm, ??? <lostgold...@163.com> wrote:
>> 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.
>
> It might be better to worry about whether the code works or not.
>
>>> 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.
>
> 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.

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

> 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.

>> but, the std::vector<typename T>::push_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<>::push_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

unread,
Sep 11, 2008, 12:57:08 PM9/11/08
to
On 2008-09-11 06:21, arnuld wrote:
>> On Wed, 10 Sep 2008 16:49:56 +0000, Erik Wikström wrote:
>
>>> arnuld wrote:

>>> std::vector<std::string> svec;
>>> std::vector<std::string>& r_svec = svec;
>
>> 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.

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

--
Erik Wikström

Jorgen Grahn

unread,
Sep 19, 2008, 6:55:47 AM9/19/08
to
On Wed, 10 Sep 2008 17:06:16 +0500, arnuld <sun...@invalid.address> wrote:
> 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

--
// Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
\X/ snipabacken.se> R'lyeh wgah'nagl fhtagn!

James Kanze

unread,
Sep 19, 2008, 4:30:52 PM9/19/08
to
On Sep 19, 12:55 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:

> On Wed, 10 Sep 2008 17:06:16 +0500, arnuld <sunr...@invalid.address> wrote:
> > 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.

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

unread,
Sep 24, 2008, 6:31:23 AM9/24/08
to
On Fri, 19 Sep 2008 13:30:52 -0700 (PDT), James Kanze <james...@gmail.com> wrote:
> On Sep 19, 12:55 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
>> On Wed, 10 Sep 2008 17:06:16 +0500, arnuld <sunr...@invalid.address> wrote:
...

>> > std::cout << "--------------------------------"
>> > << std::endl;
>
>> I would skip the std::endl here though, and use "...---\n" instead.
>
> 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".

>> 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.

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

unread,
Sep 24, 2008, 10:10:09 AM9/24/08
to
Jorgen Grahn wrote:
> On Fri, 19 Sep 2008 13:30:52 -0700 (PDT), James Kanze <james...@gmail.com> wrote:
>> On Sep 19, 12:55 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
>>> On Wed, 10 Sep 2008 17:06:16 +0500, arnuld <sunr...@invalid.address> wrote:
> ....

>>>> std::cout << "--------------------------------"
>>>> << std::endl;
>>> I would skip the std::endl here though, and use "...---\n" instead.
>> 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".
>
>>> 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.
>
> 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

unread,
Sep 24, 2008, 11:26:25 AM9/24/08
to
On Sep 24, 12:31 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
> On Fri, 19 Sep 2008 13:30:52 -0700 (PDT), James Kanze
> <james.ka...@gmail.com> wrote:
> > On Sep 19, 12:55 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
> >> On Wed, 10 Sep 2008 17:06:16 +0500, arnuld <sunr...@invalid.address> wrote:
> ...
> >> > std::cout << "--------------------------------"
> >> > << std::endl;

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

> > 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".

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

> >> 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.

> 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

unread,
Sep 25, 2008, 4:25:12 AM9/25/08
to
On Sep 24, 4:10 pm, Hendrik Schober <spamt...@gmx.de> wrote:
> Jorgen Grahn wrote:
> > On Fri, 19 Sep 2008 13:30:52 -0700 (PDT), James Kanze <james.ka...@gmail.com> wrote:
> >> On Sep 19, 12:55 pm, Jorgen Grahn
> >> <grahn+n...@snipabacken.se> wrote:
> >>> On Wed, 10 Sep 2008 17:06:16 +0500, arnuld
> >>> <sunr...@invalid.address> wrote:
> > ....

> 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

unread,
Sep 25, 2008, 12:44:50 PM9/25/08
to
James Kanze wrote:
> On Sep 24, 4:10 pm, Hendrik Schober <spamt...@gmx.de> wrote:
>> Jorgen Grahn wrote:
>>> On Fri, 19 Sep 2008 13:30:52 -0700 (PDT), James Kanze <james.ka...@gmail.com> wrote:
>>>> On Sep 19, 12:55 pm, Jorgen Grahn
>>>> <grahn+n...@snipabacken.se> wrote:
>>>>> On Wed, 10 Sep 2008 17:06:16 +0500, arnuld
>>>>> <sunr...@invalid.address> wrote:
>>> ....
>
>> 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.

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.

>> 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.

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

Reply all
Reply to author
Forward
0 new messages