Блог пользователя HosseinYousefi

Автор HosseinYousefi, история, 6 лет назад, По-английски

Competitive C++ Manifesto: A Style Guide

There are many style guides for C++ out there, but we can't really use them as competitive programmers. We just want to write our code correctly as fast as possible! Trying to hack people here on codeforces, I realized there is a need for a style guide! Our goal is to write correct, fast, clear and consistent code.

Disclaimer

This is not a rulebook. You can integrate parts of it into your coding style. Don't overthink it, especially during a contest!

I'm going to use this guide for myself and to teach my students. I'm planning to make some good stuff in the future following these principles! Stay tuned!

Compiler

Make use of C++17. Use -Wall -Wextra -Wshadow flags for compilation, and try to eliminate all of the warning messages, this will prevent you from having some silly bugs. There are more debugging flags like -fsanitize=undefined which helps you eliminate bugs such as array out-of-range access and integer overflow during runtime. For more information, check out "Read More" section.

Naming

C++ libraries use snake_case for functions and classes, in order to differentiate the user-defined code from the standard library, we will use CamelCase.

  • Types use UpperCamelCase: Point, SegTree
  • Functions and variables use lowerCamelCase: someMethod, someVariable
  • Macros and constants use all capital letters seperated by _: SOME_MACRO, MAX_N, MOD
  • Use meaningful names or at least meaningful enough for you.
Example
#define LOCAL
const double PI = 3.14;

struct MyPoint {
    int x, y;
    bool someProperty;
    
    int someMethod() {
        return someProperty ? x : y;
    }
};

Note

Using snake_case is fine, but be consistent!

Comments

In competitive programming, you usually don't want to write long comments, but in case you do want to write some comments, write them using // instead of /* */. Using // enables you to comment out a chunk of code with /* */ while debugging, and /* /* ... */ */ is a bug!

Example
/* commenting out a block of code - no problem!
 
// some comment about the function below...
void someFunction() {
    // do something
}

*/

Spacing

Control flow statements are if / else / for / while / ...

  • Indent using 2 or 4 spaces uniformly. Avoid using tabs since it might make the code stretched out in different websites (e.g. Codeforces) and also in print (e.g. ICPC). Set your editor to emit spaces when you hit the tab key.
  • Braces always open on the same line but close on a new line.
  • Preferably always use braces for control flow statement blocks even if it's currently only one line.
  • else should start on the same line after closing brace of if block.
  • Keep lines a reasonable length, some say 80 columns!
  • There should be exactly one blank line between methods. This helps you to organize your code better.
  • There should be no blank line after an opening brace or before a closing brace.
  • Binary operations should be spaced from both sides.
  • Unary operations should only be spaced from the left side.
  • Brackets <> [] {} are a part of their identifier like a[5], vector<int> or pair{1, 2}.
  • Parentheses should only be spaced from outside like (-a[3] + b) * (c + d).
  • Semicolons and commas should only be spaced from the right side.
  • Question marks and colons should be spaced from both sides (unlike English!). The only exceptions are labels like public: or switch cases case 10:.
  • There should not be any extra spaces at the end of each line.
  • Add a single newline character at the end of the file.
  • There should be exactly one space after control flow statements like if (flag).
  • In contrast to control flow statements, function calls should not be spaced like func(arg).
  • Preprocess statements should be written like #define SOME_MACRO and #include <iostream>.
  • Templates should be written like template <typename T> and a new line.
  • Scope resolution operator :: is a part of the identifier and should not be spaced.
  • Pointer and reference are a part of the type, space accordingly! Like int* ptr and const string& str. To avoid bugs, declare only one pointer per line.
  • . and -> operator should not be spaced. When -> is used to show return type (like in lambda expressions) it should be spaced from both sides.
  • Lambda expressions should be written like [](int x) -> int { return x + 1; }. The return type can be omitted most of the times. Feel free to expand the body exactly like a function if it has more than 1 line of code.
  • When overloading operators, treat them like functions, no spacing in the name like bool operator!();
  • Ellipsis ... should only be spaced from the left side.
