Libraries in C++ for ACM(shygypsy.com)

http://shygypsy.com/tools/

6 comments

swah15 anni fa

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

scott_s15 anni fa

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.

Abednego15 anni fa

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;

to

vector< pair< int, string > > blah;

scott_s15 anni fa

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.

huhtenberg15 anni fa

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

Abednego15 anni fa

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.

huhtenberg15 anni fa

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.

Abednego15 anni fa

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.

[deleted]15 anni fa

Kejistan15 anni fa

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.

boris15 anni fa

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.

dkersten15 anni fa

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

marshray15 anni fa

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

lallysingh15 anni fa

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

neo715 anni fa

Hi, Can you explain what is all this?

l0nwlf15 anni fa

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

jey15 anni fa

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

swah15 anni fa

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

jrockway15 anni fa

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

Abednego15 anni fa

"Real libraries"? Hey!

neo715 anni fa

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

lzm15 anni fa

Any other ICPC world finalists on Hacker News?

Stockholm '09 here.

rfurmani15 anni fa

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

sohilgupta15 anni fa

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

Abednego15 anni fa

Thanks. I'm glad you find them useful.

oostevo15 anni fa

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?

l0nwlf15 anni fa

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

georgecmu15 anni fa

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

ideamonk15 anni fa

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

Abednego15 anni fa

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

dkersten15 anni fa

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

zem15 anni fa

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

ideamonk15 anni fa

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

bajsejohannes15 anni fa

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.