PrevNext

(Optional) C++ - Writing Generic Code

Authors: Aryansh Shrivastava, Benjamin Qi

Writing code that can easily be reused or extended.

Templates

A template consists of code that is assumed to be in every file. Don't be afraid to write your own template or don't use one at all! Below, we'll give an example of what a template might look like.

Warning!

USACO rules prohibit the use of pre-written code, including templates. Therefore, make sure you are able to re-type your template in contest (or just don't use one)!

Templates in C++ can take advantange of more powerful features (e.g. macros) than the other contest languages, and they can be more customized to each competitor.

Code Snippet: C++ Short Template (Click to expand)
int main() { setIO(); }

This module will cover many of the features used in the code above.

What Is Generic Code?

Resources
Aryansh

Integrated here for enhancement.

LCPP

Generic code is an important concept in informatics. Of course, as all concepts go, you may dodge generic code and continue to write in a hyper-specific style. As such, begin by questioning purpose.

Generic code is adaptable, meaning that it can be put to use immediately in many ways without major changes. It can be reused, extended, and even versioned powerfully to save time. Time is of essence in informatics, where I refer to both algorithmic time complexity and coding time.

Even if you are writing a very specific data structure or algorithm, to truly grasp it, a good contemplation is "Can I generalize what I have learned to a broader class of problems?" Answer this by then attempting to generalize. That said, before you proceed, I issue the below warning:

Warning!

Generic code can easily assist black-boxing, where you write a snippet of code such that you either forget its meaning or have no idea what it means in the first place. This is a common pitfall, and you should avoid this as much as possible if you truly want to grasp a concept in informatics.

Modern C++, a groundbreaking language in the current informatics scene, indeed has several builtin features to support and streamline generic code. Here, we will cover the basic important ones you will definitely want to add to your coding arsenal.

Classes

Classes are by far the most important utility in extensible code. If you ever want to write a data structure that has several member functions to process stored data, classes are for you. Of course, classes can have public and private sections. For instance, consider a class Human, which maintains several relevant member functions.

#include <bits/stdc++.h>
using namespace std;
class Human {
private: // internal properties
int body_temp;
int temper;
string name;
public: // external reactions

But how do we actually use (and reuse) this class data structure we have created? We do this by creating instances of this class, concretely known as objects.

Below is an example instance of the Human class named sal.

Human sal;

Of course, we will want to initialize any object of this human class with its fundamental attributes (body_temperature and temper from the above), but the problem here is that we are unable to access them directly; they are private and remain uninitialized.

To partially alleviate this, we can initialize variables in the class declaration itself:

#include <bits/stdc++.h>
using namespace std;
class Human {
private: // internal properties
int body_temp = 98;
int temper = 25;
string name = "Sal";
public: // external reactions

This gives us something to work with, and we can now create sal in main() as well as call his member functions (instantiated directly from the base Human class).

int main() {
Human sal;
cout << sal.get_name() << " feels " << sal.get_feeling() << " and is "
<< sal.get_emotion() << endl;
}

To completely solve this, we might be forced to make these variables public, but instead we can be more clever and write a constructor function for this class, essentially a function that is automatically called whenever an instance of the class is created. Constructors are useful when we want to prevent modification to variables we create but be able to initialize them for use, making them naturally the most viable option for proprietary software companies.

We can create a constructor for the human class and require initialization of the variables body_temperature and temper, which gives us some control over Sal's intrinsic properties as they are initialized. The overall code becomes:

#include <bits/stdc++.h>
using namespace std;
class Human {
private: // internal properties
int body_temp;
int temper;
string name;
public: // external reactions

This is immediately very extensible if we wish to create multiple instances of human, all with their own initial properties. In fact, we can be even more general by creating an external function condition that easily states feelings and emotions for us without having to be rewritten.

// Prints out the condition of a human to cout
void condition(Human h) {
cout << h.get_name() << " feels " << h.get_feeling() << " and is "
<< h.get_emotion() << endl;
}
int main() {
Human sal("Sal", 98, 25);
Human bob("Bob", 100, 9);
Human joe("Joe", 85, 35);
// Print out the conditions of all three people
condition(sal);
condition(bob);
condition(joe);
}

As one very specific but useful note on constructors, when we wish to merely initialize properties, we can adopt an alternative declaration that executes significantly faster than the first; using the argument name as the variable itself also becomes permissible and is guaranteed defined behavior:

Human(string name, int body_temp, int temper)
: name(name), body_temp(body_temp), temper(temper) {}

Structs

Structs are useful when we care less about keeping private properties and more about having just a general reusable data structure. This means everything is public in a struct by default, and a human struct, along with the reformatted constructor above, would look like:

struct Human {
int body_temp;
int temper;
string name;
Human(string name_, int body_temp_, int temper_) {
name = name_;
body_temp = body_temp_;
temper = temper_;
}

Immediately, our struct is easier to manage given its open nature. It is more integrated with the surrounding code, and we can do manipulations like the following:

int main() {
// Initialize Sal
Human sal("Sal", 98, 25);
condition(sal); // Get Sal's initial condition
sal.name = "Sally"; // Sal's friends sometimes call him Sally
sal.body_temp = 102; // Sal gets sick
sal.temper = 40; // He develops a bad temper due to his sickness
condition(sal); // Now we get Sal's new condition
}

Finally, we can choose to discard the constructor altogether and opt for an initializer list based on the order of the declaration of intrinsic variables. In the Human case, the variables in order are body_temp, temper, and name, so we can remove the constructor and opt for an initializer list like:

human Sal{98, 25, "Sal"};

Needless to say, all of this enables very clean initialization and manipulation of classes and structs, integral to generic code.

Templates

The Human class example, though well-defined, was mostly intended to serve as an example of the versatility of classes and structs. We now switch to something simpler. Imagine a three-dimensional point in space as the following struct and two of the said 3D points: p1 and p2.

struct Point3D {
int x;
int y;
int z;
} p1{1, 2, 3}, p2{3, 4, 5}; // We can make some instances right before the ;

But what if we wanted to make a point p3 with coordinates as doubles? We would then be forced to create a secondary point struct pt1:

struct Point3D {
int x;
int y;
int z;
} p1{1, 2, 3}, p2{3, 4, 5};
struct Point3DDouble {
double x;
double y;
double z;
} p3{1.1, 2.2, 3.3};

This might not seem too bad immediately, but imagine having to create structs like this over and over again just to accommodate various type changes. We need something better.

Lo and behold, we have the template to come to our rescue. We can use the format template<...> to specify the specific templating conditions and then simply define the struct normally. In particular, if we use a class T, we achieve:

template <class T> struct Point3D {
T x;
T y;
T z;
};
Point3D<int> p1{1, 2, 3};
Point3D<int> p2{3, 4, 5};
Point3D<double> p3{1.1, 2.2, 3.3};
Point3D<long long> p4{9223372036854775807, 9223372036854775807, 9223372036854775807};

It would be narrow-minded to think that templates are in any way limited to classes and structs. They can be used with functions and much more. For example, take a look at this function ckmin:

/**
* If b is less than a, this changes the value of a to that of b
* and returns true. If not, the function simply returns false.
*/
template <class T> bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}

One interesting use case is that of the size of various containers. The size member function of a container usually returns a type incompatible with int, but we can easily write a templated function to fix this, handling all types of containers at once:

template <class T> int sz(const T &container) { return (int)container.size(); }

You can call this through typing sz<vector<int>>(v) where v is a vector<int>, but since C++11, functions (but not classes or structs until C++14 and C++17) can actually infer template arguments, meaning that we can simply use sz(v)!

What if we wanted to put multiple arguments in a template to handle multiple classes? Consider the below secondary pair comparator struct as an example:

struct CPS {
template <class T, class U>
bool operator()(const pair<T, U> &a, const pair<T, U> &b) {
return make_pair(a.second, a.first) < make_pair(b.second, b.first);
}
};

And in this design, since the template arguments both apply to only a function, they can be easily inferred! For instance, declaring a set of pair<double, int> in C++11 is as easy as set<pair<double, int>, CPS>.

What constitutes what other kinds of types we can put in templates? As a general rule of thumb, until C++17, the types valid in template arguments are only classes and fundamental types, of which only classes can be directly inferred in many cases by functions.

In fact, we can even have templates that take a variable number of arguments, known as variadic templates, or templates within templates, known as nested templates, both of which are beyond the scope of this basic exposition but can be found here and here.

As a fun fact, just as templates give us so much control over the generality of the language, a lot of the C++ standard in itself is written generically with templates under the hood.

Type Aliases With using

typedef is now rather outdated (though still used by some) because it is more or less just an annoying version of using with frustrating semantics, so we will not cover it here.

using is a fascinating keyword, frequently used to simplify namespace prefixing when applicable. For instance, statements like

using namespace std;

actually allow us to use an entire namespace. Of course, since using namespace std is frequently limited to the competitive programming community and looked down upon otherwise, we can use using to invoke better simplifications.

Suppose that a lot of my code usesstd::cout, which I find frustrating to type. I can write

using std::cout;

and then just live with cout. But what if I was using strings and wanted to type neither std::string nor string? I could use using twice to fix this:

using std::string; // Unnecessary if already using namespace std
using str = string; // Use str as an alias for string

Or I could compress this into a single statement:

using str = std::string; // str is an alias for std::string directly

We can make even more aliases, with even aliases within aliases (see ll), for environments where speed is key, such as competitive programming:

using namespace std;
using ll = long long;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;

Warning!

If you use too many type aliases or macros then your code will become unreadable to anyone besides yourself!

Finally, we can take using to the next step and invoke templates! For instance, if we want to be able to write arr<int, 6> instead of std::array<int, 6>, we write:

template <class T, int SZ> using arr = std::array<T, SZ>;

As another example, if we want to use ai to mean integer array, we can make constructions like ai<6> work as well:

template <int SZ> using ai = std::array<int, SZ>;

In general, it is important that using declarations have strong scope guarantees, meaning that they will not work outside of their defined scope. To use declarations everywhere in the program, they must be invoked in global scope. But, if we want to be clever and create a reusable struct and just specify template arguments internally, we always have the option of:

struct Point {
using T = int;
/*
* Within this scope, T is an alias for int.
* Just change this declaration to change T's meaning within this struct
*/
T x;
T y;
T z;
};

In case we want to be able to access the specific type T's alias meaning outside of Point, this too becomes very easy:

struct Point {
using T = int;
T x;
T y;
T z;
};
int main() {
// U becomes a copy of T from Point's scope and is now in the scope of main
using U = Point::T;
}

Macros

We end this section off with #define, which is used to define macros.

Resources
CPH

simple examples of macros, describes a common bug

GCC

reference

GFG
LCPP

#define is essentially a crude find-and-replace that happens before compile time (in the preprocessor stage). In this sense, it is easy to use, where #define NAME VALUE would ideally find all instances of NAME in the code and replace them with VALUE.

This example defines MOD as 1e9 + 7 by find and replace.

#define MOD 1e9 + 7
int main() {
cout << int(MOD) << "\n"; // outputs 1000000007
cout << int(MOD * 2) << "\n"; // outputs 1000000014
cout << int(2 * MOD) << "\n"; // outputs 2000000007
}

But that's obviously not a good idea. A better alternative is the following:

const int MOD = 1e9 + 7;
int main() { cout << MOD << "\n"; }

Also, using is preferable to #define. For example, the following code with #define will not compile (but it will with using).

#define ll long long
// using ll = long long;
int main() { cout << ll(1e18); }

The takeaway from this is to avoid #define when possible. Of course, some competitive programmers use macros extensively. Some examples are presented below.

Pairs

using pi = pair<int, int>;
#define mp make_pair
#define f first
#define s second

It might be annoying to keep on typing first and second, especially if you have nested pairs. These macros fix that.

Vectors

using vi = vector<int>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)

We convert a size to a signed integer to avoid unsigned overflow, as shown by this example:

vi x;
cout << x.size() - 1 << "\n"; // otutputs 18446744073709551615 (incorrect)
cout << sz(x) - 1 << "\n"; // outputs -1 (correct)

all(v) makes sorting part or all of a vector a bit shorter.

vi v{2, 4, 1, 5, 3};
sort(1 + all(v)); // v is now {2, 1, 3, 4, 5}
// This expands to sort(1 + begin(v), end(v));
sort(all(v)); // {1, 2, 3, 4, 5}

Preprocessing Logic

Ever wanted to write a program that compiles in different ways depending on some initial conditions? We can use preprocessor directives like #if and #else, or #ifdef and #ifndef to allow for this.

For instance, I may want my struct Point to be two-dimensional in some cases and three-dimensional in others. I can do this like so:

const bool d2 = false; // false for 2D, true for 3D
template <class T> struct Point {
#if (d2)
T x;
T y;
#else
T x;
T y;
T z;
#endif
};

If we are not opposed to using #define, we could use #ifdef and #ifndef to see whether or not a macro is defined via #define.

// #define 2D // Uncomment to make Point 2D
template <class T> struct Point {
#ifdef 2D
T x;
T y;
#else
T x;
T y;
T z;
#endif
}

There are many clever applications of this, including versioning. Importantly, if we want code to run differently for different versions of C++, we can write:

#if (__cplusplus < 201703L)
/**
* "Clamps" v between the values of lo and hi if it's
* out of the bounds defined by those two values.
*/
template <class T> constexpr const T &clamp(const T &v, const T &lo, const T &hi) {
assert(lo <= hi);
if (v < lo) {
return lo;
} else if (hi < v) {
return hi;
}
return v;
}
#endif

Namespaces

Finally, we can write our own namespaces to separate various functions. Within a namespace, we can have functions, variables, classes, and even more namespaces. Then, we can invoke using declarations to use the whole namespace.

namespace test {
const string greeting = "hi";
namespace test1 {
const int time = 2;
}
using namespace test1;
template <class T> struct TestDS {
T s;
void add(T x) { s += x; }
T get() { return s; }
};
} // namespace test

These are fairly self-explanatory, but a more rare feature of C++11 is the inline namespace. Inline namespaces are not technically real namespaces but allow us to chunk up code and avoid having to use namespaces just to gain access.

inline namespace test {
const string greeting = "hi";
}

So why even have inline namespaces? We can use their features interestingly. For instance, suppose we had a feature in an old version v1 of a program but now removed it in the new version v2.

namespace v1 {
const string buggy_feature = "bugs";
const string greeting = "hi";
} // namespace v1
inline namespace v2 {
// removed the buggy_feature from this new version
const string buggy_feature = "what buggy feature?";
const string greeting = "hi";
} // namespace v2
int main() {
cout << buggy_feature << "\n"; // outputs "what buggy feature?"
cout << v1::buggy_feature << "\n"; // outputs "bugs"
}

Now, not using a namespace will automatically use v2. But if we want access to v1 of the buggy_feature, we can simply write v1::buggy_feature. There you have it, simple and effective version control!

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext