29 replies to this topic

[.oisyn]

While browsing through the archive of a particular website of which I'm not yet mentioning it's name (because the answer can be found there ), I stumbled on a nice C++ problem:

Is it possible to implement a function f() that returns a pointer to itself, such that the following program compiles and works as expected. And if so, how?

typedef FuncPtr /* the signature of f() */;

int main()
{
    FuncPtr fp1 = f();    // calls f()
    FuncPtr fp2 = fp1();  // also calls f()
    FuncPtr fp3 = fp2();  // guess what ;)
}

Of course, it has to be standard compliant and fully portable

[SigKILL]

Possibly cheesy, but in vs.net the following works

class dummy;

typedef dummy&(*FuncPtr)(void);


class dummy {

private:

	FuncPtr	m_ptr;

public:

	dummy( FuncPtr ptr ) {

		m_ptr = ptr;

	};


	operator FuncPtr() {

		return m_ptr;

	};

};


dummy	&f() {

	static dummy ret(f);

	std::cout << "Called f().\n";

	return ret;

};

If this is a valid solution you better come up with something harder the next time ;)

[.oisyn]

Yes, that was the answer I was looking for, although your solution isn't very thread-safe (then again, standard C++ says nothing about threads anyway) . You'd be surprised how many people would say it isn't possible as they're trying to define a recursive type of a pointer to [a function that returns a pointer to] ad infinitum

Why the refence and the local static?

[.oisyn]

This one is also nice:

What does the following program output, and why:

#include <iostream>

int main()
{
    int x = 0;
    for (int i = 0; i < 100; i++);
        // how many times will the following line be executed ?????/
        ++x;

    std::cout << x << std::endl;
}

[dave_]

.oisyn said:

You'd be surprised how many people would say it isn't possible as they're trying to define a recursive type of a pointer to [a function that returns a pointer to] ad infinitum ;)

That's because its a trick question, the trick being this:

.oisyn said:

returns a pointer to itself

The solution returns a functor.

Personally I'd just use boost::function

[dave_]

.oisyn said:

// how many times will the following line be executed ?????/

Is that supposed to be a continuation '\' at the end or is it a double bluff? (and i did notice the semicolon at the end of the for line)

[.oisyn]

dave_ said:

That's because its a trick question, the trick being this:

The solution returns a functor.

I meant the term 'pointer' in the broadest sense of the word. I consider a boost::shared_ptr a pointer as well.

Quote

Personally I'd just use boost::function

Which isn't going to help you here without using the same temporary object.

boost::function<boost::function<boost::function<... etc ...>()>()>()> f();

dave_ said:

Is that supposed to be a continuation '\' at the end or is it a double bluff? (and i did notice the semicolon at the end of the for line)

I made no mistakes in the code . You're on the right track, but you're probably missing something (the output is indeed '0').

[dave_]

Its some other sort of continuation, at least thats what my compiler tells me:

warning C4010: single-line comment contains line-continuation character

whats special about '??/' ?

.oisyn said:

boost::function<boost::function<boost::function<... etc ...>()>()>()> f();

oh yeh of course

[.oisyn]

dave_ said:

Its some other sort of continuation, at least thats what my compiler tells me:

Well, yes, that's the point. / is no continuation character, but \ is. However, ??/ is the trigraph sequence for \

[poita]

'??/' is a trigraph that becomes '\' which makes the '++x;' part of the comment.

In any case, the for loop is empty because it is ended with a ';'

[edit]

Too late! :P

[Reedbeta]

Astounding! I never realized these trigraph things existed before.

[SigKILL]

.oisyn said:

Why the refence and the local static?

Stupidity.

I thought it would be nice to look at the assembler output so we could see that the function actually returns a pointer to itself (all that dummy class stuff is just forcing C++ to do what you want). This is the optimized output of vs.net 2003 (btw. f() now returns dummy by value):

