The C++ programming language 2. Pre-processor directives 3.

Variables and Constants

January 4, 2025
Pre-processor directive always start with a ’#’.
Ramasamy Kandasamy 3.1. Variable types
• #include filename
Type Location memory location Scope
Replace with contents of filename
1. Compile and Debug Global Outside functions data/bss Global
Static Outside functions data/bss Source file
1.1. G++ – files with double quotes: # include "file.h" Static Inside a function data/bss Local
Usage: First pre-processor looks for file.h in the same directory Local Inside a function stack Local
g++ option [Link] -o hello as the source file and then in pre-configured list of standard Register# Inside a function∗ register Local
∗
g++ [Link] -o hello system directories. causes error if declared in global space.
#
g++ -O3 [Link] -o hello This is not strict. The compiler might choose not to keep the
– files with angle bracket: # include <stdio.h>
Options: variable in register.
The pre-processor looks only in the pre-configured list of
-o Output file name.
standard system directories. 3.2. Variable declaration and initialization
-I Include additional directories in the search path. Eg:
g++ -I /home/user/libs [Link] – Additional directories can be include • Eg: int num; Local or global depending on context.
-O<level> Optimization level, starts from 0. Eg: -O3
-g Creates breakpoints for debugging using GDB. • #define NAME replacement text • Eg: static int num; Static variable.
Missing link. Used to link certain libraries like math.h. NAME is replaced with replacement text
-lm • Eg: const int num; Causes error if num is modified.
-E Output preprocessed but uncompiled code.
-S Compile but do not assemble. • #define token (arg1,arg2) statement 3.3. Data types
-c Compile and assembly, but do not link. Defining a macro. Eg:
Major variable types
#define max(A,B) ((A) > (B) ? (A) : (B))
1.2. GDB char 1 byte.
• #undef NAME short int 2 bytes.
To run: gdb hello
Nullifies existing definition of NAME. Used to ensure a routine is int 4 bytes.
break Set break point. Eg: break function or break line
a function. long int 4 to 8 bytes.
number .
run Run the program. The program stops at every break long long int 8 bytes.
point. • #if, #elif,#else, #endif int128 t 16 bytes, not part of standard definition, but is
next Run until next breakpoint. Eg-1: supported by g++.
print Eg: print i or print &i #if !define(HDR) float 4 bytes.
sizeof Eg: print sizeof(i) #define HDR double 8 bytes.
&i Address of i. /*contents of hrd.h*/ long double 80 bit floating point supported by g++.
*j Content of memory location j. #endif size t unsigned type.
ptype get type of a variable. Eg: ptype(i) NOTE: define() after #if returns 1 if its argument is already Their actual size might vary depending on the system.
set var Reassign variable. Eg: set var i = 1 defined. Modifiers for variable types
Here #define HDR is first line of hrd.h and this file is included unsigned With int and char.
disassemble Use after break and run. Gives assembly code.
Accessing memory location using x only if it was not already included. Eg-2: signed With int and char.
Usage: x/nfs. nfs describes the format. #if SYSTEM == SYSV
n - Number of units to display. #define HDR "sysv.h"
3.4. Constants
f - Number format. #elif SYSTEM == BSD 1234 int
s - Size of each unit. #define HDR "bsd.h" 1234567890L long int. When should I use L?
x Hex. #elif SYSTEM == MSDOS 010 Octal ≡ 8.
o Octal. #define HDR "msdos.h" 0x10 Hexadecimal ≡ 16.
t Binary. #else 0b10 Binary ≡ 2. Binary format is not part of standard
d Decimal. #define HDR "default.h" C, but is supported by gcc.
u Unsigned decimal. #endif ’x’ Character constant, has an integer value.
i Instruction. ’\ooo’ Specify ASCII code of the character in octal.
c Character. ’\xhh’ Specify ASCII code of the character in hexadecimal.
• #ifdef and #ifndef
s String. Escape sequences:
Test whether a name is already defined.
b byte. \a, \b, \f, \n, \r, \t, \v, \\, \?, \’, \".
Eg-1 in above point can be replaced by: #ifndef HDR
h Halfword. Enumeration constants: List of constant integers.
#define HDR
w Word.
g Giant.
/*contents of hdr.h*/ • Eg: enum ans {NO, YES};
#endif By defaults integers are assigned from 0.
• Eg: enum days {MON=1,TUE,WED,THU,FRI,SAT,SUN};
Here, MON is assigned 1, and by default, TUE is 2.

1
 • Eg: enum months {JAN =1, FEB, APR=4,MAY}; Continue continue: Continue next iteration.
