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

>   This code causes it. Can you see what is the mistake?
>
> #include <string>
> using namespace std;
>
> int main()
> {
>     string x();
>     x.clear();
> }

Oh yes, that is one of the classics that don't give any useful compiler
error message.  At least now I know what it looks like in gcc, neither
Visual C++ nor CodeWarrior give a better error message  <sigh>


     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

Thorsten Froehlich wrote:
> 

> <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.
> 
	All right, then how do you justify the first inequation? The valid
demonstration is:
lg(n) > 2 (for n > 3) | * n
=>
n lg(n) > 2n          | + n lg(n)
=>
2n lg(n) > 2n + n lg(n)

> >  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
> 
> ...
	I wasn't really speaking about the reasoning. My point is that you
can't compare two infinite limits. The valid reasoning is to say that
for n big enough (in this case "big enough" means greater than 3) you
have those equations (without the limits). Or else redefine clearly what
you mean by:
 lim ...
n->oo
since you're not using the standard definition.
	Again it's more a complaint about the form of your reasoning (which is
wrong) than with the content (which for this part is right, I haven't
looked into the rest so I can't speak about the whole)


-- 

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

Post a reply to this message

On Sat, 09 Sep 2000 18:46:59 -0500, Thorsten Froehlich wrote:
>In article <39bab424@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:
>
>> : No, it is a clear which one is faster, just my notation for the total was
>> : incorrect:  See my later posts explaining it in more detail.
>>
>>   You had another mistake (which I mentioned in another response).
>>
>>   The total retrieval time in my case is O(n), not O(n*log(n)).
>
>No, it is O(log(n)) for each ++ operator, see my other post!

This depends on implementation.  My favorite map (the one I use here) is
O(1) for each ++ operator, at the expense of a bit more bookkeeping at
insertion and deletion time.  The bookkeeping is also O(1), though, so
it's dwarfed by the O(log n) the insert or delete already takes.

Whether implementation is prescribed by STL is something I don't know; I
haven't bothered to learn about STL yet as the compiler I'm forced to use
doesn't implement it (MSVC 1.52, the last 16-bit compiler MS made.  Low-level
programming on Win9x is pretty much required to be 16-bit.)

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

On 11 Sep 2000 09:40:08 -0400, Warp wrote:
>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?

amortized time is still O(log(n)) in that case, unless I missed something.

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

This is precisely what my implementation does.  The only thing I find lacking
in my implementation is the interface; the iterator is not separate and the
usage is confusing at best.  Neither of those two flaws are my doing, however;
I was writing a more robust and efficient implementation of a class that was
designed by a drooling moron on crack (spelled consultant) before I started 
here.  The exact depth of the consultant's stupidity is unplumbed, but suffice
to say that they thought the best implementation was an unsorted array, with
O(1) insertion, O(n) deletion, and O(n) lookup per element.  When this proved
to be too slow for the purpose, they "fixed" the problem by adding a cache to 
keep the five (no, the cache size was not configurable) most recent results.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

On 11 Sep 2000 16:39:05 -0400, Ron Parker wrote:
>On 11 Sep 2000 09:40:08 -0400, Warp wrote:
>>  What is the amortized O()-time for ++ then?
>
>amortized time is still O(log(n)) in that case, unless I missed something.

You are missing something: The iterator doesn't have to start at the
root of the tree (assuming the map is implemented as a tree)
to find the next item, so the the search time is generally much
faster than log(n).

In fact, for a splay tree, it only has to follow one pointer.

For a binary tree where each node has a pointer to its parent, it is
a bit more complicated: In 50% of the cases, the current node will be
the left leaf, so two pointer operations (up, right down) are needed.
In 25 % it is the right leaf of a node on the left of its parent, so 4
operations (up, up, right, left) are needed, etc:

1/2 *2 + 1/4 * 4 + 1/8 * 6 + 1/16 * 8 ...

works out to exactly 4, which is also O(1).

Oops, I just noticed that only my leave nodes have data, but I'm too
lazy to calculate this now for a normal binary tree, and it should even
be better, anyway.

Note that a binary tree without "up" pointers doesn't have any way
to get from one node to the next, so the iterator will have to do
additional bookkeeping in this case.

	hp

-- 
   _  | Peter J. Holzer    | Nicht an Tueren mangelt es,
|_|_) | Sysadmin WSR       | sondern an der Einrichtung (aka Content).
| |   | hjp### [at] wsracat      |    -- Ale### [at] univieacat
__/   | http://www.hjp.at/ |       zum Thema Portale in at.linux

Post a reply to this message

: (except that I'm surprised that this works inside another
: function

  The C standard says that a function definition can be done inside another
function. If done so, the scope of that function definition is only inside
that other function (it has a clear modular reason).
  Thus, the C++ standard supports it as well.

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

> : (except that I'm surprised that this works inside another
> : function
> 
>   The C standard says that a function definition can be done inside another
> function. If done so, the scope of that function definition is only inside
> that other function (it has a clear modular reason).
>   Thus, the C++ standard supports it as well.
> 
	One of the big differences between C and Pascal is precisely that the
Pascal standard allows definitions of function inside another while the
C standard doesn't (or so I always thought). Something to do with the
ability to return a function as the result of a function call. I don't
know the exact position of C++ in this respect but I assumed it followed
the C standard.


-- 

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

Post a reply to this message

On 12 Sep 2000 05:17:32 -0400, Warp wrote:

>: (except that I'm surprised that this works inside another
>: function
>
>  The C standard says that a function definition can be done inside another
>function. If done so, the scope of that function definition is only inside
>that other function

No, only function *declarations* inside other functions are permitted,
but not function *definitions*.

Thus:

    int main(void) {
	extern void foo(void);

	void();
	return 0;
    }

is allowed, but:


    int main(void) {
	void foo(void) {
	    printf("hello\n");
	}

	void();
	return 0;
    }

is not.

>(it has a clear modular reason).

There is a good technical reason why it is not allowed. It makes
function pointers very difficult to implement and unintuitive to use. 

Nevertheless, gcc implements it as an extension.

	hp

-- 
   _  | Peter J. Holzer    | Nicht an Tueren mangelt es,
|_|_) | Sysadmin WSR       | sondern an der Einrichtung (aka Content).
| |   | hjp### [at] wsracat      |    -- Ale### [at] univieacat
__/   | http://www.hjp.at/ |       zum Thema Portale in at.linux

Post a reply to this message

Peter J. Holzer <hjp### [at] sikituwsracat> wrote:
: No, only function *declarations* inside other functions are permitted,
: but not function *definitions*.

  I meant what you are saying, ie. declaration. I know that you can't put
the body of the function inside another function.
  I really don't know the difference between the words "declaration" and
"definition".
  Usually when I have to refer to the body of the function I use
the word "implementation". It may be wrong, though.

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

On 15 Sep 2000 02:46:13 -0400, Warp wrote:
>Peter J. Holzer <hjp### [at] sikituwsracat> wrote:
>: No, only function *declarations* inside other functions are permitted,
>: but not function *definitions*.
>
>  I meant what you are saying, ie. declaration. I know that you can't put
>  the body of the function inside another function.
>  I really don't know the difference between the words "declaration" and
>  "definition".

In C, a declaration tells the compiler what a "thing" (an object[1] or a
function) looks like, while a definition creates it. Every definition
is also a declaration, but not vice versa.

>  Usually when I have to refer to the body of the function I use
>the word "implementation". It may be wrong, though.

No it isn't wrong. It just isn't the word used when one talks about the
C programming language. Modula-2 for example has "definition modules"
and "implementation modules". Obviously when someone talks about a
"definition" in a modula program, he means something else than someone
talking about a "definition" in a C program.

Unfortunately, often a single word is used for different concepts, and
different words are used for the same concepts. What is meant has to be
guessed from context.

	hp

[1] Just as another example: An "object" in C is just a place to store
values (either a variable or a malloced area). It has nothing to do with
object-oriented programming.


-- 
   _  | Peter J. Holzer    | access ist als datenbankserver fraglos noch
|_|_) | Sysadmin WSR       | ungeeigneter als beispielsweise EDIT.COM,
| |   | hjp### [at] wsracat      | und das primaer aufgrund der erzeugung
__/   | http://www.hjp.at/ | falscher erwartungshaltungen. frank paulsen

Post a reply to this message