int main(int argc, char*argv[]) {

	FuncPtr fp1 = f();    // calls f()

00401020  mov         eax,dword ptr [__imp_std::cout (403024h)] 

00401025  sub         esp,8 

00401028  push        offset string "Called f().\n" (40314Ch) 

0040102D  push        eax  

0040102E  call        dword ptr [__imp_std::operator<< (403020h)] 

    FuncPtr fp2 = fp1();  // also calls f()

00401034  lea         ecx,[esp+8] 

00401038  push        ecx  

00401039  call        f (401000h) 

    FuncPtr fp3 = fp2();  // guess what ;)

0040103E  lea         edx,[esp+10h] 

00401042  push        edx  

00401043  call        dword ptr [eax] 

00401045  add         esp,10h 

	__asm int 3;

00401048  int         3    

	return 0;

00401049  xor         eax,eax 

};

If you know your assembler you'll see that f() returns a pointer to itself. However, the first call to f() is inlined, the second time it calls f() directly instead of through a pointer and the third time it calls f() through a pointer. I know why this happends, but it's also kind of funny.

If anyone asks why I'm having an "__asm int 3" in there: It's an habit from the old days when using a debugger that wouldn't break in release builds...

[roel]

Reedbeta said:

Astounding! I never realized these trigraph things existed before.

I second that. I love this thread :)

[.oisyn]

SigKILL said:

Stupidity.

I thought it would be nice to look at the assembler output so we could see that the function actually returns a pointer to itself (all that dummy class stuff is just forcing C++ to do what you want). This is the optimized output of vs.net 2003 (btw. f() now returns dummy by value):

[..snip..]
If you know your assembler you'll see that f() returns a pointer to itself. However, the first call to f() is inlined, the second time it calls f() directly instead of through a pointer and the third time it calls f() through a pointer. I know why this happends, but it's also kind of funny.

Can you post the assembly code for f()? I wonder why it pushes a parameter on the stack before calling f() or the function pointer. The parameter that is passed seems to be the address of a local variable. Maybe f() uses it to store the function return value in, which is the dummy object, but eax is also used so I don't understand why the compiler does that.

[.oisyn]

Another one: What should this program output? (not all compilers get this correct)

[code=c++]#include <iostream>

struct A
{
operator int() { return 0; }
};

void foo(int)
{
std::cout << "foo(int)" << std::endl;
}

template<class T> void bar(T t)
{
foo(t);
}

void foo(char)
{
std::cout << "foo(char)" << std::endl;
}

void foo(A)
{
std::cout << "foo(A)" << std::endl;
}

int main()
{
bar('3');
bar(3);
bar(A());
}[/code]

[dave_]

A guess, seems obvious, is it: char, int A?


I dont know is the last one supposed to be a trick? A()() would give an int...

[Kenneth Gorking]

A()() would give an error...

My guess would be int, int, int, since foo(char) and foo(A) is declared after bar().

[.oisyn]

The answer is:

foo(int)
foo(int)
foo(A)

For non-dependent names in templates, name lookup is done at point of definition. For dependent-names, however, ADL (Argument Dependent Lookup) is also performed at point of instantiation, next to the normal lookup. Since foo is called with a template argument, it is a dependent name.

For bar<char>, foo is lookup at definition time and ::foo(int) is found, and the namespace associated with char is also searched at point of instantiation (in main()). However, char has no associated namespace and so foo(int) is called. Likewise for bar<int>. For bar<A>, the namespace associated with A is again searched at point of instantiation, which is the global namespace, which contains foo(A).

A::operator int() is not used in this example and was purely meant to put you on the wrong foot

VC++ has this incorrect and only looks up at point of instantiation time (which is documented in the MSDN as non-standard behaviour)

[SmokingRope]

Although char doesn't have an associated namespace, is there some way to associate it with one, i.e.

typedef char myChar;
void foo(myChar){};
// or 
namespace MyNamespace
{
  typedef char myNamespaceChar;
  void foo(myNamespaceChar){};
}

void main()
{
  bar(myChar('3'));
  bar(myNamespace::myNamespaceChar('3'));
}

[.oisyn]

No, myChar and myNamespace::myNamespaceChar are simply aliases for char. There is no difference between bar<char> and bar<myChar>