Libraries in C++ for ACM

http://shygypsy.com/tools/

by l0nwlf • 15 years ago

38 33 15 years ago

shygypsy.com

neo72• 15 years ago

Hi, Can you explain what is all this?

l0nwlf2• 15 years ago

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

neo72• 15 years ago

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

jey• 15 years ago

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

swah2• 15 years ago

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

sohilgupta• 15 years ago

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

Abednego6• 15 years ago

Thanks. I'm glad you find them useful.

oostevo• 15 years ago

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?

l0nwlf2• 15 years ago

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

lzm• 15 years ago

Any other ICPC world finalists on Hacker News?

Stockholm '09 here.

rfurmani• 15 years ago

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

swah2• 15 years ago

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

marshray• 15 years ago

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

lallysingh• 15 years ago

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

boris• 15 years ago

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.

dkersten2• 15 years ago

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

scott_s2• 15 years ago

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.

Abednego6• 15 years ago

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;

huhtenberg2• 15 years ago

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

Abednego6• 15 years ago

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.

georgecmu• 15 years ago

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

ideamonk2• 15 years ago

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

zem• 15 years ago

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

dkersten2• 15 years ago

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

Abednego6• 15 years ago

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

Libraries in C++ for ACM

Related Stories