In article <39b80909$1@news.povray.org>, "Thorsten Froehlich" 
<tho### [at] trfde> wrote:

> > Thanks, I will put these on my list of books to get.
> 
> See it this way:  If you plan to major in CS (if you do?)

I do(though I have not decided the exact areas)...


> you will have to get most of them sooner or later anyway ;-)

 ...and I know I will. :-)
Especially graphics and algorithms books, all I have are "introduction 
to C/C++/Java" books and one good C++ intro/reference book(C++ Primer 
Plus, which does cover the STL, just in a somewhat incomprehensible way 
for someone who doesn't already use it).
Hmm, maybe I can get my parents to pay for them...probably not.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Thanks, I will take a look at these sites.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
: Why would I use code from someone else for something as simple as a 
: linked list or tree?

  A list is rather simple, but it's not unusual at all that you make mistakes
easily (memory leaks, reading freed memory...).
  A weighted binary tree IS NOT easy at all to do. You have to code quite a
lot to get one done. Why should I do it when it's already done. And done well.

  I always like to show in these cases this example I made:

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{ typedef map<string,unsigned> wlist_t;
  wlist_t words;
  string word;
  while(cin) { cin >> word; words[word]++; }
  for(wlist_t::iterator i=words.begin(); i!=words.end(); i++)
    cout << i->first << ": " << i->second << endl;
}


  It reads words from the standard input (a word is limited by whitespaces)
and then outputs an alphabetically ordered list of the words and a number
indicating the amount of times the word appears in the text.

  Try to make that without using any STL. It must be at least as fast as
this one.
  How many code lines do you need? How much time do you need to make it?

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

In article <39b8cf06$1@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   A list is rather simple, but it's not unusual at all that you make 
> mistakes easily (memory leaks, reading freed memory...).

My first version of the new glow patch being an embarassing example of 
this...


>   A weighted binary tree IS NOT easy at all to do. You have to code quite 
> a lot to get one done. Why should I do it when it's already done. And 
> done well.

Because I want to know how to do it? And because I don't want to be 
separated from what my program is doing? And because when I was *trying* 
to learn the STL, I often got errors and couldn't figure out why?

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
:>   A weighted binary tree IS NOT easy at all to do. You have to code quite 
:> a lot to get one done. Why should I do it when it's already done. And 
:> done well.

: Because I want to know how to do it?

  So instead of spending 1/2 hour once to learn how to use the STL you
spend 2 hours every time you want to use a weighted binary tree?

: And because I don't want to be 
: separated from what my program is doing?

  Sorry, I didn't understand at all what are you talking about here.

: And because when I was *trying* 
: to learn the STL, I often got errors and couldn't figure out why?

  Get a proper compiler and try again. You can get one by free.

  And read documentation and tutorials.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

In article <chrishuff-078CCD.07512408092000@news.povray.org> , Chris Huff 
<chr### [at] maccom>  wrote:

>>   A weighted binary tree IS NOT easy at all to do. You have to code quite
>> a lot to get one done. Why should I do it when it's already done. And
>> done well.
>
> Because I want to know how to do it? And because I don't want to be
> separated from what my program is doing?

Hmm, sounds like reinventing the wheel to me ;-)

The thing is once you have done it two or three times it gets really boring
writing the same code over and over again and it distracts from the fun part
of programming and especially it distracts from the actual problem you want
to solve.

I think all data structures the STL provides are listed in yet another set
of classic books "Introduction to Algorithms" for the more practical
information should cover them, and the books by Knuth, especially "The Art
of Computer Programming" without question include all of algorithms used in
the STL in a very detailed and abstract manner (NOTE: Neither of these books
has anything to do with the actual STL, they are pure computer science
books).  Actually, most STLs likely use suggested implementations you find
in one of his books :-)


       Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <39b9050f@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> : And because when I was *trying*
> : to learn the STL, I often got errors and couldn't figure out why?
>
>   Get a proper compiler and try again. You can get one by free.

Actually, CodeWarrior is a good (not perfect) compiler with a really good
and ISO C++ standard compliant _library_.  The only not supported ISO C++
language feature (and thus it is not fully compliant to the ISO C++
standard...) is the "export" keyword for templates (section 14, paragraph
6), but I know only very few compilers that support it (if you know one for
IRIX or Mac OS, I am interested!).

The library itself passes all special cases listed in the ISO C++ standard
as well as the ones in The C++ Prog. Lang. 3rd Ed, Appendix B (I tried those
myself).  CodeWarrior is also supposed to (I never checked) support the
minimum limits listed in Annex B of the ISO C++ standard.

