C++11 memo (headers, APIs)

Posted on | In
| Words count in article 4673

using namespace std;

typedef vector<vector<int>> graph; typedef pair<int, int> pii;

According to https://www.geeksforgeeks.org/c-data-types/

char 1 byte (8 bits)

short int 2 bytes (16 bits)

int 4 bytes (32 bits)

unsigned int 4 bytes (32 bits)

long long int 8 bytes (64 bits)

float 4 bytes (32 bits)

double 8 bytes (64 bits)

INT_MIN, INT_MAX: #include <climits>

INT_MIN -2147483648 = - (2^31)

INT_MAX 2147483647 = (2^31) − 1; 2.15 * (10^9); 二十一亿四千七百四十八万三千六百四十七

65535 = (2^16) - 1; 六万五千五百三十五

1
2
3
4
5
6
#include <cfloat>

cout << FLT_MIN << endl; // 1.17549e-38
cout << FLT_MAX << endl; // 3.40282e+38
cout << DBL_MIN << endl; // 2.22507e-308
cout << DBL_MAX << endl; // 1.79769e+308

FLT_MIN 等 属于<cfloat>，不属于<climits>。

numeric_limits<int>::min(), numeric_limits<int>::max(): #include <limits>

numeric_limits<int>::min() 同 INT_MIN

numeric_limits<int>::max() 同 INT_MAX

numeric_limits<float>::min() 同 FLT_MIN

numeric_limits<double>::min() 同 DBL_MIN

INT_MIN 等 属于<climits>，不属于<limits>。

numeric_limits<int>::min() 等 属于<limits>，不属于<climits>。

memset: #include <cstring>

1
2
3
4
int a[5]; 
   
// all elements of A are zero 
memset(a, 0, sizeof(a));

According to https://www.geeksforgeeks.org/memset-in-cpp/

We can use memset() to set all values as 0 or -1 for integral data types also. It will not work if we use it to set as other values. The reason is simple, memset works byte by byte.

fill_n: #include <algorithm>

1
2
3
4
5
#include <algorithm>    // std::fill_n
#include <vector>       // std::vector

std::vector<int> myvector (8, 10);        // myvector: 10 10 10 10 10 10 10 10
std::fill_n (myvector.begin(), 4, 20);     // myvector: 20 20 20 20 10 10 10 10

cout: #include <iostream> cin: #include<iostream> scanf: #include<iostream> printf: #include<iostream>

priority_queue: #include <queue>

empty(), size(), top(), push(), pop()

1
2
3
4
int myints[]= {10,60,50,20};
std::priority_queue<int> first;
std::priority_queue<int> second (myints,myints+4);
std::priority_queue<int, std::vector<int>, std::greater<int> > third (myints,myints+4);

In C++, the default STL (Standard Template Library) priority queue is Max priority queue (returns the largest element). Using greater as comparison function to get Min priority queue, like:

priority_queue<int, vector<int>, greater<int> >pq;

To use lambda expressions:

1
2
3
4
5
6
7
// Max priority queue, similar to "priority_queue<int> pq;"
auto cmp = [](ListNode* a, ListNode* b){return a->val < b->val;};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> max_pq(cmp);

// Min priority queue, similar to "priority_queue<int, vector<int>, greater<int>> pq;"
auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val;};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> min_pq(cmp);

queue: #include <queue>

empty(), size(), front(), back(), push(), pop()

stack: #include <stack> empty(), size(), top(), push(), pop()

vector: #include <vector> size(), empty(), front(), back(), push_back(), pop_back()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// Returns an iterator pointing to the first element in the vector.
begin()

// Returns an iterator referring to the past-the-end element in the vector container. 
// The past-the-end element is the theoretical element that would follow the last element 
// in the vector. It does not point to any element, and thus shall not be dereferenced.
end() 

// the maximum number of elements that the vector can hold.
// This is the maximum potential size the container can reach due to 
// known system or library implementation limitations, but the container 
// is by no means guaranteed to be able to reach that size: it can still 
// fail to allocate storage at any point before that size is reached.
max_size()

