Nice C++ riddle/problem

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 May 30, 2007 at 11:42

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

29 Replies

Please log in or register to post a reply.

4e70f904a74bd2aa8773733b25b77d41
0
SigKILL 101 May 30, 2007 at 13:34

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

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 May 30, 2007 at 14:10

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?

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 May 30, 2007 at 14:19

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;
}
A9102969e779768e6f0b8cb87e864c94
0
dave_ 101 May 30, 2007 at 14:27

@.oisyn

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

returns a pointer to itself

The solution returns a functor.

Personally I’d just use boost::function

A9102969e779768e6f0b8cb87e864c94
0
dave_ 101 May 30, 2007 at 14:30

@.oisyn

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

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 May 30, 2007 at 14:50

@dave_

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.

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_

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

A9102969e779768e6f0b8cb87e864c94
0
dave_ 101 May 30, 2007 at 16:23

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

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

oh yeh of course

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 May 30, 2007 at 16:35

@dave_

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 \

36b416ed76cbaff49c8f6b7511458883
0
poita 101 May 30, 2007 at 16:38

’??/’ 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

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 May 31, 2007 at 06:28

Astounding! I never realized these trigraph things existed before.

4e70f904a74bd2aa8773733b25b77d41
0
SigKILL 101 May 31, 2007 at 12:20

@.oisyn

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…

6aa952514ff4e5439df1e9e6d337b864
0
roel 101 May 31, 2007 at 19:39

@Reedbeta

Astounding! I never realized these trigraph things existed before.

I second that. I love this thread :)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 01, 2007 at 09:35

@SigKILL

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.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 01, 2007 at 10:26

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

#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());
}
A9102969e779768e6f0b8cb87e864c94
0
dave_ 101 Jun 01, 2007 at 14:22

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…

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Jun 01, 2007 at 15:21

A()() would give an error…

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

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 01, 2007 at 21:20

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

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

860fe478a2545d6c07b88c759292499e
0
SmokingRope 101 Jun 04, 2007 at 10:40

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'));
}
340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 04, 2007 at 13:24

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

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 06, 2007 at 11:33

Let’s continue :P

#include <iostream>

namespace A
{
    const char str[] = "A::str";
}

namespace B
{
    const char str[] = "B::str";

    void foo1()
    {
        using namespace A;
        std::cout << str << std::endl;
    }

    void foo2()
    {
        using A::str;
        std::cout << str << std::endl;
    }
}

int main()
{
    B::foo1();
    B::foo2();
}

What does this output, and why?

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Jun 06, 2007 at 17:17

It outputs B::str then A::str.

My guess at why would be because “using namespace” simply adds the members of the namespace to the lookup list but gives them lowest precedence when choosing from name conflicts. With “using A::str” the compiler treats A::str as if it were a local variable so it has precedence over the B::str.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 06, 2007 at 20:12

My guess at why would be because “using namespace” simply adds the members of the namespace to the lookup list but gives them lowest precedence when choosing from name conflicts

Not entirely true

namespace A
{
    static const char str[] = "A::str";

    namespace B
    {
         static const char str[] = "A::B::str";
    }

    void foo1()
    {
        using namespace B;
        std::cout << str << std::endl;  // error, str is ambiguous
    }

    namespace C
    {
        namespace D
        {
            const char str[] = "A::C::D::str";
        }

        void foo2()
        {
            using namespace D;
            std::cout << str << std::endl; // uses A::C::D::str
        }
    }
}

Indeed for a using declaration (“using A::str;”), it introduces the name in the current scope. For using directives (“using namespace A;”) however, the name is introduced in the nearest enclosing namespace that contains both the current scope and the referred namespace.

In the first example, in B::foo1(), B::str has priority over A::str because the nearest enclosing namespace containing both B::foo1 and A is the global namespace, so B::str hides A::str.

In the example above, in A::B::foo1(), the nearest enclosing namespace containing A::B and A::foo1() is A. However, A itself also has a str, so A::str and A::B::str are on the same level within the context of foo1() and ‘str’ is therefore ambiguous.
In A::C::foo2(), the nearest enclosing scope containing A::C::D and A::C::foo2() is A::C. Therefore A::C::D::str hides the definition of A::str within the context of foo2()

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Jun 07, 2007 at 10:54

:S

Interesting stuff!

Any more? :)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 07, 2007 at 23:50

I’m running out of ideas :P

#include <iostream>

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

namespace A
{
    struct AStruct { operator int() { return 0; } };
    void bar(AStruct) { std::cout << "A::bar()" << std::endl; }

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

namespace B
{
    struct BStruct { operator int() { return 0; } };
    void bar(BStruct) { std::cout << "B::bar()" << std::endl; }
}

int main()
{
    A::AStruct a;
    B::BStruct b;
    A::foo(a);
    A::foo(B);
}
Cfaa1d0c20618d4ea3d06aee59b51d91
0
chombik 101 Jun 17, 2007 at 23:13

C++ 3.11
How to increase an output scrolling to see all the print out?
I know this is not a nice C++ problem, but no one replied so far anywhere.
Please, help.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 18, 2007 at 00:15

C++ has no version, and C++ does not know the concept of a “screen”. Your question has nothing to do with C++. Open a different topic for your question, and state your platform (linux, windows, etc.)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jul 04, 2007 at 11:35

@.oisyn

I’m running out of ideas ;)

#include <iostream>

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

namespace A
{
    struct AStruct { operator int() { return 0; } };
    void bar(AStruct) { std::cout << "A::bar()" << std::endl; }

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

namespace B
{
    struct BStruct { operator int() { return 0; } };
    void bar(BStruct) { std::cout << "B::bar()" << std::endl; }
}

int main()
{
    A::AStruct a;
    B::BStruct b;
    A::foo(a);
    A::foo(:);
}

Nobody has an answer?

Any way, here’s another one:
how many consecutive characters (without spaces etc) of the following symbols can you use in a valid C++ program?
a) ‘+’
:) ‘&’
c) ‘<’ d) ‘?’

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jul 04, 2007 at 16:48

I’ll assume excluding comments, since you can repeat as many of any of those symbols as you like in a comment. ;)

(a) unlimited (c++; c++++; c++++++; …)
(:) 3: if (foo &&&bar)
(c) 3: I’m not sure if this is legal…

struct foo {};
template <typename T>
operator << (const foo& lhs, T rhs);
// ...
foo a;
operator <<<int> (a, 0);

(d) 3:

a ???/
b : c;

where ??/ is the trigraph for \, here acting as an escaped newline in the middle of the conditional-expression.

So how’d I do? :)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jul 04, 2007 at 21:14

B) and c) are wrong, but for c) you’re in the right direction, and for a) you’re only including an even number of characters in your example ;)

a) unlimited: +c, ++c, +++c, ++++c, etc.
You’ll need to at least overload the unary + to return an l-value for an uneven number. Another solution is to overload the postfix ++ to return l-value, so you can finish it with the binary + for an uneven number: c+++++d

B) 5: &MyStruct::operator&&&&&a, which is parsed as: &SomeStruct::operator&& && &someVar
So you’re and’ing a pointer-to-member-function with another pointer

c) 4: &MyStruct::operator<<<<someVar
You’ll need to overload the global << operator to be able to ‘shift’ a pointer-to-member-function with a user defined type :)

For d) I was indeed looking for the trigraph sequences :)