1.STL

//trivial 1.从iteartor中得出value-type等类型信息，2.偏特化自动推导内置类型
template<class I>
class iterator_trivial {
    typedef typename I::value_type value_type;
    typedef typename I::reference reference;
    typedef typename I::pointer pointer;
    typedef typename I::difference_type difference_type;
    typedef typename I::iterator_category iterator_category;
};
template<class T>
class iterator_trivial<T*> {
    typedef typename T value_type;
    typedef typename T& reference;
    typedef typename T* pointer;
    typedef typename ptrdiff_t difference_type;
    typedef typename random_iterator_category iterator_category;

};
template<class T>
class iterator_trivial<const T*> {
    typedef typename T value_type;
    typedef typename const T& reference;
    typedef typename const T* pointer;
    typedef typename ptrdiff_t difference_type;
    typedef typename random_iterator_category iterator_category;
};
//type_trivial
struct false_type {};
struct true_type {};
template<class T>
struct type_trivial {
    typedef false_type has_trivial_destructor;

};

#include<cstddef> 
template<class T, class Category,class Ref=T&,class Pointer=T*,class Distance=ptrdiff_t>
class iterator {
    typedef T value_type;
    typedef Ref reference;
    typedef Pointer pointer;
    typedef Distance difference_type;
    typedef Category iterator_category;
};
template<class InputIterator>
typename iterator_trivial<InputIterator>::difference_type _distance(InputIterator first,InputIterator end,random_iterator_category) {
    return end - first;
}
template<class InputIterator>
typename iterator_trivial<InputIterator>::difference_type _distance(InputIterator first, InputIterator end, input_iterator_category) {
    typedef typename iterator_trivial<InputIterator>::difference_type difference_type;
    difference_type n;
    for (; first != end; ++first) {
        ++n;
    }
    return n;
}
template<class InputIterator>
typename iterator_trivial<InputIterator>::difference_type distance(InputIterator first, InputIterator end) {
    typedef typename iterator_trivial<InputIterator>::iterator_category iteraotr_category;
    return _distance(first, end, iteraotr_category());
}

image.png

void TestSTL() {
    vector<int> v{ 2,3,1,5,4,9 };
    cout << "make_heap" << endl;
    make_heap(v.begin(), v.end());
    for (auto& i : v) {
        cout << i << endl;
    }
    cout << "push_heap" << endl;
    v.push_back(10);
    push_heap(v.begin(), v.end());
    make_heap(v.begin(), v.end());
    for (auto& i : v) {
        cout << i << endl;
    }
    cout << "pop_heap" << endl;
    pop_heap(v.begin(), v.end());
    v.pop_back();
    for (auto& i : v) {
        cout << i << endl;
    }
    cout << "sort_heap" << endl;
    sort_heap(v.begin(), v.end());
    for (auto& i : v) {
        cout << i << endl;
    }
}

2.实现：

1.sort:

template<class ValueType>
void Swap(ValueType& a, ValueType& b) {
    ValueType tmp = a;
    a = b;
    b = tmp;
}
template <class Iterator>
void BubbleSort(Iterator start, Iterator end) {
    int left = 0, right = end - start - 1;
    for (int i = left,r=right; i < r;r--) {
        for (int j = i;j<r;j++) {
            if (start[j] > start[j + 1])
                Swap(start[j], start[j + 1]);
        }
    }
}
template<class Iterator>
void SelectionSort(Iterator start, Iterator end) {
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    int left = 0, right = end - start - 1;
    for (int l = left, r = right; l < right; ++l) {
        int minIndex = l + 1;
        for (int i = l + 1; i <= r; ++i) {
            if (start[minIndex] > start[i])
                minIndex = i;
        }
        Swap(start[minIndex], start[l]);
    }
}
template<class Iterator>
void InsertSort(Iterator start, Iterator end) {
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    int left = 0, right = end - start - 1;
    for (int l = left + 1, r = right; l <= r; ++l) {
        valueType tmp = start[l];
        int i = l - 1;
        for (; i >= 0; --i) {
            if (start[i] > tmp)
                start[i + 1] = start[i];
            else
                break;//注意这里是break
        }
        start[i + 1] = tmp;
    }
}
template<class Iterator>
void Quick_Sort(Iterator& start, int left, int right) {
    if (left >= right) return;
    int pivot = left;
    int l = left, r = right;
    while (l < r) {
        while (start[r] >= start[pivot] && l < r)--r;
        while (start[l] <= start[pivot] && l < r)++l;
        if (l < r)
            Swap(start[l], start[r]);
    }
    Swap(start[r], start[pivot]);
    pivot = r;
    Quick_Sort(start, left, pivot - 1);
    Quick_Sort(start, pivot + 1, right);
}
template<class Iterator>
void QuickSort(Iterator start, Iterator end) {
    int left = 0, right = end - start - 1;
    Quick_Sort(start, left, right);
}