// Resizes the container so that it contains n elements.
resize()

// Returns the size of the storage space currently allocated for the vector, expressed in terms of elements.
// This capacity is not necessarily equal to the vector size. It can be equal or greater, with the extra space 
// allowing to accommodate for growth without the need to reallocate on each insertion.
capacity()

// Requests that the vector capacity be at least enough to contain n elements.
reserve() 

// Returns a reference to the element at position n in the vector container.
[] 

// Returns a reference to the element at position n in the vector. 
// It automatically checks whether n is within the bounds of valid elements in the vector, 
//throwing an out_of_range exception if it is not
at() 

clear() // Removes all elements from the vector (which are destroyed), leaving the container with a size of 0.

// The vector is extended by inserting new elements before the element at the specified position, 
// effectively increasing the container size by the number of elements inserted.
// Because vectors use an array as their underlying storage, inserting elements in positions other 
// than the vector end causes the container to relocate all the elements that were after position to 
// their new positions. This is generally an inefficient operation compared to the one performed for 
// the same operation by other kinds of sequence containers (such as list or forward_list).
insert()

std::vector<int> myvector (3,100);
std::vector<int>::iterator it;
it = myvector.begin();
it = myvector.insert ( it , 200 );

// Removes from the vector either a single element (position) or a range of elements ([first,last)).
// Because vectors use an array as their underlying storage, erasing elements in positions other than the 
// vector end causes the container to relocate all the elements after the segment erased to their new positions. 
// This is generally an inefficient operation compared to the one performed for the same operation by other kinds 
// of sequence containers (such as list or forward_list).
erase() 

// erase the 6th element
myvector.erase (myvector.begin()+5);

// erase the first 3 elements:
myvector.erase (myvector.begin(), myvector.begin()+3);

Doubly-linked lists

list: #include <list>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
begin(), end() // iterators
empty(), size(), max_size(), front(), back(), push_front(), pop_front(), push_back(), pop_back(), resize(), clear()

insert()

