JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
A challenge problem | Reply
Here's a challenge problem to see how well you understand C++. It was something that we found it necessary to develop at a company I did some work for, where performance was critical.

You have a class Base and several subclasses, one of them called Derived. Base and Derived both have a virtual method e.g.
// header file
struct Base
{
    virtual void foo();
    virtual ~Base() {}
};
 
struct Derived : public Base
{
    virtual void foo();
};
 
// .cpp file
void Base::foo() { cout << "Base::foo\n"; }
void Derived::foo() { cout << "Derived::foo\n"; }

One of the limitations of C++ virtual functions is that even if you know that Derived will never be subclassed, the following code will always go through the late binding mechanism:
Derived *derived = new Derived;
derived->foo();

Your task is to modify the classes so that

  1. The code above is as efficient as if the method were not virtual (i.e. just a method call with no vtable lookup).

  2. Code that calls base->foo() (where base is a Base *) is just as efficient as currently and handles polymorphism correctly.

  3. There is no duplication of code, either at the source level or of generated code due to tricks with templates, macros etc.


To be fair, these are implementation details which the C++ standard doesn't address, but it should still be possible to write standard C++ code that will satisfy these requirements on any decent compiler (I've verified that my solution works on GCC, by examining the assembly output).

EDIT: see this clarification for more details.

If you want to post a solution or a hint, hide your solution in an edit to as not to spoil it for others.
Re: A challenge problem (response to post by bmerry) | Reply
I don`t know if You would consider the code as breaking the duplication rule, but anyway it is in edit.
Re: A challenge problem (response to post by bmerry) | Reply
OK, that should be my last submission. I've just finished this version and I'm about to add it to my personal archive of interesting C++ code. Thanks to bmerry for an interesting problem!

(Code in edit).
Re: A challenge problem (response to post by maniek) | Reply
I assumed we can't modify the base class. In particular, if Base is a part of a library and other classes are relying on semantics of foo, your change will break them.
Re: A challenge problem (response to post by bmerry) | Reply
Much easier. Code in edit.
Re: A challenge problem (response to post by eraserhd) | Reply
Shouldn't that require derived's foo() to be static?
Edit: I think this is cheating because its working here only because the function does not accesses any of the object variables. It gives seg fault for the code in edit.
Re: A challenge problem (response to post by bmerry) | Reply
Here is my attempt at it. I don't know how to check if there is a vtable lookup for it. I believe it is not. The only change I did is to remove the virtual keyword from derived's foo()'s prototype declaration. Code in edit.
Re: A challenge problem (response to post by bmerry) | Reply
derived->Derived::foo();
Re: A challenge problem (response to post by bmerry) | Reply
Just to clarify: these are your classes so you can change the implementation however you like. What you need to keep the same is the source-level interface to those classes, so that you don't break code that uses the classes. Also the bit about "duplicated code" means that you shouldn't duplicate large amounts of code. In this case, pretend that "cout << ..." is a large amount of code, since normally these methods would do something more useful.

And some comments on solutions:

  • Krzysan Very nice idea, I hadn't thought about trying to do it without modifying Base. If you wanted to refine it even further, you could make the argument of a private inner class, so that nobody can accidentally pass the argument.

  • maniek That's pretty much what I had in mind. One catch is that you should implement the wrappers in the header, since otherwise they can't be inlined from a different .cpp file.

  • eraserhd, tomek on the right track, but see my clarification above.

  • dhoni This won't work, and it's an important point to understand about the <code>virtual</code> keyword. If a base class declares a method virtual, then any method in a derived class with the same name and signature is also virtual, even if it isn't declared virtual.
Re: A challenge problem (response to post by bmerry) | Reply
:)

I see you guys were busy during Christmas! Very nice problem!
I have found two approaches. Hope to be correct in the context you provided. Here they are (in the edit):
Re: A challenge problem (response to post by bmerry) | Reply
Nice solutions by maniek and eraserhd (he really loves the NULL pointer). Pretty impressive one by Krzysan.
Re: A challenge problem (response to post by zmij) | Reply
P.S.: Sorry to spoil this thread but i couldn't properly hide the code. I tried the white font thing but it didn't hide the cpp code. How did you do it?
Seems like hiding the code in an edit is the preferred way to do this. Just edit your post and delete all the code - people can then see it by reviewing your edits.

I found your recurring template thing very confusing. I understand how the actual recurring template bit works, but I'm not sure how your classes map onto Base and Derived in my sample code. I don't see how you can achieve run-time polymorphism with what you've written.
Re: A challenge problem (response to post by bmerry) | Reply
You did not say run-time polymorphism. You only said polymorphism.
And indeed this is static (compile-time) polymorphism - also called sometimes simulated dynamic binding (it's a widely used method; e.g. in Boost, some implementations of the STL, in ATL and WTL).

I think my example was a little bit hasty. I'll try to come up with a more elaborated example, though it does not seem i understood correctly the problem and it's not the answer you seek.
Re: A challenge problem (response to post by zmij) | Reply
See bmerry's clarification:
..these are your classes so you can change the implementation however you like. What you need to keep the same is the source-level interface to those classes, so that you don't break code that uses the classes.
It means that the code:
int main() {
	Derived *derived = new Derived;
	derived->foo(); // (*) prints Derived::foo
	Base *base = derived;
	base->foo(); // prints Derived::foo
	base = new Base;
	base->foo(); // prints Base::foo
	delete base;
	delete derived;
	return 0;
}
(any user code that relies on the class definitions as seen in the original post) must work afterwards exactly the way it did before (all polymorphism aspects included, that means), unchanged, just with an added requirement that line (*) be more efficient. Changing user code to embrace (dynamic_cast<Derived*>(derivedBase))->foo() or MyDerived() is out of question.

Take a look at maniek's and Krzysan's correct codes to understand what it takes.
Re: A challenge problem (response to post by ulzha) | Reply
I did take a look (and indeed they provided very intelligent solutions) but i don't get the part with "what it takes".

Anyway, as i previously said, i did take a wrong turn and i did not fully comprehend the requirements. I'll try to come up with a real solution in a timely fashion. If not, then it means i do not have "what it takes".
[ 1 2 ]    NEXT >

RSS