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

> Thorsten Froehlich <tho### [at] trfde> wrote:
> : Is this by any chance the only example you have? ;-)
>
>   Yes. And why not? I could write more similar examples, but what would
> be the point? I think one is enough.

I think this example is very abstract in what it does is a typical "demo
application", and the map data type is rather hard to understand without any
explanation. Some example showing a more "common" known data type like a
list and some string operations would probably be more impressive.


      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 <39bab7db@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   My strong reaction was to the negative attitude against the STL which 
> you showed (or at least I got that impression). Nothing personal :)

You mean what I was saying about using other languages? Sorry that it 
wasn't clear what I meant...at least I know not to take up writing as a 
profession. :-)

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

Thorsten Froehlich wrote:
> 
> In article <39baaf56@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:
> 
> >   Believe me, the error messages of gcc are MYSTICAL! :)
> >
> >   For example, can you say what causes this error message?
> >
> > request for member `clear' in `x', which is of non-aggregate type
> > `string ()()'
> 
> Hmm, this is a funny error message.  What is the cause? I am curious!
> 
	My bet is: forgotten parenthesis (ie: "x.clear;" instead of
"x.clear();")


-- 

* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde...                  * http://www.enst.fr/~jberger
*******************************

Post a reply to this message

Thorsten Froehlich wrote:
> 
>  lim   2n lg n   >   lim   2n + n lg n
> n->oo               n->oo
> 
> =>
> 
>  lim   n lg n  >   lim   2n
> n->oo             n->oo
> 
	This doesn't make any mathematical sense since all four limits are
infinity and therefore can't be compared. What can be said is that for a
big enough n, you have:
2n lg(n) > 2n + n lg(n)
and
n lg(n) > 2n

	Moreover your implication goes the wrong way (ie the second inequation
implies the first, not the other way round).

> In fact you are falling in the same trap I fell at first when replying to
> Ron:  Trying to compare these two functions based on big-O notation!  But
> you simply cannot compare two functions with the same big-O with each other
> using big-O.  Other methods are needed, i.e. limits will solve the problem
> for the worst case very well.
> 
	Limits won't solve the problem at all since they can't be compared.
OTOH you can probably get away with saying "for a big enough n..."

	I'm not trying to say that one is better than the other, I haven't
computed it and I don't intend to. I'm just pointing out that this
particular argument doesn't work (at least in the way it is presented).


-- 

* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde...                  * http://www.enst.fr/~jberger
*******************************

Post a reply to this message

Thorsten Froehlich wrote:
> 
> In article <39bab3c5@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:
> 
> > Thorsten Froehlich <tho### [at] trfde> wrote:
> > : 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))
> >
> >   By the way, you are wrong here.
> >
> >   It's true that retrieval is O(n*log(n)), but an operator++() of the
> > iterator is O(1), so the retrieval of the whole tree is O(n) in my case.
> 
> OK, so Stroustrup is wrong?
	I don't know what Stroustrup said, but according to the STL
documentation here: http://www.sgi.com/Technology/STL/trivial.html 

> The complexity of operations on trivial iterators is guaranteed to be amortized
constant time. 


-- 

* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde...                  * http://www.enst.fr/~jberger
*******************************

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
:> request for member `clear' in `x', which is of non-aggregate type
:> `string ()()'

: Hmm, this is a funny error message.  What is the cause? I am curious!

  This code causes it. Can you see what is the mistake?

#include <string>
using namespace std;

int main()
{
    string x();
    x.clear();
}


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

Thorsten Froehlich <tho### [at] trfde> wrote:
:>  And iterators are just brilliant.

: It is easy to make the wrong assumptions about them, i.e. how fast they
: really are for some data structures.  Nevertheless, they are really useful!

  It's the idea behind the iterators that make them so brilliant.

  They work like pointers (but are of course much safer). This means that
you can read the same data container from different places using different
iterators without them interfering each other.
  A mistake made often by people is to create a data container and then
add some methods like "getFirst()" and "getNext()". This has the serious
problem that you can't read the container from different places without
each of them interfering the others. But as iterators work like pointers,
they can be used independently.

  Also iterators are very independent of the data container they are
associated to. This means that you don't have worry how to get to the next
item; you just make a ++ and you are in the next item, no matter if the
container is a list, a vector, a tree or whatever.

  This means that general algorithms that work for most STL containers can
be made (and they have been made in the <algorithm> include file).
  For example if you want to sort your items you just call:

sort(myCont.begin(), myCont.end());

  It doesn't matter if myCont is a vector, a list, a deque or whatever (for
binary trees it makes no sense since they are already sorted; also the STL
list has an inner sort which is more efficient since it only changes
pointers and doesn't need to copy the items, but the above command should
work for lists as well).

  If you want to sort your container in reverse order, it's easy:

sort(myCont.rbegin(), myCont.rend());

  (Btw, the fact that rbegin() returns an iterator to the same item as end()
and that rend() returns an iterator to the same item as begin() is very
confusing until you understand how they really work.)

  Also copying data from one container to other is very easy. For example:

vector<int> myVector(myCont.begin(), myCont.end());

  It doesn't matter what myCont is, as long as its iterator supports
operator++().
  This last thing is specially useful in this case:

int main(int argc, char* argv[])
{ vector<string> CommandLine(argv, argv+argc);

  This is so because regular pointers work as iterators as well (not a
big surprise).

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

Thorsten Froehlich <tho### [at] trfde> wrote:
: Now set a breakpoint at i++  and step into the function.  Go down until you
: find a loop.   If you can't find a loop, I would really like to know which
: data structure your library uses to store maps (I assume it is a tree
: structure).

  It's true that the operator++ has to make several steps in some cases but
only when it has to go backwards in the tree. When going forward it has to
make just one step. It has to make log(n) steps backwards only once (when
going from the largest item which is smaller than the root item to the
root item). It has to make log(n)/2 steps two times. And so on.
  What is the amortized O()-time for ++ then?

  Btw, using some extra memory it could be possible to avoid all extra steps:
By putting a pointer to the next item in the walk in each item.

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

Warp wrote:
> 
>   This code causes it. Can you see what is the mistake?
> 
> #include <string>
> using namespace std;
> 
> int main()
> {
>     string x();
	This line doesn't define a variable of type string but a function with
no arguments that return a string and whose code is assumed to be given
elsewhere (except that I'm surprised that this works inside another
function, I would have understood better if "string x();" was before
"int main()").

>     x.clear();
	But this should work: "x().clear();" (assuming you've got the function
x defined elsewhere). Hey, I wasn't that far off! :))

> }
> 


-- 

* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde...                  * http://www.enst.fr/~jberger
*******************************

Post a reply to this message

<Jer### [at] enstfr>  wrote:

>  Moreover your implication goes the wrong way (ie the second inequation
> implies the first, not the other way round).

Hmm, maybe you are forgetting some fundamental things here...

2n lg n   >   2n + n lg n    |   : n lg n

=>

n lg n  >  lim   2n

because n lg n can never be 0 in this case (so the division is legal).  Of
course I am just silently dropping the + 1 here and some other changes to
the function because of the division.

>  This doesn't make any mathematical sense since all four limits are
> infinity and therefore can't be compared. What can be said is that for a
> big enough n, you have:
> 2n lg(n) > 2n + n lg(n)
> and
> n lg(n) > 2n

Nope, you can do the following (as what I am up to is not a result, but only
a relative comparison of the growth rate):

 lim   2n lg n   >   lim   2n + n lg n
n->oo               n->oo

<=>

 lim   2n lg n - 2n + n lg n  >  0
n->oo

<=>

 lim   n lg n - 2n  >  0
n->oo


       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