std::list<int> mylist;
std::list<int>::iterator it;
// set some initial values:
for (int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5
it = mylist.begin();
++it;       // it points now to number 2           ^
mylist.insert (it,10);                        // 1 10 2 3 4 5


erase()

int main ()
{
  std::list<int> mylist;
  std::list<int>::iterator it1,it2;

  // set some values:
  for (int i=1; i<10; ++i) mylist.push_back(i*10);

                              // 10 20 30 40 50 60 70 80 90
  it1 = it2 = mylist.begin(); // ^^
  advance (it2,6);            // ^                 ^
  ++it1;                      //    ^              ^

  it1 = mylist.erase (it1);   // 10 30 40 50 60 70 80 90
                              //    ^           ^

  it2 = mylist.erase (it2);   // 10 30 40 50 60 80 90
                              //    ^           ^

  ++it1;                      //       ^        ^
  --it2;                      //       ^     ^

  mylist.erase (it1,it2);     // 10 30 60 80 90
                              //        ^

  return 0;
}

Singly-linked lists forward_list: #include <forward_list>

1
2
begin(), end() // iterators
empty(), max_size(), front(), push_front(), pop_front(), insert_after(), erase_after(), resize(), clear()

pair: #include <utility> // std::pair, std::make_pair

1
2
3
4
5
6
std::pair <std::string, double> product1;                     // default constructor
std::pair <std::string, double> product2 ("tomatoes", 2.30);   // value init
std::pair <std::string, double> product3 (product2);          // copy constructor
product1 = std::make_pair(std::string("lightbulbs"), 0.99);   // using make_pair (move)
product2.first = "shoes";                  // the type of first is string
product2.second = 39.90;                   // the type of second is double

Sets are typically implemented as binary search trees. set: #include <set> begin(), end(), empty(), size(), max_size(), clear()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
insert()
std::set<int> myset;
for (int i=1; i<=5; ++i) myset.insert(i*10);    // set: 10 20 30 40 50

erase()
std::set<int> myset;
myset.erase (40);
for(int i=1; i<10; i++) myset.insert(i*10);  // 10 20 30 40 50 60 70 80 90

find()
std::set<int> myset;
std::set<int>::iterator it;
for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50
myset.erase (myset.find(40));

count()
if (myset.count(x)) {... // x is in the set, count is 1 } 
else {... // count zero, i.e. x not in the set }

unordered_set: #include <unordered_set> begin(), end(), find(), count(), insert(), erase(), clear()

Maps are typically implemented as binary search trees. map: #include <map> empty(), size(), max_size(), [], at(), insert(), erase(), clear(), find(), count()

[]: If k matches the key of an element in the container, the function returns a reference to its mapped value. If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

unordered_map: #include <unordered_map> begin(), end(), [], at(), find(), count(), insert(), erase(), clear()

library 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <algorithm>

find()
// using std::find with array and pointer:
int myints[] = { 10, 20, 30, 40 };
int * p;
p = std::find (myints, myints+4, 30);
if (p != myints+4) std::cout << "Element found in myints: " << *p << '\n';
else std::cout << "Element not found in myints\n";

count()
int myints[] = {10,20,30,30,20,10,10,20};   // 8 elements
int mycount = std::count (myints, myints+8, 10);
std::cout << "10 appears " << mycount << " times.\n";

swap()
#include <algorithm>    // std::swap
int x=10, y=20;                              // x:10 y:20
std::swap(x,y);                              // x:20 y:10
std::vector<int> foo (4,x), bar (6,y);       // foo:4x20 bar:6x10
std::swap(foo,bar);                          // foo:6x10 bar:4x20

reverse()
std::reverse(myvector.begin(),myvector.end());

rotate()
std::vector<int> myvector;
for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::rotate(myvector.begin(),myvector.begin()+3,myvector.end()); // 4 5 6 7 8 9 1 2 3

random_shuffle() 
// using built-in random generator:
std::random_shuffle ( myvector.begin(), myvector.end() );

sort()
sort(myvector.begin(), myvector.begin()+4);
bool myfunction (int i,int j) { return (i<j); }
std::sort (myvector.begin()+4, myvector.end(), myfunction);

stable_sort()
std::stable_sort (myvector.begin(), myvector.end());

is_sorted()
std::is_sorted(foo.begin(),foo.end())

lower_bound(), upper_bound()
int myints[] = {10,20,30,30,20,10,10,20};
std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30
std::vector<int>::iterator low,up;
low=std::lower_bound (v.begin(), v.end(), 20); //          ^
up= std::upper_bound (v.begin(), v.end(), 20); //                   ^
std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

binary_search()
int myints[] = {1,2,3,4,5,4,3,2,1};
std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1
std::sort (v.begin(), v.end());
std::cout << "looking for a 3... ";
if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!\n"; 
    else std::cout << "not found.\n";
    
merge()
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10);
std::sort (first,first+5);
std::sort (second,second+5);
std::merge (first,first+5,second,second+5,v.begin());
std::cout << "The resulting vector contains:";
for (std::vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
std::cout << '\n';

make_heap()
int myints[] = {10,20,30,5,15};
std::vector<int> v(myints,myints+5);
std::make_heap (v.begin(),v.end());
std::cout << "initial max heap   : " << v.front() << '\n'; // 30

min(), max()
std::cout << "min(1,2)==" << std::min(1,2) << '\n';
std::cout << "max(1,2)==" << std::max(1,2) << '\n';
  
// Returns an iterator pointing to the element with the smallest value in the range [first,last).
min_element(), max_element()
int myints[] = {3,7,2,5,6,4,9};
std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';
std::cout << "The largest element is "  << *std::max_element(myints,myints+7) << '\n';

lexicographical_compare() 
char foo[]="Apple";
char bar[]="apartment";
std::cout << std::lexicographical_compare(foo,foo+5,bar,bar+9); // true

next_permutation()
// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort
int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

prev_permutation()
#include <iostream>     // std::cout
#include <algorithm> 
int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);
  std::reverse (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::prev_permutation(myints,myints+3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

less<T>(): #include <functional>

1
2
int foo[]={10,20,5,15,25};
std::sort (foo, foo+5, std::less<int>());  // 5 10 15 20 25

greater<T>(): #include <functional>

1
2
int numbers[]={20,40,50,10,30};
std::sort (numbers, numbers+5, std::greater<int>());

string: #include <string>

1
2
3
4
5
6
int main ()
{
  std::string str ("Test string");
  std::cout << "The size of str is " << str.length() << " bytes.\n";
  return 0;
}

Lambda function in C++11

1
2
vector<int> vec = { 1,2,3,4,5,6,7,8,9 }; // 1 2 3 4 5 6 7 8 9 
sort(vec.begin(), vec.end(), [](int a, int b){return a > b;}); // 9 8 7 6 5 4 3 2 1

Macro definitions: #define

#define TABLE_SIZE 100 #define int32 uint32_t

const int MAXN = 21;

bool adj[MAXN][MAXN]; bool visited[51];

C++ coding competition style IO:

1
2
3
typedef long long ll;
ll N;
scanf("%lld", & N);

1
2
3
4
5
6
7
int scanf_ret, T;
int a[5];
while(true){
  scanf_ret = scanf("%d", &T);
  if(scanf_ret == EOF) break;
  for(int i = 0; i < 5; i++) scanf("%d", &a[i]);
}

1
2
3
4
scanf("%c", &c); // reads one character, won't ignore leading whitespace
scanf(" %c", &c); // The blank in the format string tells scanf to skip leading whitespace
printf("c = %c\n", c);
putchar('\n'); 

1
2
3
int T;
scanf("%d", &T);
printf("Network %d: %s\n\n", T, "DISD");

rand()

Returns a pseudo-random integral number in the range between 0 and RAND_MAX.

RAND_MAX is a constant defined in <cstdlib>. Test with http://cpp.sh/ shows that: cout << RAND_MAX << endl; // 2147483647

1
2
3
v1 = rand() % 100;         // v1 in the range 0 to 99
v2 = rand() % 100 + 1;     // v2 in the range 1 to 100
v3 = rand() % 30 + 1985;   // v3 in the range 1985-2014

According to https://stackoverflow.com/questions/35910043/why-does-rand-compile-without-including-cstdlib-or-using-namespace-std :

rand() is defined in <cstdlib>. However, standard library header files may include other standard library header files. So iostream may include cstdlib directly or indirectly. In practice, it suffices to use #include<iostream>.

Header files with C-standard library equivalents (e.g. cstdlib) are allowed to bring C standard library names into the global namespace, that is, outside of the std namespace (e.g. rand) This is formally allowed since C++11, and was largely tolerated before.

abs()

abs() is defined in <cmath>. However, in practice, it suffices to use #include<iostream>.

Library bitset

1
2
3
4
5
6
7
8
9
#include <iostream>       // std::cout
#include <bitset>         // std::bitset
int main (){
  std::bitset<4> foo; // 4 bits init to 0 
  foo[1]=1;             // 0010
  foo[2]=foo[1];        // 0110
  std::cout << "foo: " << foo << '\n'; // foo: 0110 
  return 0;
}

Modulo 10^9+7 (1000000007):

https://www.geeksforgeeks.org/modulo-1097-1000000007/

  • prevent integer overflows
  • In some of the problems, to compute the result modulo inverse is needed and this number helps a lot because it is prime.

A few distributive properties of modulo are as follows:

  • ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
  • ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
  • ( a – b) % c = ( ( a % c ) – ( b % c ) ) % c

( a / b ) % c = ( ( a % c ) / ( b % c ) ) % c is not true!!!!

struct in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct TreeNode {
      int val;
      TreeNode* left;
      TreeNode* right;
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 };

struct Tuple{
    TreeNode* node;
    int a, id;
    Tuple(int id, TreeNode* node, int a): id(id), node(node), a(a){}
};

struct Student{
    int id, grade;
    Student(int id, int grade): id(id), grade(grade){}
    
    bool operator<(Student other){
        return grade < other.grade;
    }
};

int main(){
    Tuple t1(1, new TreeNode(0), 10);
    Tuple* t2 = new Tuple(2, new TreeNode(5), 25);
    vector<Tuple> v = {t1, *t2, Tuple(3, new TreeNode(7), 15)};
    for(auto e: v) cout << e.id << ", "; cout << endl; // 1, 2, 3, 
    sort(v.begin(), v.end(), [](Tuple t1, Tuple t2){return t1.a < t2.a;});
    for(auto e: v) cout << e.id << ", "; cout << endl; // 1, 3, 2, 
    
    Student s1(1, 56);
    vector<Student> vv = {s1, Student(2, 30), Student(3, 99)};
    for(auto e: vv) cout << e.id << ", "; cout << endl; // 1, 2, 3,  
    sort(vv.begin(), vv.end());
    for(auto e: vv) cout << e.id << ", "; cout << endl; // 2, 1, 3, 
}

Array in C++ (raw array, as opposed to STL std::array in <array>)

1
2
3
4
int a[5];
int b[5] = {16, 2, 77, 40, 12071}; 
int c[] = {4, 57, 9, 2};
int d[]{10, 20, 30};

Compiler uses pointer arithmetic to access array element, arr[i] is treated as *(arr + i) by the compiler. However, array and pointer are two different things in general.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int arr[] = {10, 20, 30, 40, 50, 60}; 
int *ptr = arr; 

cout << arr[2] << endl;    // 30
cout << *(arr + 2)<< endl; // 30
cout << ptr[2]<< endl;     // 30
cout << *(ptr + 2)<< endl; // 30

// sizof(int) * (number of element in arr[]) is printed 
cout << sizeof(arr) << endl; // 24

// sizeof a pointer is printed which is same for all type  
// of pointers (char *, void *, etc) 
cout << sizeof(ptr) << endl; // 8

hash: #include <functional>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char a[] = "test";
string b(a);
int c = 0, d = 1, e = 100, f = - 23;
float g = 17.5;
double h = 17.5;

std::hash<char*> hashc;
std::hash<string> hashs;
std::hash<int> hashi;
std::hash<float> hashf;
std::hash<double> hashd;

cout << hashc(a) << endl; // 140723202892979
cout << hashs(a) << endl; // 15118982290295364091
cout << hashi(c) << endl; // 0
cout << hashi(d) << endl; // 1
cout << hashi(e) << endl; // 100
cout << hashi(f) << endl; // 18446744073709551593
cout << hashf(g) << endl; // 3757725912424151043  
cout << hashd(h) << endl; // 4693821169703498693

To create an unordered_map of user-defined class in C++:

  • implement const method operator== in the user-defined class
  • create a struct/class that contains const method operator()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Coordinate {
    int x, y;
    
    bool operator==(Coordinate other) const{
        return x == other.x && y == other.y;
    }
};

struct myHash{
    size_t operator()(Coordinate c) const{
      return std::hash<int>()(c.x + 1000 + c.y);
    }
};

int main(){
    unordered_map<Coordinate, Coordinate, myHash> pred;
    unordered_map<Coordinate, bool, myHash> used;
    
    Coordinate c{0, 1};
    cout << used[c] << endl; // 0
    used[c] = true;
    cout << used[c] << endl; // 1
}

1
2
3
4
5
6
7
8
9
enum Color{white, black, red, green, blue};

int main(){
    cout << white << endl; // 0
    cout << black << endl; // 1
    
    Color g = green;
    cout << g << endl; // 3
}

numeric_limits<double>::epsilon():

Machine epsilon (the difference between 1 and the least value greater than 1 that is representable). See also FLT_EPSILON, DBL_EPSILON.

1
2
3
4
5
6
7
8
9
10
double SquareRoot(double x) {
    double l = 1, r = x, m = 0;
    if(x < 1) swap(l, r);
    while( (r - l) / max( abs(l), abs(r) ) > numeric_limits<double>::epsilon() ){
      m = l + (r - l) / 2;
      if(m * m <= x) l = m;
      else r = m;
    }
    return l;
}