Libraries in C++ for ACM | Hacker News Reader

Libraries in C++ for ACM

shygypsy.com

38 pointsl0nwlf33 comments

Is this beautiful or ugly to a "C/C++" programmer?

  template< class T, int MAXN >
  int BST< T, MAXN >::count( const T &x ) const
  {
      return find( x ) ? 1 : 0;
  }

I don't know.

What does find(x) do?

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

I don't think many C++ programmers think that much in the language counts as beautiful.

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

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

vector<pair<int, string> > blah;

vector< pair< int, string > > blah;

I actually prefer the first one, since it's the closest that C++03 will allow to what I want. In C++0x, you will be able to say

  vector<pair<int, string>> blah;

And the parser will recognize >> as the end of two template calls, and not the stream operator.

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:

  int BST<T, >::count(T & x)
  {
    return find(x) ? 1 : 0;
  }

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 think you might like Python.

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.

I hear you regarding Python.

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.

Hi, Can you explain what is all this?

These are standard data structures and algorithms coded in C++. Pretty useful for programming competitions.

hmm... thanks a lot, was just reading all that.

Oh, looks like the title should say "ACM ICPC". "For ACM" was very confusing to parse.

I'm missing something... Are those more useful to competitions than to general use for some reason?

In general use, you can use real libraries instead. Or, you can choose not to use C++, which is also a good choice.

"Real libraries"? Hey!

Any other ICPC world finalists on Hacker News?

Stockholm '09 here.

Prague and Shanghai (Igor, the author, was also at Shanghai)

Awesome work!! Great set of libraries for competitions...

Thanks. I'm glad you find them useful.

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?

You can always bring codes in the form of printouts. And these libraries are mainly for practice problems on ACM UVA Online Judge.

Are you allowed to use STL/BOOST in the competition?

STL is allowed in all the competitions including TC, ICPC, SPOJ, etc BOOST is not allowed in any.

why would boost not be allowed but this guy's libraries be?

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

At least, this is how it was seven years ago.

The International Olympiad in Informatics also allows STL, but no other libraries.

Google Code Jam allows BOOST and all other freely available languages and libraries.

Reply on news.ycombinator.com