Asp Forum - sorting the input

arnuld

9/10/2008 12:06:00 PM

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

16 Answers

???

9/10/2008 1:13:00 PM

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

9/10/2008 4:29:00 PM

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

9/10/2008 4:32:00 PM

On Sep 10, 5:06 am, 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++.
>
> /* 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

9/10/2008 4:38:00 PM

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

9/10/2008 4:46:00 PM

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

9/10/2008 4:50:00 PM

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

9/11/2008 4:22:00 AM

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

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

???

9/11/2008 5:05:00 AM

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

9/11/2008 4:57:00 PM

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

9/19/2008 10:56:00 AM

On Wed, 10 Sep 2008 17:06:16 +0500, arnuld <sunrise@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!

comp.lang.c++

sorting the input

arnuld

???

James Kanze

red floyd

Kai-Uwe Bux

Erik Wikström

Erik Wikström

arnuld

???

Erik Wikström

Jorgen Grahn

x Login to ForumsZone