C++

tricky trickeries

• set objects are const! if need to edit an element of a set, you have to delete+insert again. really.
• if a class contains a pointer, when copied with the default behavior, the pointer is copied but that means it points to the same data. If needed, overload operator= / copy constructor
• object you insert in a set/map require operator< to be present (if map, for the key)
  • so if they're eg objects identified by id or string, overload it with bool operator<(const Obj& o) const { return this->id < o.id; }
  • vectors have (lexicographical) ordering! (operator<, etc.) - so they can be used as keys without overloading.
  • unordered_* instead need operator==
• explicit: in constructors, use to prevent implicit type-conversion.

<random>

cast (convert types)

number in argv? string2integer

file

• copy file content to vector

  std::vector<double> v; std::ifstream f(vector_file_name); v.read(f); f.close();

• read file piece by piece (istringstream / getline):

  // simple example with a function that splits string into a vector of words vector<string> split(const string& s, char d=’,’) { string word; vector<string> v; std::istringstream iss(s); while(std::getline(iss, word, d)) v.push_back(word); return v; }

operator overload

• if an operator receives as input objects of the same class (eg. operator* between two classes) it must be declared outside the class itself (right below), i.e. as an helper function, not a member function.
• When overriding operator< (eg for sets, maps), remember to also check the == case! (in which you would likely want to order by another class member)

init vars

• vector

  std::vector<string> v{'a','b','b'}; // ['a','b','b'] std::vector<string> v(3,'x'); // ['x','x','x'] std::vector<string> v(3); // it's long 3 but slots uninitialized std::vector<string> v2(v.cbegin(),v.cend()); // copy of v

• string: must specify what to fill in, cannot just tell size.

  std::string s(5,'x'); // 'xxxxx' std::string s('abcde'); // 'abcde' std::string s2(s,2); // 'c' (only the third char!! there's no rep like vectors) std::string s3(s,0,3); // 'abc' (first 3 chars of s) std::string s4 = s2 + s3; // 'cabc' (string join like python yay!)

• map empty init:

  myMap[key]; // equivalent to myMap[key] = std::map<T1,T2>();

• make pair: two alternatives (first is more precise with types)

  myMap.insert(std::pair<int, myClass>(num,T)); myMap.insert(std::make_pair(num, T));

• class:

  // init by constructor: Post newpost(date,content); // call constructor from another constructor: Matrix::Matrix(..r, ..c) : rows(r), cols(c) {}; Matrix::Matrix(..r, ..c, ..d) : Matrix(r,c)**, data(d) {}; // in a class method, create a class copy of itself: Matrix M2 = *this;

• init set of strings / convert vector to set [#TODO check] (splitWords() (same as split()) is given in "utilities.h", returns vector of strings)

  vector<string> v( split(text,' ') ); set<string> words(v.cbegin(), v.cend()); // or by copy: words = set<string>(v.cbegin(), v.cend());

• static variable: preserves its value even when out of scope! Like God variables. It cannot be re-initialized. Useful for (very)global counters!

  int fun() { static int count = 0; // the variable is declared + initialized to 0 inside the function count++; // but still increases to 1,2,3 every single time you call fun()! return count; } int main() { std::cout << fun() << “, “ << fun() << “, “ << fun() << std::endl; return 0; } // Output: 1 2 3 (I know right? wow)

• global counter

  // .h class myClass { static unsigned counter; ... } // .cpp unsigned myClass::counter = 1;

upper/lower_bound

reserve vs resize

• .resize() will modify both capacity and size (extra values get default-init, expensive)
• .reserve() will only modify capacity (extra values not initialized)

insert vs emplace

TL;DR emplace is much more efficient for containers, since it avoids copying the big boi

.insert() - a map is made of pairs, so the usual .insert() adds to the container the kind of element it contains (in case of a map, the pair). But with .insert() you first create the pair, and then it's copied to the container. If it’s a big object, this might be a problem.

.emplace() - a more modern and efficient method is to use .emplace(), which instead creates already in-place the object: instead of getting a source from which to copy into the container, .emplace() takes the parameters that will be forwarded to the constructor of the object stored in the container!

Pointers

Raw Pointers: basic pointer work

Shared Pointers:

• what? Basically a wrapper class over a (raw)pointer with an operator like * and -> overloaded. The objects of the smart pointer class look like normal pointers - but, unlike them, it can deallocate and free destroyed object memory. (no need to call delete ptr, out of scope it auto deletes itself+obj, see motivation below) - unique_ptr<T>, shared_ptr<T>

• motivation: when p goes out of scope, it gets deleted together with the object it refers to!

• Now that you're motivated (right?), here's all you need to play

• keep in mind that implicit conversion from int* to shared_ptr<int> (pointer to smartpointer) is not possible. -> so:
  • use raw pointers if you need to store addresses
  • use smart pointers if you want a new dynamic variable

Complexity

Full detailed list of complexities here, here's just a super strict recap in a different format, including the difference between average and worst case complexities, when it's different.

Data Structure choosing:

Misc

• pro knowledge tips

  • The STL queue is a container adaptor. That is, it is not a "first-class" container, but instead simply "adapts" one of the sequential first-class containers (by default, the deque) for its own purposes. So, the deque interface is restricted (i.e., much of it is hidden) so that the required FIFO queue-like behavior is provided.
  • std::deque: internally built on top of a vector storing pointers to blocks of the same size. Elements are never reallocated.
  • std::vector: internally stores a pointer to a block of contiguous elements, with its number and the number of used elements
  • std::unordered_map: the very worst case is when all elements have the same hash value for their keys (so complexity O(n))

• map rangefor - remember this! so useful and intuitive

  for (const auto& pair : myMap) std::cout << pair.first << " has value " << pair.second << std::endl;
  While with iterators it would be:
  for (const auto pairit=myMap.cbegin(); pairit!=myMap.cend(); pairit++) std::cout << pairit->first << " has value " << pairit->second << std::endl;