template<class Iterator>
void MergeSort(Iterator start, Iterator end) {
    int left = 0, right = end - start - 1;
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    valueType* tmp = new valueType[right + 1];
    Merge_Sort(start,tmp, left, right);
}
template<class Iterator,class ValueType>
void Merge_Sort(Iterator start, ValueType* tmp, int left, int right) {
    if (left >= right) return;
    int mid= (left + right) / 2;
    Merge_Sort(start, tmp, left, mid);
    Merge_Sort(start, tmp, mid + 1, right);
    int l = left, r = mid + 1, t = left;
    while (l <= mid && r <= right) {
        if (start[l] > start[r]) { tmp[t] = start[r]; ++r; ++t; }
        else { tmp[t] = start[l]; ++l; ++t; }
    }
    if (l > mid) {
        while (r <= right) { tmp[t] = start[r]; ++r; ++t; }
    }
    if (r > right) {
        while (l <= mid) { tmp[t] = start[l]; ++l; ++t; }
    }
    for (int l = left, r = right; l <= r; ++l) {
        start[l] = tmp[l];
    }
}
template<class Iterator>
void BucketSort(Iterator start, Iterator end) {
    int left = 0, right = end - start - 1;
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    valueType min = GetMin(start, end);
    valueType max = GetMax(start, end);
    int* bucket = new int(max - min + 1);
    for (int i = min; i <= max; ++i) {
        bucket[i] = 0;
    }
    for (int i = left; i <= right; ++i) {
        bucket[start[i]]++;
    }
    for (int i = min, j = left; i <= max; ++i) {
        if (bucket[i] > 0) {
            int num = bucket[i];
            while (num > 0) {
                start[j] = i;
                ++j; --num;
            }
        }
    }

}
template<class Iterator>
typename IteratorTraits<Iterator>::valueType GetMin(Iterator start, Iterator end) {
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    int left = 0, right = end - start - 1;
    valueType min = start[left];
    for (int l = left, r = right; l <= r; ++l) {
        if (min > start[l])
            min = start[l];
    }
    return min;
}
template<class Iterator>
typename IteratorTraits<Iterator>::valueType GetMax(Iterator start, Iterator end) {
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    int left = 0, right = end - start - 1;
    valueType max = start[left];
    for (int l = left, r = right; l <= r; ++l) {
        if (max < start[l])
            max = start[l];
    }
    return max;
}
template<class Iterator>
void HeapSort(Iterator start, Iterator end) {
    int left = 0, right = end - start - 1;
    int size = right + 1;
    for (int i = size / 2 - 1; i >= 0; i--) {//i是最后一个子节点的父节点(index+1=size)/2-1
        AdjustHeap(start,i,size);
    }
    int l = left, r = right;
    while (size) {
        Swap(start[l], start[size-1]);
        --size;
        AdjustHeap(start,0,size);
    }
}
template<class Iterator>
void AdjustHeap(Iterator& start,int index,int size) {
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    valueType tmp=start[index];
    int child = index * 2 + 1;
    for (;child<size;child=child*2+1) {
        if (child + 1 < size && start[child] < start[child + 1]) {
            child++;
        }
        if (start[child] > tmp) {
            start[(child+1)/2-1] = start[child];
        }
        else break;
    }
    start[(child+1)/2-1] = tmp;

}
template<class Iterator>
void ShellSort(Iterator start, Iterator end) {
    typedef typename IteratorTraits<Iterator>::valueType valueType;
    int left = 0, right = end - start - 1;
    int size = right + 1;
    int gap = size / 2;
    while (gap) {
        for (int i = gap; i <= right;++i) {
            valueType tmp = start[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (start[j] > tmp)
                    start[j + gap] = start[j];
                else
                    break;
            }
            start[j + gap] = tmp;
        }
        gap /= 2;
    }
}

2.hash:

