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实现