Example
#include <bits/stdc++.h>

using namespace std;

const int DIFF = 10;

template <typename T>
struct Point {
    T x, y;
    
    Point(T _x, T _y) : x(_x), y(_y) {}
    
    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<Point<int>> v;
    for (int i = 0; i < 5; ++i) {
        v.push_back({i, i + DIFF});
    }
    for (auto p : v) {
        if (p.x + DIFF == p.y) {
            cout << p << '\n';
        } else {
            cout << "huh!?\n"; // will never get printed!
        }
    }
}
Output
(0, 10)
(1, 11)
(2, 12)
(3, 13)
(4, 14)

Competitive Coding Recommendations

  • Use #include <bits/stdc++.h> instead of many includes.
  • Use using namespace std; instead of typing std:: every time.
  • Use using instead of typedef, for example using ll = long long;. Rationale: It's more consistent with the style of modern C++.
  • Use struct instead of class. Rationale: It defaults to public, and you don't need encapsulation in competitive programming!
  • Don't use too many macros but don't be afraid of using macros! Rationale: It's not easy to debug and read a code full of ugly macros. but we're hackers after all!
  • Use const for defining a constant instead of #define. Rationale: consts have a type, and they are evaluated at compile time.
  • To avoid bugs, you can use curly braces for each case of switch statement.
  • Use auto to increase readability and decrease code size.
  • Use braced initializer lists.
  • Use emplace and emplace_back for containers when dealing with pairs and tuples. Rationale: (elem1, elem2, ...) instead of ({elem1, elem2, ...}).
  • Use lambda functions! They're especially useful when passing functions as arguments like in sort. Don't repeat yourself, use lambda functions in your code instead of copy/pasting.
  • Use nullptr instead of NULL or 0.
  • Boolean values are true and false!
  • Use ios::sync_with_stdio(false); and cin.tie(nullptr); for a faster I/O using cin/cout.
  • Use builtin functions starting with __builtin.
  • GCD and LCM are available in C++17 under gcd and lcm.
  • Use C++11 for-each style for loops for (auto& elem : vec).
  • Use C++17 binding style like for (auto& [key, val] : dic) and auto [x, y] = myPoint;
  • Use C++17 template argument deduction pair p{1, 2.5}; instead of pair<int, double> p{1, 2.5};.
  • If you have a lot of nested loops and conditions, refactor! You probably should be using functions.
  • Never use goto! But be brave enough to use goto when you want to break from several nested loops (in case you just can't refactor it)!
  • Some websites like codeforces use the flag -DONLINE_JUDGE to compile your code, this means that you can remove your cerrs or your debug functions automatically or redirect input/output to file instead of stdin/stdout, etc.
#ifdef ONLINE_JUDGE
#define cerr if (false) cerr
#endif 
// Alternatively this can be done using a local -DLOCAL flag
// when compiling on your machine, and using #ifndef LOCAL instead.
  • Prefer using normal operators like !, &&, ||, ^, ... instead of their alternative representations not, and, or, xor, .... Rationale: We're not coding in python!
  • Break down your code into different smaller functions. Your code will be cleaner and easier to debug.
  • Don't try to be too clever!
  • Don't reinvent the wheel!Make use of standard library!
  • Use common sense and be consistent!

Read more

Contribution

Any suggestions are welcome. You can contribute to this post by commenting or using GitHub.

Contributors so far: ntrung03, SharpC

  • Проголосовать: нравится
  • +251
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 9   Проголосовать: нравится +13 Проголосовать: не нравится

Happy New Year, and thanks for the helpful blog. In my humble opinion, an incorrect solution that passed a pretest is more likely to be hacked during a contest when it is more readable. Nonetheless, this case is better than the case when an incorrect solution fails during the system test phase because it is less readable, and as such no contestant in the hacking room is able to discover the error. In the former case, there may be enough time for the contestant to fix the code if the problem has not been locked yet.

P.S. I don't like to use the hacking feature for increasing my own rating in a contest, but I would like to use this feature only to help another contestant in avoiding a possible system test failure.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I agree! When your code is cleaner (definition of clean is different for everyone) it’s easier for you to spot mistakes, and debug. I’m less concerned about the hacking, since the guide is written not only for codeforces.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +64 Проголосовать: не нравится

      I don't really understand why people would want to prevent other people from trying to hack them (except for things like hashing). The only times somebody else hacking you is a bad thing is when your solution would have passed the systests if they hadn't hacked you (and nobody else uses the same hack on someone else during the contest). Usually, that's pretty rare. Other than that, I think of hacking as somebody else helping me debug for free.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 8   Проголосовать: нравится 0 Проголосовать: не нравится

      Fair enough. A common error in competitive programming that even senior C++ coders may experience sometimes is overlooking some problem constraint such as a maximum allowed value, time-limit, memory-limit, etc. In some problems, this may lead to an improper choice of a data type such as 32-bit integer for a variable whose value can be above INT_MAX, or an incorrect choice of a problem solving method, and can cause wrong answer, time-limit or memory-limit exceeded in pretest or system test, or even overlooking some corner test case that does not exist in the problem pretest. Hacking can offer useful feedback about the presence of any of these errors before the system test, provided that the contestant has not locked the problem, as mentioned before.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

You are citing Google C++ Style Guide that has few very doubtful recommendation:

  • T* var instead of T *var. In C++ usually one uses T *var but T& var because of frequent usage of var as variable of type T *, and, simultaneously, *var as variable of type T. It's not valid for T&, & here is ref-modifier, almost like cv-modifier. So most consistent style guides use T const& var, T const *var.
  • template <typename T> instead of template<typename T>. T<U> can be viewed as meta-function call, we don't use space in function call and in function declaration: fn(42) and void fn(int answer), so we don't use space inside type vector<int> and inside template declaration template<typename T>.

Also some minor patches I can propose:

  • One-char comment switch:
//*
uncommented
//*/

and

/*
commented
//*/
  • Keep lines a reasonable length, some say 80 columns! This requirement comes from archaic diff utilities in console. Modern limit is usually 120, but it was created only because of difficulties of work with diffs. Competitive programming doesn't include hours spent on git merges and conflict resolving, so this requirement just asks for unnecessary work.

  • There should be exactly one blank line between methods. This helps you to organize your code better. Exactly two. One blank line should be used for separation of meaningful blocks of code inside of function.

  • GCD and LCM are available in C++ under gcd and lcm. You forgot to mention that gcd and lcm are available only since C++17.

  • Use using instead of typedef, for example using ll = long long; There is need in another list item: Don't use integer types (except int) without explicit bit count, f.e. use int16_t instead of short and uint64_t instead of unsigned long long.

Perhaps you can also be interested in STL guide for students that take part in competitions (in Russian): https://sharpc.livejournal.com/99212.html

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    In C++ usually one uses T *var but T& var

    Citation needed.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • “Some” say! Reasonable for you with a wide screen monitor might be way more.
    • long long is guaranteed to be 64 bits. In production code you are right, but competitive programming doesn’t really need int16_t! Regardless, I used long long only as an example for using syntax.
    • For competitive programming, I opt to limit the amount of blank lines to the minimum amount necessary for dividing sections. If your code has many blank lines within one function, you should be probably breaking it down to different functions.
    • I have written in the first section, Compiler, to use C++17, so I didn’t need to specify it there.
    • C++ has more type safety than C. Pointers and Refrences are a part of the type, so they should be connected to their type. In contrast to C, which we would write int *p to say that *p is int meaning p would be a pointer to int. (You can find even Bjarne has said something like this somewhere in his site)
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

      long long is guaranteed to be 64 bits There is no such guarantee in Standard, it was the reason to introduce integer types with explicit bitness. Also uint64_t is shorter than unsigned long long.

      If your code has many blank lines within one function, you should be probably breaking it down to different functions. Your "many" may vary. Breaking down to functions is time-consuming action, so it requires more convincing reasong than just question of style.

      to use C++17, so I didn’t need to specify it there. It's fine but just inconsistent with few next lines where C++ versions are stated explicitly. Still not every judge has even C++11, so it could be useful to point out feature's year.

      so they should be connected to their type There are obvious asymmetry between pointers and references, for example T& a = init(); T b = a; is just why references are in use, but T *a = init(); T b = a; is compilation error (almost always :)). They should differ in code style as well.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You don’t need to use every single style recommendation in your code.

        I understand that there are some wars in style such as spaces vs tabs, or which style to use curly braces. Use the style you prefer afterall.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится

          We even didn't touch your imperfect recommendation about braces. I have cited only points that seems like randomly omitted from your guide.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why not be an edgelord and write T * var, T & var? Think of * as a shortcut for pointer, you wouldn't write Tpointer var or T pointervar.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +36 Проголосовать: не нравится

        because it starts to look like multiplication and bitwise-and?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится -31 Проголосовать: не нравится

          Between type and variable name? Really?

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            Are you aware that problem of recognition if some identifier is type or variable is Turing-complete in C++?

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              How is that relevant for coding style?

              • »
                »
                »
                »
                »
                »
                »
                »
                6 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

                Coding style should make reading easier. If your pointer usage is indistinguishable from multiplication without careful exploration of visibility and deduction chain of left identifier, it's not simplification, it's diversion and job security.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

                  If you can't determine what's an expression and what's a type-varname pair without careful exploration, a nice coding style is the least of your problems.

                  Also, what does job security have with competitive programming? You keep dragging unrelated things to this. Stop.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

                  It's not some exotic voodoo case, it's quite popular and the reason why STL and lot of libraries uses _t suffix for types.

                  Author and me didn't try to make special style guide for CP, author even didn't try to relax some Google requirements especially inconvinient for CP. So your objection is irrelevant.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится +1 Проголосовать: не нравится

                  _t suffix. It's so popular that I never needed it. Not a single time did I need to write nullptr_t, uint8_t or anything similar. STL doesn't use vector_t either.

                  The author of a code being unable to detect what's a type in that code really is an exotic voodoo case, no matter how much you try to claim otherwise.

                  Author and me didn't try to make special style guide for CP, author even didn't try to relax some Google requirements especially inconvinient (sic) for CP

                  You didn't read the blog post, huh? For example, the advice "using auto is good" is good for CP, but the Google style guide advises being much more careful. The topic of lambdas is much more complex there than just "use lambdas to keep DRY", too.

                  Why not just direct people to the Google style guide instead of writing a blog post if was the same thing?

                  Also, you defend something "especially inconvenient" on the basis of "coding style should make reading easier"? No thanks, I'd rather avoid your advice.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится -46 Проголосовать: не нравится

                  I will try to say it clearly: style like T * a and T & a is criterion for "get out of profession" and "cut off hands to neck". Sorry I'm not interested to convince you personally that it's wise policy.

                  Author made a nice attempt to shorten Google code style for students and it really needs only few my minor patches. So you are definitely overreacting and overlooking the essence of discussion.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится -20 Проголосовать: не нравится

                  I will try to say it clearly: style like T * a and T & a is criterion for "get out of profession" and "cut off hands to neck".

                  Finally you're making it clear — you're only here to fling insults. Good to know.

                  pic
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Oh, come on, save space, man! Everybody knows it should be T*var and T&var!

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    From Bjarne Stroustrup, Original Creator of C++:

    http://www.stroustrup.com/bs_faq2.html#whitespace


    Is ``int* p;'' right or is ``int *p;'' right? Both are "right" in the sense that both are valid C and C++ and both have exactly the same meaning. As far as the language definitions and the compilers are concerned we could just as well say ``int*p;'' or ``int * p;'' The choice between ``int* p;'' and ``int *p;'' is not about right and wrong, but about style and emphasis. C emphasized expressions; declarations were often considered little more than a necessary evil. C++, on the other hand, has a heavy emphasis on types. A ``typical C programmer'' writes ``int *p;'' and explains it ``*p is what is the int'' emphasizing syntax, and may point to the C (and C++) declaration grammar to argue for the correctness of the style. Indeed, the * binds to the name p in the grammar. A ``typical C++ programmer'' writes ``int* p;'' and explains it ``p is a pointer to an int'' emphasizing type. Indeed the type of p is int*. I clearly prefer that emphasis and see it as important for using the more advanced parts of C++ well. The critical confusion comes (only) when people try to declare several pointers with a single declaration: int* p, p1; // probable error: p1 is not an int* Placing the * closer to the name does not make this kind of error significantly less likely. int *p, p1; // probable error? Declaring one name per declaration minimizes the problem &mdash; in particular when we initialize the variables. People are far less likely to write: int* p = &i; int p1 = p; // error: int initialized by int* And if they do, the compiler will complain. Whenever something can be done in two ways, someone will be confused. Whenever something is a matter of taste, discussions can drag on forever. Stick to one pointer per declaration and always initialize variables and the source of confusion disappears. See The Design and Evolution of C++ for a longer discussion of the C declaration syntax.
    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      BS explicilty stated that T* is consistent only when you use one declaration per line. You are trying to choose style for CP and even your short code sample contains declaration of few variables in one line. So BS's wisdom is not for you.

      Also you are selectively citing him: he never uses template <typename T>, only template<typename T>.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится

        I don’t feel like this discussion is constructive. This is yet another style guide which is suitable for me personally. I am neither forcing you or anyone to use this nor saying it’s the perfect style. I myself noted that you may only integrate parts of it in your coding style and it’s perfectly fine.

        That said. You’re not going to get any more replies from me on this.

        Cheers!

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится -21 Проголосовать: не нравится

          My first comment was constructive, according to your Any suggestions are welcome. All your replies were just attempts to not accept any patches. Of course it's your business, but if your objections are ungrounded they will be busted.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Make use of -fsanitize=undefined (UNIX only) flag for compilation, too. This helps you eliminate bugs such as array out-of-range access, integer overflow during runtime.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +27 Проголосовать: не нравится

