Aside from the author's habit of putting spaces after angle brackets and parenthesis, it's standard looking code. It's pretty busy looking, but then again, there's a lot going on:
- A generic type T is introduced into the scope of this member function.
- The template parameter MAXN is a compile time constant that is part of the type of the data structure.
- This is the count member function of the class BST, which is paramaterized on the types mentioned above.
- count does not modify any instance variables of BST.
- The parameter x is passed by constant reference.
- count's return type is int.
- The actual value returned is 1 if find(x) evaluates to true, and 0 if find(x) evaluates to false.
You learn to look for what you need to know when reading the code. Also, it's also worth noting that this code is most decidedly C++ only. C programmers may hate this code.
Thanks for the summary. This is my code. I've since switched to using "Bst" instead of "BST" for class names. I've also stopped putting spaces inside parentheses and angle brackets. Although I still think that code looks better with the spaces, I realize that most people don't format it that way, and I'm fine going with the popular convention.
This really sucks for angle brackets though. Compare
This is neither beautiful nor ugly. It is annoying.
I've been routinely programming in C++ for over a decade and this sort of required verbosity is what really rubs me the wrong way. This piece should really be:
When this is getting compiled, the template< class T, int MAXN > part can be unambiguously deduced from the context, so needing to type it is really a matter of helping a compiler do its job. MAXN is not used, so there's no need to drag it into the picture. Instead tell the compiler that BST can be specialized with more than one parameter by using trailing comma. The const-ness can and should be deduced automatically by looking at what find() is like, in a recursive fashion. If nothing in find() and the functions it calls modifies the x, then count() can accept const arguments and can be considered const itself.
I mean, c'mon. My car can park itself, but my compiler can't understand parametrized types without hand-holding :)
I would argue that automatic inference of 'const' is a very bad idea because it defeats the whole purpose of having 'const' in the first place -- to catch bugs at compile time. If somebody modifies 'find()' in a way that makes it non-const, then your code will continue compiling without errors. However, if somebody relies on the fact that 'count()' is const, then that person would be royally screwed, and it will take weeks to find the bug.
Re: const inferrence - I have been thinking about it on and off for a while now and I think C++ has it backwards to what it should be. Consider the case when I am implementing some function and need to call foo() passing it variable bar, but don't want foo to modify it.
The way C++ offers to solve this problem is by having me first code a version of foo that swears that it does not touch its argument. So effectively I need to code foo in a way that anticipates const usage, i.e. make it forward compatible with const expectations of external code. Expectations that may or may not materialize, but yet I still need to be mindful of them. This seems excessive.
The way I would rather do it is to state that I expect foo() not to modify my variable when I'm issuing a foo call -
foo( const bar ); // note the spacious padding :)
and then let the compiler decide if this restriction can be satisfied. Note that this example assumes that bar is a local variable. Another common case is when bar is a given and already a const, and then I can do just this -
foo( bar );
In other words, const-ness should be a property of just variables. In a vast majority of cases deducing if a function is const can be done automatically -- and this is what I want from my compiler.
Am I missing something? This is a complex subject, so probably I am.
I don't think this is enough for a lot of common cases. Let's say you want to write a 'sort()' function. It takes a 'vector' and a comparator function. Unless that comparator function is declared 'const', you can't be sure that it won't destroy your 'vector'.
Another example. Let's say your 'foo()' function calls 'bar.toString()'. How can the compiler tell whether this call should be allowed when 'bar' is 'const'? You would need to know whether 'toString()' modifies 'bar' or not, but you don't have a way to tell. You might be able to figure this out if you look inside the code of 'toString()', but what if 'toString()' is virtual? You can't look at the code then.
What you're missing is that const is a compile time validation. The compiler _does_ compute whether or not the function you've created is const automatically and uses that to give you an error when it conflicts with what you've told it to expect. This is a way of validating your code's assumptions.
It is slightly annoying that you do need to declare const in functions ahead of time, but it ensures that if you say "this function wont change the variable" your compiler will make sure that you dont. And no amount of changing the internals of that function will change that assertion.
The code is fairly idiomatic C++, except maybe for the name of the class template (BST); hardly anybody names their classes in all capital letters (note that naming template parameters [T, MAXN in this case] in all capitals is quite common). Other than that, maybe the spaces after ( and < as well as before ) and > are a matter of taste.
hardly anybody names their classes in all capital letters (note that naming template parameters [T, MAXN in this case] in all capitals is quite common)
Agreed. My code and a lot of C++ code I've seen uses uppercase for template parameters, but never for classes/structs or methods. (Actually, I generally follow the Java conventions for capitalization of class names, method/function names, constants etc, though I use underscores in local variables.)
(Other than return something which evaluates in boolean context unless the template function is skipped for instantiation due to SFINAE and not modify x or *this unless a C-style or const_cast is used somewhere).
Somebody correct me if I'm wrong, but as far as I can remember from when I was doing ICPC, I wasn't allowed to bring in anything in electronic format. I could, however, bring in printed materials.
Have the rules changed? Or are these libraries just for practice problems?
This guy's library can be contained within your submission source code, so it can be used. BOOST in any case won't be installed or would be kept out of execution sandbox, on the judge server, so BOOST won't be usable. STL will be present along the gcc version they use by default. S = Standard in STL :)
You can anything you like in paper form to the competition, so you could print this guys thing and type it in at the competition. You could certainly do the same for boost (but you'd be limited to the very small subset that is easy to type in).
