C++ notes (for placement)

c++_notes.txt

1. std::set is a sorted container
		set<int> S;
		S.insert(1);
		S.insert(3);
		S.insert(2);
		
		auto I = S.find(2); // Returns an iterator
		assert(*(I - 1) == 1);
		assert(*(I + 1) == 3);

2. To reverse a std::vector V, use std::reverse:
		reverse(V.begin(), V.end())

3. To create a std::vector of size N, use:
		vector<int> v(N)
   To initialize (perhaps to zero) at the same time:
		vector<int> v(N, 0)

4. TODO: Remember code for bitwise log2, etc. from nlib

5. To convert integer i to std::string, use std::to_string as:
		string str = to_string(i)
   To convert std::string str to integer, use std::stoi as:
        int i = stoi(str)

6. To sort a std::vector<T> V, use std::sort:
		sort(V.begin(), V.end(), comparator)
   where the optional comparator function has 
   the signature:
		 bool cmp(const T &a, const T &b);
   and returns true iff a < b.
   
   All characters inside a std::string S can also be sorted
   using:
	sort(S.begin(), S.end());

7. Lambda functions can be used as comparator function in std::sort as:
		sort(V.begin(), V.end(), [&](int i,int j){return A[i]<A[j];} );

8. To append std::string B to A, use string::append:
		A = A.append(B); // or
		A = A + B
	To add a single character, use string:push_back:
		A.push_back('a');

9. To get a substring from index i to j inclusive, use std::string::substr as:
		string A = "Hello!";
		string B = A.substr(1, 3);
		assert(B == "ell");

10. To fill a std::vector V from i to (i+V.size()-1), use std::iota as:
		iota(V.begin(), V.end(), i);
	std::iota can be found in <numeric>

11. Following is a table of different types of iterators:

        Category          Ability                           Providers
        ----------------- --------------------------------- ----------------------------
		None ............ N/A ............................. stack, queue, priority_queue
        Input  .......... Reads forward   ................. istream
        Output .......... Writes forward  ................. ostream, inserter
        Forward ......... Reads/writes forward  ........... forward_list,
                                                            unordered_[multi]set,
                                                            unordered_[multi]map
        Bidirectional ... Reads/writes forward/backward ... list, [multi]set, [multi]map
        Random access ... Reads/writes with random access . vector, deque, string, array

	and following is the list of operations allowed on those iterators:

        Expression                                Iterators
        ----------                                ---------------------------
    	auto it1 = it2             .............. All
    	++it, it++                 .............. All
    	it1 == it2, it1 != it2     .............. Input,  Forward, BiDi, RA
    	*it, it->m                 .............. Input,  Forward, BiDi, RA
    	*it = val, *it++ = val     .............. Output, Forward, BiDi, RA
    	Multipass { it2=it1; *it1++; *it2; }  ... Forward, BiDi, RA
    	--it                       .............. BiDi, RA
    	it--                       .............. BiDi, RA
    	*it--                      .............. BiDi, RA
    	it ± n, n ± it             .............. RA
    	it1 <>≤≥ it2               .............. RA
    	it1 += n, it1 -= n         .............. RA
	    a[n]                       .............. RA

12. To binary search between two iterators, use std::binary_search as:
	bool binary_search (ForwardIterator first, ForwardIterator last,
						const T& val, __Optional__ Compare comp);

13. To get the first element >= Value in [first, last), use std::lower_bound as:
		ForwardIt lower_bound(ForwardIt first, ForwardIt last, 
							  const T& Value, __Optional__ Compare comp);

14. An iterator based syntax for "for" loops is:
		for (auto& it: B) { /* ... */ }
	where B is a data structure that supports B.begin()

15. std::pair:
		pair<string, int> p = {one, 1};
		cout << p.first << " " << p.second << endl;

16. For hash table, use std::unordered_map:
		unordered_map<string, int> um;
		cache["five"] = 5;
		cache["ten"] = 10;
		cache["fifteen"] = 15;
		
		for (auto &i : cache) {
			cout << i.first << " " << i.second << endl;
		}

		auto t = cache.find("one");
		if (t != cache.end()) {
			cout << t->first << " " << t->second << endl;
		}


17: To convert a std::string to std::vector:
		std::vector<char> vec(str.begin(), str.end()); 
	To convert a std::vector to std::string:
		std::vector<char> vec;
		//... do something with vec
		std::string str(vec.begin(), vec.end());

18. To find nth bit of a integer num, use:
		((num >> n) & 1)

19. To count number of bits in a integer num, use:

		int count = 0;
		while(num != 0) {
			n = num & (num - 1);
			count++;
		}
	
	Each iteration decrements the value in such a way that the least significant bit
	that is set to 1 disappears. This happens because subtraction by 1 leads to
	all ending 0s turning to 1s, until the last 1 which becomes a 0. ANDing it with
	the number then flips that last 1 to a zero.

20. To find Hamming Distance between a and b, first calculate a^b (XOR) which
	gives a number that has all differing bits set. Then, use the above algorithm
	to count the number of bits.
	
21. To store two numbers in one variable/array slot, use the following trick 
	made possible by the integer arithmetic:
	
		(a + b*n)/n = b
		(a + b*n)%n = a
			(given that a,b < n)

22. To detect overflow in multiplication (x, a & b need to be unsigned, to prevent UB):
		x = a * b;
		if (a != 0 && x / a != b) {
			// overflow handling
		}		

23. https://en.cppreference.com/w/cpp/algorithm/swap

24. https://en.cppreference.com/w/cpp/string/basic_string/erase

25. Fibonacci Calculation (check out Methods >=4):
	https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/