Here, MAY is 5.
5. Control Flow Works for while, for, do while
If switch is within a loop and if continue is
used inside switch and if it is executed, then
4. Arithemetic and logical operation the loop skips to next loop.

Operators Associativity Goto and label Example:

If-else if (expression )
if (disaster)
1 () [] -> . left to right statement
{
2 ! ˜ ++ -- + - * & (type) sizeof right to left else if (expression )
goto error;
3 * / %(reminder) left to right statement
}
4 + - left to right ..
. ···
5 << >> left to right error:
6 < <= > >= left to right else
statement {
7 == != left to right statement
8 & left to right Switch switch (expression )
}
9 ^ left to right {
10 | left to right case const-expr : statements ; break;
11 && left to right case const-expr : statements ; break; Shorter alternative for if-else statement:
12 || left to right default: statements ; break; x = <cond-expr> ? <out-if-true> : <out-if-false>;
13 ?: left to right } Eg: char is pos = (n > 0) ? ’y’ : ’n’;
14 = += -= *= /= %= &= ^= |= <<= >>= right to left Without break statement the execution will fall
15 , left to right through all the cases.
This can be used as:
4.1. Explanation for selected operators switch (expression )
{
• -> and .
See Structures. case 1: case 2: case 3:
• Casting group = 0;
Changes the type of a variable. break;
Eg: float a = (int) 3/2;// a is 1.0. case 4: case 5:
group = 1;
• sizeof break;
sizeof num; // Give size of the variable num. default:
sizeof (int) // Gives size of int, i.e. 4. group = -1;
• Bitwise operators break;
}
– >>
Eg: a = b >> 1 //Shift b bitwise to the right by 1 bit. While while (expression )
Fill left most bits with the original left most bit. statement
– <<
For for (expr1; expr2; expr3)
Eg: a = b << n //Shift b bitwise to the left by n bits.
statement
Fill right most bits with zero.
This for loop is equivalent to:
Others: expr1;
& Bitwise AND while (expr2)
| Bitwise inclusive OR {
^ Bitwise EXOR statements;
~ Bitwise NOT expr3;
{
• Comma operator

– expr1,expr2 Do While do
Use sparingly, Eg: i++,j-- statement
while (expression );
– x = (Conditional expresion)? expr1 : expr2
x =expr1 if Conditional expression is true, else x = Break break : Exit the the loop or control.
expr2. Works for while, for, do while and switch

2
6. Functions 7. Pointers and arrays 7.6. Arrays and pointers
The following two are equivalent:
6.1. int main function: command line argu- 7.1. Pointers pa = &a[0]; pa = a;
ments Declaration type *ptr ;
a[i] *(a + i)
p[i] *(p + i)
main(int argc, char *argv[]) Eg: int *p; f(int arr[]) f(int *arr)
{ Initialization type *ptr = val ;
Legal Illegal
··· Eg: int *p = 0;
} Eg: int *p = NULL;// Null pointer. pa++ a++
argc Number of arguments including the program Eg: int *p = (int *) 100; pa[-1] a[-1]
name. NOTE: Casting is required for integer other than
argv[0] Pointer to program name. zero. Also, the above memory location may not be
7.7. Pointer to functions
NOTE: argv[0] represents name of the available. Eg:
compiled program and not the source file & Gives address. int sum f(int size, int arr[], int (*foo)(int )) // Definition.
and how it is called eg: [Link] vs ./[Link] Eg: ptr = &x; {
argv[i] Pointer to ith argument. * Dereferencing operator. int sum = 0;
argv[argc - 1] Pointer to last argument. Eg, *ptr refers to x. for (int i = 0; i < size; i++)
sum += (*foo)(arr[i]);
6.2. Function definition 7.2. Arrays }
Here foo is a pointer to a function and (*foo) is the function.
type function name (argument list ) • Character arrays sum f(size, arr, square) // [Link] of squares.
{ char s[100]; sum f(size, arr, cube) // [Link] of cubes.
statements s = "abc"; //ERROR. NOTE: Function names act as pointers to the function.
··· *s = "abc"; // OK.
return expression char s[] = {’a’,’b’,’c’};
} char s[] = "abc";
eg:
int foo(int num, int cars[],char *pn) • Integer, float arrays
{ int num[100]
statements num = {1,2,3} // ERROR
··· *num = {1,2,3} // ERROR
return expression int num[] = {1,2,3}
} float num[] = {1.0,2.0,3.0}

6.3. Function declaration 7.3. Character pointers

Implicit declaration:
Examples:
The function is assumed to return int. Nothing is assumed about the
char *pmessage;
arguments.
pmessage = "Hello, World!\n";
Explicit declaration:
printf("%s",pmessage); # Prints the string
Examples:
*pmessage refer to ’H’
int foo(int, int [], int *);
int foo(int x, int y[], int *p); 7.4. Pointer to pointers
Explicit declaration is not necessary if the function is defined before
main(). Examples:
int **p p is a pointer to a pointer to int
6.4. Passing functions as arguments *p is poiner to a pointer to int
Example: passing foo2 to foo. char *line[MAXLEN] line is a pointer to a character array.
Declaration:
int foo(int x, int (*foo2)(int y));
7.5. Multi-dimensional arrays
Usage: I think, multi-dimensional arrays can be thought of as pointers to
foo(x, foo2); pointers etc.
Also see:7.7 Pointers to functions Example:
Given: int a[2][3] = {{1,2,3},{4,5,6}}
The following are equivalent:
a[0][0] **a
a[1][1] *(*(a + 1) + 1)
Here a is a pointer to an array of pointers.

3
8. Structures, unions and typedefs 8.3. Union Using capture:
A union is a variable that may hold objects of different types and sizes. Lambda functions can also be stored in variables like the add in the
following example.
8.1. Structure The syntax is based on structures:
union u tag {
• Definition: int ival; #include <iostream>
struct point float fval;
{ char *sval; int main() {
int x; } u; int x = 10;
int y; For example, integer value of u can be accessed as: int y = 20;
}; [Link] auto add = [x, y]() -> int {
NOTE-1: Structure tag is optional?? return x + y;
NOTE-2: In C a function cannot be a member of a structure. 8.4. Bit fields int result = add();
Eg: };
• Declaration examples: }
struct {
unsigned int is keyword : 1;
– struct {· · · } a,b,c;
unsigned int is extern : 1;
unsigned int is static: 1;
– struct point {· · · } a,b,c;
} flags;
10. Bit operations
– struct point a,b,c This defines flags that contains three 1-bit fields.
The number following the colon represents the field width.
10.1. Builtin functions
– struct point *p; builtin clz Count leading zeros.
Namespace using namespace std;
With this statement standard library functions can be used without builtin ctz Count trailing zeros.
• Accessing members the prefix std:: builtin popcount Count number of ones.
a.x = 5; builtin parity Parity of number of ones.
printf("%d\n",a.x);
9. Lambda Functions Bit hacks
• Accessing members with pointer Format:
struct point *p = &a; [capture](parameters) -> return type {body}
The following are equivalent:
• Capture: Captures variable from the surrounding scope by
value or reference.
– p -> x;
Eg: [a,&b]
– (*p).x; • Parameters: Parameters of the function.
– a.x; Eg: (int a, int b)
Return type: Return type of the function.
• Arrays of structure:
struct points pts[100]; Examples
struct {· · · } pts[] = {{· · · },{· · · },· · · ,{· · · }}; Sorting in reverse order:
NOTE: In above assignment, in the RHS, elements within the
braces could be of different types matching the members of the sort([Link](), [Link](), [](int a, int b) -> bool {
structure. return a > b;
In case of simple members, each members need not be enclosed });
within braces.
Counting number of elements in a vector:

8.2. typedef int count = count_if([Link](), [Link](), [](int a) -> bool {

return a > 5;
enditemize });
• typedef int Length;
Length len, maxlen;
Length *length[];
typedef struct tnode *Treeptr;
typedef struct tree Treenode;
• The above examples could also be implemented by #define
The following can only be implemented by typedef:
typedef int (*PFI) (char*, char*);

4
11. Input output 11.5. printf and scanf Printf and variants
• int printf(char *format, arg1, arg2, · · · );
11.1. File Access Conversion formats for printf and scanf Print output to stdout.
Character Argument type; Printed as
Format: • int sprintf(char *string, char *format arg1, arg2, · · · );
FILE *fp; d,i int; decimal number
Print output to string.
FILE *fopen(char *name, char *mode); o int; unsigned octal number (without leading zero)
x,X int: unsigned hexadecimal number (without a leading • int fprintf(FILE *fp, char *format arg1, arg2, · · · );
int fclose(FILE *fp);
0x or 0X), using abcdef or ABCDEF. Print output to file pointed by the file pointer fp.
fp = fopen(name, mode);
Allowable modes include: u int; unsigned decimal number. Example:
"r" read. zu size t. printf("%s\n", string var);
"w" write. c int; single character. printf("%s", "hello, world");
"a" append. s char *; Print string, scan word. printf("square of n is %d\n", n square);
"b" binary files: "rb", "wb", "ab". NOTE: scanf reads only a word and not the entire
NOTE: Difference between rb and r etc: string.
While using just "r" might work in writing binary files, it might cause f double; [-][Link]. Scanf and variants
trouble due misinterpretation of special characters like LF and CR. e,E double; [-][Link]±xx, or [-][Link]±xx. • int scanf(char *format, arg1, arg2, · · · );
See: [Link] g,G double; %e or %E if exponent is < -4 or >= precision, Scan input from stdin.
else use %f. • int sscanf(char *string, char *format arg1, arg2, · · · );
Standard I/O p void *; pointer. Scan input from string.
Can be treated in the same way as file pointer. % no argument; Print %.
Between % and conversion character there may be in order: • int fscanf(FILE *fp, char *format arg1, arg2, · · · );
stdin, stdout, stderr Scan input from the file pointed by the file pointer fp.
• Minus sign: Left justification.
11.2. Reading and writing a file NOTE1: unlike printf, in scanf the variable are pointers.
size_t fread{const void* ptr, size_t size,/ • Number: Minimum field width. NOTE2: In scanf %s reads a word and not the entire string.
size_t count, FILE* stream}; • Period: Separates field width from precision. Also see: [Link]
Examples:
• Number: Precision. scanf("%d", &n);
size_ t fwrite{const void* ptr, size_t size,/
For float: number of digits after decimal. sscanf(string, "%d", &n);
size_t count, FILE* stream};
For int: minimum number of digits. fscanf(fp, "%d", &n);
For string: maximum number of characters to be printed.
11.3. Character I/O
• h: for short integer. l: for long integer. 11.6. cin and cout
getchar Takes input from standard input.
int getchar() cin Read input until space, or tab or LF.
Equivalent to getc(stdin) Formatting rules cout Output.
putchar Output to standard output. Examples
Wildcard NOTE:
int putchar(int)
%*d Here precision can be specified dynamically. Eg: • Use the following to increase speed ot I/O.
Equivalent to putc(c), stdout
printf("%*d", 6, foo);, this is equivalent to ios_base::sync_with_stdio(false);
getc int getc(FILE *fp), Eg: getc(stdin)
printf("%6d",foo); [Link](nullptr); [Link](nullptr);
putc int putc(int c, FILE *fp)
Integers • Use [Link]() after cin and before using getline.
ungetc
%d print as decimal integer.
11.4. Line I/O %6d print as decimal integer, at least 6 characters wide.
gets Reads until EOF. Floating point numbers 11.7. Miscellaneous
gets deletes terminal \n %6f print as floating point. int fflush(FILE *stream)
puts Writes line to stdout. %.2f print as floating point, 2 characters after decimal Causes any buffered but unwritten data to be written. The effect is
puts adds terminal \n point. undefined on an input stream.
fgets char *fgets(char *line, int maxline, FILE *fp) %6.2f print as floating point, at least 6 characters wide and int fclose(FILE *stream)
fputs int *fputs(char *line, FILE *fp) 2 characters after decimal point. Flushes any unwritten data for stream, discardes any unread buffered
getline Eg: getline(cin, s). Where s is a string. String: example hello, world (12 chars). input.
:%s: :hello, world:
NOTE: Never use gets :%10s: :hello, world:
gets does not check for buffer overrun, and keeps reading until :%.10s: :hello, wor:
it encouters new line or EOF. It has been used to break computer :%-10s: :hello, world:
security. :%.15s: :hello, world:
:%-15s: :hello, world :
:%15 .10s: : hello, wor:
:%-15 .10s: :hello, wor :

5
12. Libraries String ¡-¿ numbers 12.5. Algorithms
Usually in Linux, the library header files are stored in /usr/include
String to numbers Sort and search
NOTE: Use #include <bits/stdc++.h> to include all standard Search and sort from C
libraries. From C library int atoi(char *s). • void *bsearch(const void *key, const void *base,
Variants: atof, atol, atod size t n, size t size,
12.1. Character class tests: <cctype> From C++ library int stoi(string s, size t *p = 0, int base int (*cmp) (const void *keyal, const void *datum))
= 10). Searches base[0] · · · base[n-1] for key.
isalpha(c) Comparison function must return negative if its first argument
Variants: stol, stod, stof, stold
isupper(c) (search key) is less than its second argument (a table entry)
Eg:
islower(c) and so on.
isdigit(c)
isalnum(c) • qsort(void *base, size t n, size t size,
int n = stoi("1234"); // n = 1234.
isspace(c) true for ASCII codes: 9-13 & 32. int (*cmp)(const *void, const *void))
int n = stoi("12", 0, 16); // n = 18.
toupper(c) int n = stoi("A", 0, 16); // n = 10. Search and sort from C++
tolower(c)
Compare functions:
Number to string bool compare(x, y){
12.2. String functions: <cstring> return(x strictly precedes y)
strcat(s,t) Concatenate t to end of s }
to string Eg: string s = to string(1234);\\s = ”1234”.
strncat(s,t,n)
strcmp(s,t) In all the below, a could be an iterator or a pointer and all of them
strncmp(s,t,n) can use custom compare functions.
strcpy(s,t) Copy t to s
Memory management
• y = lower bound(a, a+n, x)
strncpy(s,t,n) • void *calloc(size t nobj, size t size) Returns an iterator to the first element whose value is ≥ x.
strlen(s) Return pointer to array of nobj of size size.
The space is initialized to 0. • y = upper bound(a, a+n, x)
strchr(s,c) Return pointer to first c
Returns an iterator to the first element whose value is > x.
strchr(s,c) Return pointer to last c
• void *malloc(size t size) • y = equal range(a, a+n, x)
Returns pointer to an object of size size. Returns a pair of iterators pointing to the upper bound and
12.3. Mathematical function: <cmath> The space is uninitialized. lower bound of x.
sin(x) • void *realloc(void *p, size t size) • y = equal range(a, a+n, x, compare function)
asin(x) Change size of the object pointed to by p to size. Returns a pair of iterators pointing to the upper bound and
hsin(x) Return pointer to new space. lower bound of x.
exp(x)
• sort(it1, it2, compare function);
log(x) • free (void *p)
log10(x) Deallocates space point to by p. • stable sort(it1, it2, compare function);
pow(x,y) xy • is sorted(it1, it2, compare function);
sqrt(x) • is sorted until(it1, it2, compare function);
ceil(x) Memory management in C++ Returns the iterator to the element until which the array is
floor(x) sorted.
abs(x) Abs. val. of x. Returns integers types. • void* operator new(size)
Eg: myClass* p1 = new myClass; • find if(start it, end it, func)
fabs(x) Absolute value of x. Returns double
myClass* p1 = new(sizeof(myClass)); Returns iterator to the first element in the range [start it,
frexp frexp(int x, int *exp). Returns significand (y) in
end it) for which func returns true.
the range [0.5, 1) and the stores the exponent in exp, • void delete(void* ptr)
such that x = y ∗ eexp • find if not(start it, end it, func)
Eg: delete p1; delete(p1); Returns iterator to the first element in the range [start it,
ldexp ldexp(double y, int exp). Inverse of frexp.
modf double modf(x, double *ip). Splits x into integer end it) for which func returns false.
and fractional parts. Returns the fractional part and
stores integer parts at ip.
limits Min Max
fmod(x,y) Floating point remainder of x/y with the same sign as Examples: • max(a, b, comp); min(a, b, comp);
x. • max({a1, a2, a3}, comp); min({a1, a2, a3}, comp);
• numeric limits<int>::min()
• max element(a, a+n, comp);
12.4. Utility Functions: <cstdlib> • numeric limits<int>::max() Returns the iterator for the largest element in a. If there are
multiple largest element, returns the iterator/pointer for the
system(char *s) • numeric limits<double>::min() first one.
Run system commands.
Eg: system("date") • numeric limits<double>::infinity() • min element(a, a+n, comp);

6
 Merge 13. Data structures 13.4. String
• merge(InputIterator F1, InputIterator L1, InputIterator A string is like a vector of characters.
F2, InputIterator L2, OutputIterator R); 13.1. Pair Definition:
Returns the iterator to the end of output. Eg: pair<int, int> x = 1,2; string s = "Hello";
NOTE: This operator does not allocate memory. The [Link] Returns 1. String operations:
OutputIterator R should point to a vector with sufficient [Link] Returns 2. a + b Concatenate.
memory to store the concatenated vector. [Link](t) append t to s.
• set intersection Arguments and output are the same as that 13.2. Tuple [Link](t) returns 0 if s == t, returns < 0 if s ≺ t,
for merge. Fixed length collection of heterogenous values. else returns > 0.
• set union Arguments and output are the same as that for Eg: tuple<int, string, double> t; [Link](start, len) Select a substring.
merge. Operations related to tuple [Link](str2) find first occurence of str2.
get<i> Return it h value of t. Eg: get<0>(t);. [Link](str2, pos) Find first occurence of str2 by searching
• set difference Arguments and output are the same as that for from the positon pos.
make tuple() Returns tuple out of individual values.
merge.
Eg: make tuple(5, "Paul", 23.4).
• set symmetric difference Arguments and output are the same tie() Unpacking tuple. 13.5. Set
as that for merge. Eg: Definition
tie(n, s, x) = t; set<type> s;
Hash Function tie(n, std::ignore, x) = t; multiset<type> s;
Can be used for custom types in unordered map and unordered set. unordered set<type> s;
13.3. Vectors unordered multiset<type, hasher> s;
Usage: hasher: Refer Custom Hash Function.
Definiton:
hash<T> hasher; Set operations
vector<T> v;
size t hasvalue = hasher(x);//Where x is an object of [Link](item);
Element access
type T operator[] [Link](item);
[Link]() Last element [Link](item);
[Link]() First element [Link](item); Returns the iterator that points to item.
Eg: Modifiers [Link]() Inserts elements in s.
[Link] back(5) Add 5 to the vector. Simillar to push in stack Eg: Insert elements from t to s.
hash<int> h; size_t x = h(10); data structure.
hash<string> h; size_t x = h("hello"); [Link]([Link](), [Link](), [Link]());
[Link]() Inserts elements / range in v. [Link]()
Custom hash function. Eg: Append u to v. Not availabe for unordered set and
Custom hash function for a user defined type can be defined as follows: [Link]([Link](), [Link](), [Link]()); unordered multiset.
[Link] [Link]{iterator pos, Args}. New element [Link] bound(x) Returns iterator to the smallest element that
class CustomHash { is constructed in place using Args and inserted
public: is larger than or equal to x.
at pos. [Link] bound(x) Returns iterator to the smallest element that
size_t operator () (const pair<string, string>& p) const { [Link] back [Link] back{Args}. New element is con-
hash<string> hasher; is larger than x.
structed in place using Args and inserted at the
auto h1 = hasher([Link]); NOTE: erase method remove all instances of the item in the multiset.
end.
auto h2 = hasher([Link]); IMPORTANT: Note the differences between
return h1 ^ h2; // Below for better heuristics. 13.6. Bit set
pushback, insert, emplace and emplaceback.
} [Link] back() Remove element on top of the stack. Definiton
}; [Link]() Remove element / range from v. bitset<size> s;
[Link]() Clears all the elements in v. Examples:
Heuristics to combine hash values.
Capacity bitset<5> s; bitset<5> s(string("1100110"));
h2 = h2 ^(h1 << 1); h2 ^= h2 + 0x9e3779b9 + (h1<<6) + (h1>>2);
[Link]() Returns the size of the vector. Operations on Bit set:
0x9e3779b9 is a prime number. a & b Bitwise AND.
See: [Link] [Link]() Current memory allocated to v in terms of
number of elements. a | b Bitwise OR.
[Link] size() Maximum memory available for v. a ^b Bitwise EXOR.
Others a Bitwise negation.
• swap(T& a, T&b); [Link]() Reserve a minimum size for v. Does not affect
[Link]().
• reverse(Iterator first, Iterator last); [Link] to fit() Shrink the capacity to fit the size.
13.7. Map
• next permutation([Link](), [Link]()); [Link]() Test if v is empty. map : Balanced binary tree.
• prev permutation([Link](), [Link]()); unordered map: Hash list.
tie Can be used to unpack a vector. Definition:
• random shuffle([Link](), [Link]()); Example: tie(a, b, c) = v; map<type1, type2> m;
Gives the next permutation for a given vector of integers. Eg: map<string, int> m;
unordered map<type1, type2, hasher> m;

7
hasher: Refer Custom Hash Function. 13.12. Priority queue
Operations on map Format:
m["banana"]
[Link]("banana")
Retrive value associated with banana.
Return 1 if the key is present else 0.
priority queue(type, vector<type>, compare) 14. Code snippets, etc.,
Max priority queue [Default]
[Link](); Eg: priority queue<int> q; 14.1. GCD:
Min priority queue
13.8. Stack priority queue<int, vector<int>, greater<int>> q; int gcd(int x, int y){
Eg: stack<int> s; [Link](3) return y ? gcd(y, x%y) : x;
[Link](5) [Link]() Returns the largest element. }
[Link]() [Link]() Removes the largest element.
[Link]()
Compare function for priority queues 14.2. Middle of an array
13.9. Queue class compare{ n: length of array
Eg: queue<int> q; public:
[Link](5) Adds element to the end. bool operator()(const T& x, const T& y) const {
return(x < y); // Max priority queue.
0-based indexing
[Link]() Removes first element. jnk
[Link]() Returns first element. // return(x > y); // Min priority queue. if n is odd:
[Link]() True if q is empty. } j2n k jnk
} if n is even: − 1 and
2 2
13.10. Dequeue
Eg: dequeue<int> d; 13.13. Iterators 1-based indexing
[Link] back(5) Add to the top. lnm
Iterators are like pointers but more specific to a collection. if n is odd:
[Link] front(2) Add to the bottom.
[Link] back() Remove from the top.
Not applicable for unordered set, unordered map and priority queue. l2n m lnm
if n is even: and +1
[Link] front() Remove from the bottom. 2 2
Example definition:
13.11. Heap vector<int>::iterator it; 14.3. Decimal to binary
set<string>::iterator it; int n;
Format:
Constructing a heap: cin >> n;
[Link]() Returns iterator pointing to the first element in the
auto a = bitset<64>(n);
make_heap(iterator f, iterator s); collection.
make_heap(iterator f, iterator s, comp); [Link]() Returns iterator pointing next to the last element in
the collection.
Iterating over a map: a[0] contains zeroth bit and so on.
pop_heap(iterator f, iterator s);
pop_heap(iterator f, iterator s, comp); Here *it is a pair of the key and value. Eg: pair<string, int> p =
*it;
push_heap(iterator f, iterator s); Eg:
push_heap(iterator f, iterator s, comp);
map<string, int>::iterator it = [Link]();
NOTE: // Accessing key and value
f points to the first element and s points next to the second element. string key = it->first;
f and s can be pointers when the heap is constructed over a array. int value = it->second;
Compare function:
Reverse Iterators
bool compare(x, y){
return(x < y); // For max heap 13.14. Representing graphs
return(x > y); // For min heap
} 13.15. Adjacency list
Eg:
vector<int> adj[N]// Unweighted graph.
vector<pair<int,int>> adj[N]// Weighted graph.

13.16. Adjacency matrix

Eg: int adj[N][N];

13.17. Edge list

Eg:
vector<pair<int,int>> edgesUnweighted graph.
vector<tuple<int,int,int>> edges // Weighted graph.
8
15. Previous Mistakes: 15.7. min element and max element 15.14. Error while using [Link]() as limit
Do not use these two functions to find minimum and maximum in a loop
15.1. Using proper variable types elements in an unsorted array. Read documentation to know more
[Link]() return a value of type size t which (probably) unsigned
Eg: using int instead of long long int would cause erroneous output. about them.
long long int. Therefore it inherits the same dangers associated with
15.2. Be careful of unsigned int 15.8. map vs multiset, NOT exactly a mis- using unsigned int(13.2). Eg: Here if [Link]() is zero, [Link]()-1 will
not return -1, rather it would return the largest long long.
Eg take
unsigned x; cin >> x; In one problem I used multiset to keep count of some values. It was for(int i = 0; i <= [Link]()-1; i++){}
while(x >= 0){ very slow compared to using map to keep count of those values. Probable a correct way to write the above code is as follows:
// Do something
} 15.9. Math errors for(int i = 0; i <= (int)[Link]()-1; i++){}
Division by zero and logarithm of zero. Another example:
The above will never terminate, since x never becomes negative. for(int i = [Link]()-2; i >=0; i++){}
15.3. Upper bound and lower bound 15.10. Not accessing out of bound elements Correct version.
Check for edge cases. While searching for x, if x is not found, then if(a[i] == 0) {do something;} // Wrong. int rl = [Link]();
lower bound points to an element larger than x. The following might for(int i = rl-2; i >=0; i++){}
if(i < n && a[i] == 0){do something;}// Correct.
be helpful.
15.11. Order of precedence and brackets 15.15. Loop condition dependent on
if(lower_bound > begin && *lower_bound > x) lower_bound--;
if(lower_bound == end) lower_bound--; Example:(CRF-732: 1546C) string::find
if(upper_bound == end) upper_bound--; // Might be Bugs could arise because string::find return -1 when the query is
if(l_pos[k] - l_pos[k-1] % 2 == 1){do something}// Wrong;
necessary sometimes. not found.
if((l_pos[k] - l_pos[k-1]) % 2 == 1){do something}// Correct;
Eg:
15.4. Loops 15.12. Using braces appropriately in condi- for(int i = 0; i < size; i++){
i = [Link](c, i);
• Using variable in boundary condition. Eg: tionals and loops //More code...
// value of x changes within the loop. Example:(CRF-732: 1546C) }
for(int i = 0; i < (d[x] - c); i++) // Dangerous !! Correct version:
// Wrong if do_2 depends on x :
if(x) do_1; for(int i = 0; i < size; i++){
k = d[x] - c;
do_2; i = [Link](c, i);
for(int i = 0; i < k; i++) //
if(i == -1) break;
• When the variable in boundary condition is updated by // Correct if do_2 depends on x : //More code...
mulitiplication. if(x){ do_1; }
In the following loop when n > 1 and a = 1, this loop won’t do_2;
terminate. }
15.16. Semicolon typo
int x = 1; Eg:
while(x < n){ 15.13. Errors due to 0-based and 1-based in-
x = a * x; dexing for(int i = 0; i < n; i++);{
} The data in most programming contests use 1-based indexing. Error cout << i << ’\n’;
could arise while reading or using such data. }
15.5. Bugs in compiler directives Eg:
In Bioinformatics contest 2021, a bug was because I use bitset<M>, In above code the for loop is prematurely terminated. This would
where M was specified as compiler directive. While debugging I did not for(int i = 0; i < n; i++){ result in runtime error.
pay attention to #define statements. int temp; cin >> temp;
Lesson: While debugging pay attention to the entire code, particularly a[temp]++; 15.17. Bugs due to using infinity
compiler directives. They are particulary important because they are } Eg:
hidden and not directly noticeable in the code.
Here if a is 0-based and input temp is 1-based, then error will arise.
The following is correct. const int inf = numerics::limits<int>max();
15.6. Bugs due to augmented data int x = inf;
Ref: ABC 207 problem C. There were two vectors, v and t associated for(int i = 0; i < n; i++){ cout << x + inf << ’\n’;
by index. The vector v[i] corresponds to t[i]. In this problem, I int temp; cin >> temp;
sorted v independently from t. Thus this broke the association a[temp-1]++; The output here would not be inf. I made a simillar mistake while
between v and t resulting in erroneous results. } using infinity in Floyd-Warshall’s algorithm.

9
15.18. No code after return 16. Variable nomenclature for com-
Once I made the following mistake:
petitive programming
return [Link](); [Link]();

Obviously, that [Link]() did not work.

15.19. Beware when using logical operators

with functions
The following is dangerous:

ans = ans && f(x);

If ans is initally false, f won’t be executed.

Better one would be (I am not sure if this always works with all
programming languages):
Category Symbols
ans = f(x) && ans;
Counter i, j, k; i1, i2
I made this mistake in LeetCode 130. Surrounded Regions.
Limits (h, l), (u, d), (l, r), (h1, l1)
15.20. Be careful with char vs int Integers n, m, k; n1, n2
Floats x, y, z, x1, x2
I made the following mistake: Element e: for(auto e: v)
Pair/points p, q, r, p1, p2
if(mat[i][j] == 1){ Pointer ptr; ptr1, ptr
// do something. String s; s1, s2
} Map mp; mp1, mp2
Vector a, b, c, u, v; u1, u2, v1, v2
Here mat was vector<vector<char>> I should have tested for Matrix mat, mat1, mat2
mat[i][j] == ’1’. Graph g, g1, g2
DP mat/vect dp; dp1, dp2
15.21. Be careful about pass by reference. Priority queue pq; pq1; pq2
Ref: A student’s code. Stack stk; stk1, stk2
Not using pass by reference resulted in failure in the update of value of Set set1, set2
the target. This caused issue in an implementation of linked-list. Temporary tmp; tmp1, tmp2

15.22. a = a + 1 vs a += 1 Using suffix

Ref: Discussion with a labmate. This is in the context of python Eg: Description
programming. a = a + 1 creates a new object and assigns it to a. a ai Element of a
+= 1 does not create a new object. It modifies the existing object. al Left limit element of a (or) Left limit ptr of a
ar Right limit element of a (or) Right limit ptr of a
15.23. Failure to initialize all the variables aptr Pointer to an element in a
Ref: A student’s code. ait Iterator to a
The student did not initialize all the variables. This resulted in a bug.
This was particularly critical because one of the class variable was a
pointer. This resulted in segmentation fault. It also cause TLE, but I
am not sure about the exact mechanism.

Using prefix

10
Eg: Description
na Number of elements in a
ma Map associated with a
sa Set associated with a
qa Queue or priority queue associated with a
ga Graph associated with a

11