vector

notes

iterator

• Input Iterator : utilisés pour lire !=, ++, *
  
• Output Iterator : utilisés pour écrire dans un container
  
• Forward Iterator : est un InputIterator et un OutputIterator
  
• Bidirectional Iterator : est un ForwardIterator mais qui peut se déplacer dans les deux directions (début à la fin ou de la fin vers le début)
  
• Random Access Iterator Il peut être vu comme un pointeur sur un élément d'un container et utilise des fonctions comme :

operator* : retourne l'élément pointé par l'itérateur
operator++ : permet de passer à l'élément suivant
operator== et operator!= permet de comparer deux itérateurs et s'ils pointent sur le même élément
Chaque container possède 4 fonctions à utiliser avec les itérateurs :

begin() : retourne un pointeur sur le premier élément du container
end() : retourne un pointeur situé après le dernier élément du container
cbegin() : comme begin() mais constant (read-only)
cend() :comme end() mais constant (read-only)
Chaque container possède au moins 2 types d'itérateurs :

container::iterator : itérateur (read/write)
container::const_iterator() : itérateur (read-only)

initializtion

types

• Value initialization, e.g. std::string s{};
  
• Direct initialization, e.g. std::string s("hello");
  
• Copy initialization, e.g. std::string s = "hello";
  
• List initialization, e.g. std::string s{'a', 'b', 'c'};
  
• Aggregate initialization, e.g. char a[3] = {'a', 'b'};
  
• Reference initialization, e.g. char& c = a[0];
  

Copy initialization

• Copy-initialization is less permissive than direct-initialization: explicit constructors are not converting constructors and are not considered for copy-initialization.
  

struct Exp { explicit Exp(const char*) {} }; // not convertible from const char*
Exp e1("abc");  // OK
Exp e2 = "abc"; // Error, copy-initialization does not consider explicit constructor
 
struct Imp { Imp(const char*) {} }; // convertible from const char*
Imp i1("abc");  // OK
Imp i2 = "abc"; // OK

SFINAE (Substitution Failure Is Not An Error) source

• means that when compiler try to substitute types in declaration of a function template, and this substitution fails, this is not considered an error, the compiler try to find another templates, to make the substitution, if he doens't succeed then it's an error.
• this can be used when you want to define a function of specific type for example, integral return defined function

template <bool B, typename T = void>
struct my_if 
{
};
template <typename T>
struct my_if<true,T> 
{
 typedef T type;
};

template <typename T>
typename my_if<std::is_integral<T>::value,T>::type uneFonction(T x);

install libc++

sudo apt update
sudo apt install libc++abi1 libc6 libgcc1 libc++1
sudo apt-get install libc++-dev

insert

• every node has a value and a height and a left, right and a parent node pointers
• search through the tree to find right place to insert the node
• if the node does exist before return it otherwise insert
• after insert the new node is assigned height of 0
• the height is updated for every node going from the new node to the root
• check for imbalance going from the new node to the root
• after imbalance is found do the necessary rotations, at most two rotation are sufficient to rebalance the tree
• left roation, right rotation, left and right rotations, right and left roations

rebalance

• after doing the rotations, the heigth of some node gets messed up
• call a function that updates the height, the function gets as argument the node that was imbalanced and type of imbalance
• the function checks if the imbalance was 'right right' or 'left left' it updates the height of the imbalanced node and it's ancestors
• if the imbalace was 'right left' or 'left right' it updates the height of the imbalanced node , it's sibling and it's ancestors

Links

• Why is the copy constructor not called?
• In-order iterator for binary tree
• LLVM Debian/Ubuntu nightly packages
• What is a symbol table?
• typename c++ and order of compiling
• Binary Search Tree - Copying one tree into another tree
• GNU C++ STL Class Index
• AVL Trees
• Binary Search Trees
• Insert operations on AVL trees