TL;DR: copy tourist's style.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

We don't know what data type T is in Point class. But we need min or max of T. How it can be done?

template <typename T>
struct Point {
    T x, y;
    
    Point(T _x, T _y) : x(_x), y(_y) {}
   
    void print_max_min_of_T() {
        cout<<"Maximum: "<<numeric_limits<T>::max()<<endl;
        cout<<"Minimum: "<<numeric_limits<T>::min()<<endl;

    }
    
    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};
  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    When instantiating the class for a specific T, we know what it is. Before that, we don't need to know. You can view a template as a function in C++ compiler language that takes template arguments and returns a class/function/whatever.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Why do some people use solve function in c++. Also why do they declare stuff globally? Is there a helpful resource for the same?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    experience is the most helpful resource. code as you please, look and pick up what you find convenient for your reasons from others' practices.

    That being said, the solve function unclutters the main function, and lets it handle perhaps input, output, test cases, where the algorithm itself sits in the solve. If your solution is recursive, a solve function is mandatory.

    As for global variables, they can be used since you don't need to pass them in as parameters to your functions, so they save writing time. You can simply look up "benefits of global variables in competitive programming" to be redirected to relevant resources.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

You should use constexpr instead of const for compile-time values.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A better rationale for not using these !, &&, ||, ^, ... can be that the alternatives are longer :p