As for the STL, being compliant causes a lot of problems with other
compilers.  Take a look at gcc and the iostreams it comes with.  They are so
far behind the standard, you need to make fixes all over the place to get it
to work cross-platform.

>   And read documentation and tutorials.

Now, when you buy a book that covers STL, you have one of two problems:
Either it doesn't cover the ISO C++ STL or it does and you can't use it with
a lot of compilers (Visual C 5.0 also had a lot of problems, 6.0 seems to be
better, gcc is still a mess).

This example does apply when trying to compile CodeWarrior code with Visual
C++ 5.0 (it happened to me!!!):
If you get an error message you end up having to analyse error messages and
try to figure out what is wrong.  Sometimes these error messages can be
impossible to understand when you assume you have a compliant library.  My
mistake was to use a "getchar" member function in one class.  Too bad, some
compiler libraries have not been updated to the ISO C++ standard (which
requires this to be a function!) and it is still a macro.  Now, your
compiler will always tell you something about an illegal class declaration,
but everything looks OK!!!

Now, this isn't even an example with an STL problem and it can still be hard
to understand the problem.  Try making a simple mistake just like declaring
a nested template with '>>' at the end.  How useful is the error message you
get from _your_ compiler?


     Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <39b8cf06$1@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>   I always like to show in these cases this example I made:
>
> #include <iostream>
> #include <map>
> #include <string>
> using namespace std;
> int main()
> { typedef map<string,unsigned> wlist_t;
>   wlist_t words;
>   string word;
>   while(cin) { cin >> word; words[word]++; }
>   for(wlist_t::iterator i=words.begin(); i!=words.end(); i++)
>     cout << i->first << ": " << i->second << endl;
> }

Is this by any chance the only example you have? ;-)


      Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <39b8cf06$1@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> #include <iostream>
> #include <map>
> #include <string>
> using namespace std;
> int main()
> { typedef map<string,unsigned> wlist_t;
>   wlist_t words;
>   string word;
>   while(cin) { cin >> word; words[word]++; }
>   for(wlist_t::iterator i=words.begin(); i!=words.end(); i++)
>     cout << i->first << ": " << i->second << endl;
> }

The return is missing...

>
>   It reads words from the standard input (a word is limited by whitespaces)
> and then outputs an alphabetically ordered list of the words and a number
> indicating the amount of times the word appears in the text.
>
>   Try to make that without using any STL. It must be at least as fast as
> this one.
>   How many code lines do you need? How much time do you need to make it?

Hmm, lets see, you need (runtimes from the C++ Prog. Lang 3rd Ed. page
464)...

For inserting:       O(n * log(n))
For retrieval:       O(n * log(n))
Total:               O(n * log(n) + n * log(n))


I can get:

For inserting:       O(n)
For sorting *:       O(n * log(n))
For retrieval:       O(n)
Total:               O(2 * n + n * log(n))

* No fancy algorithm, just quicksort.


How?  That is simple:  I read in the words. Then sort them and then just
count when retrieving.

Of course I can do this using the STL (see below)!  But your example shows
something dangerous you forgot:  the STL can trick you into thinking you
have found a good algorithm, but in fact yours is nearly log(n) times slower
than mine for most cases (for log(n) > 2)!

The condensed version (readable version at the end):

#include <iostream>
#include <list>
#include <string>
using namespace std;
void main() {
    typedef list<string> wlist_t;
    wlist_t words;
    string word;
    while(cin) { cin >> word; words.push_back(word); }
    words.sort();
    for(wlist_t::iterator i = words.begin(); i != words.end();) {
        wlist_t::iterator temp = i; int cnt = 0;
        for(; i != words.end(); i++, cnt++) if(*i != *temp) break;
        cout << *temp << ": " << cnt << endl;
}   }


Note that I can also provide a standard C only version which is less than
twice the length, supports dynamic string length and should be slightly
faster that this version by using some tricks.


      Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org




The more readable version of my program:


#include <iostream>
#include <list>
#include <string>

using namespace std;

void main()
{
    typedef list<string> wlist_t;
    wlist_t words;
    string word;

    while(cin)
    {
        cin >> word;
        words.push_back(word);
    }

    words.sort();

    for(wlist_t::iterator i = words.begin(); i != words.end();)
    {
        wlist_t::iterator temp = i;
        int cnt = 0;

        for(; i != words.end(); i++, cnt++)
        {
         if(*i != *temp)
          break;
        }
        cout << *temp << ": " << cnt << endl;
    }
}

Post a reply to this message

Yo, Chris,  when can we expect the fixed version of the +.3?  The memory
leak has sorta crippled my IRTC anim...  
Oops.
:)

H.E. Day

Post a reply to this message