template<class ValueType>
class HashTable {
private:
    vector<list<Pairs<ValueType>*>> v;
    int tableSize;
    int prim;
public:
    typedef list<Pairs<ValueType>*> llist;
    HashTable(int nt) :tableSize(nt) {
        prim = getPrim();
        for (int i = 0; i < tableSize; ++i) {
            llist l;
            v.push_back(l);
        }
    }
    int Hash(string s) {
        int sum = 0;
        int size = s.size();
        for (int i = 0; i < size; ++i) {
            sum = (sum >> 5) + s[i];
        }
        return sum % prim;
    }
    void Insert(string s, ValueType val) {
        int index = Hash(s);
        v[index].push_back(new Pairs<ValueType>(s, val));
    }
    void Erase(string s) {
        int index = Hash(s);
        auto l = v[index];
        auto it=Find(l.Begin(), l.End());
        l.Erase(it);
    }
    ValueType& operator[](string s) {
        int index = Hash(s);
        auto l = v[index];//<BiDirectionIterator<Pairs<ValueType>*>,Pairs<ValueType>>
        auto it = Find(l.begin(), l.end(),new Pairs<ValueType>(s,1), [](Pairs<ValueType>* a, Pairs<ValueType>* b)->bool {return a->first == b->first; });
        if (it != l.end()) return (*it)->second;

    }
    int getPrim() {
        for (int i = tableSize; i >= 2; i--) {
            bool flag = true;
            for (int j = 2; j < i; ++j) {
                if (i%j == 0)
                    flag = false;
            }
            if (flag == true)
                return i;
                
        }
    }

};

3.BTree:

template<class ValueType> 
class BTree {
public:
    typedef ValueType v;
    typedef TreeNode<v> node;
    typedef TreeNode<v>* nodeP;
protected:
    nodeP head;
public:
    BTree() {
        head = (nodeP)malloc(sizeof(node));
        head->right = nullptr;
        head->left = nullptr;
        
    }
    BTree(const vector<v>& vec,v nullVal) :BTree(){
        head->left=BuildTree(vec, nullVal);
        head->right = head->left;
    }
    nodeP BuildTree(const vector<v>& vec, v nullVal) {
        //1.从queue中取一个父节点2.遍历vec创建一个节点作为左节点，如果不为空加入queue3.右节点同理
        if (vec.empty() || vec[0] == nullVal)
            return nullptr;
        nodeP root = new node(vec[0]);//真正意义上的root
        queue<nodeP> q;
        q.push(root);
        int index = 1;
        int size = vec.size();
        while (1) {
            nodeP np= q.front();
            q.pop();
            if (index >= size) break;//如果vec读完，结束
            else {
                if (vec[index] == nullVal) {//为空值
                    np->left = nullptr;
                }
                else {//非空值
                    nodeP l= new node(vec[index]);
                    np->left = l;
                    q.push(l);
                }
                ++index;
            }
            if (index >= size) break;//如果vec读完，结束
            else {
                if (vec[index] == nullVal) {//为空值
                    np->right = nullptr;
                }
                else {//非空值
                    nodeP r = new node(vec[index]);
                    np->right = r;
                    q.push(r);
                }
                ++index;
            }

        }
        return root;
    }
    template<class Fn>
    void PreOrderTraversal(Fn f) {
        nodeP np = head->left;
        stack<nodeP> s;
        while (np||!s.empty()) {
            while (np) {
                f(np->val);
                s.push(np);
                np = np->left;
            }
            np = s.top();
            s.pop();
            np = np->right;
        }
    }
    template<class Fn>
    void MidOrderTraversal(Fn f) {
        nodeP np = head->left;
        stack<nodeP> s;
        while (np||!s.empty()) {
            while (np) {
                s.push(np);
                np = np->left;
            }
            np = s.top();
            f(np->val);
            s.pop();
            np = np->right;
        }
    }
    template<class Fn>
    void PostOrderTraversal(Fn f) {
        nodeP np = head->left;
        stack<nodeP> s;
        while (np||!s.empty()) {
            while (np) {
                s.push(np);
                np = np->left;
            }
            np = s.top();
            if (np->right == nullptr) {
                f(np->val);
                s.pop();
            }
            np = np->right;

        }
    }
    //后序有两种思路，一种是左边到底用top访问之前的路，如果节点右为空才访问并弹出，第二种根据后序遍历的反转是对称树的先序这一特点用两个stack实现