本文共 4551 字，大约阅读时间需要 15 分钟。
一些自己用得比较顺手的代码
定义 Compare
排序有时需要自己指定比较器 (Comparator)
# 指定std::greater<> 作为比较器，将vector或者别的容器降续排列
#include //greateer#include #include #include #include int main(){ int A[] = { 6, 9, 1, 5, 2}; std::vector vec(A, A+sizeof(A)/sizeof(A[0])); std::sort(vec.begin(), vec.end(), std::greater ()); //将vector降续排列，注意这里greater 后有要加括号() for(int i = 0; i < vec.size(); std::cout << vec[i++] << ' '); //9 6 5 2 1 std::cout << std::endl; std::priority_queue
, std::greater
> pqueue(A, A+sizeof(A)/sizeof(A[0])); //定义最小堆，注意这里greater
后没有括号 while(!pqueue.empty()){ std::cout << pqueue.top() << ' '; //1 2 5 6 9 pqueue.pop(); } std::cout << std::endl; return 0;}
# 自定义比较器，让优先队列 可以存储特殊struct。
#include #include #include #include //pairusing namespace std;typedef pair Node;class Comparator{public: bool operator()(const Node &a, const Node &b){ return a.second < b.second; //升序，队头元素最小 }};int main(){ int A[] = { 9, 2, 8, 7, 0, 6}; priority_queue , Comparator> pqueue; for(int i = 0; i < sizeof(A) / sizeof(int); pqueue.push(Node(i, A[i])), ++i); while(!pqueue.empty()){ cout << pqueue.top().second << ", orginal index: " << pqueue.top().first << endl; pqueue.pop(); } return 0;}/*输出：9, orginal index: 08, orginal index: 27, orginal index: 36, orginal index: 52, orginal index: 10, orginal index: 4*/
max_element() 与 min_element()
max_element() 可以得出序列中最大值所在的iterator
#include // std::cout#include // std::min_element, std::max_elementbool myfn(int i, int j) { return i
链表类
# 需要一个指针走一步，一个指针走两步。
for(; p2 != NULL; p1 = p1 -> next, p2 = p2 -> next){ p2 = p2 -> next; if(p2 == NULL) break; } 格式的特点是 p1 = p1 -> next, p2 = p2 -> next 写在 for 的里面，为了防止空指针引用，for循环体里要加上 if(p2 == NULL) break;
场景(1) 将链表分为两段，前半段长度 n - n/2， 后半段长度n/2
ListNode *p1 = head; ListNode* p2 = head -> next; for(; p2 != NULL;p1 = p1 -> next, p2 = p2 -> next){ p2 = p2 -> next; if(p2 == NULL) break; } ListNode* temp = p1; p1 = p1 -> next; temp -> next = NULL;
场景(2) 除了分两段，判断环链表也需要这种格式的代码，之所以要从head -> next出发，是因为如果要接着找出环入口的话，相遇点的位置是正确的。
bool hasCycle(ListNode *head) { if(NULL == head) return false; ListNode* p1 = head -> next; ListNode* p2 = head -> next; for(; p2 != NULL; p1 = p1 -> next, p2 = p2 -> next){ p2 = p2 -> next; if(p2 == NULL || p1 == p2) break; } if(p2 == NULL) return false; return true; } 话说回来，这样写稍微有点非主流，清晰一点的写法是这样：
ListNode *FindCircleStart(ListNode *head){ if(!head) return NULL; ListNode *p = head, *q = head; while(q -> next){ p = p -> next; q = q -> next -> next; if(!q || q == p) break; } if(!q) return NULL; //无环 for(p = head; p!= q; p = p -> next, q = q -> next); //找出相遇点 return p;}
看似简单，但是其实考虑到了几种边界情况，比如只有一个节点的环链表。
BIT 类
返回一个整数转化为二进制后，1 的个数
int __builtin_popcount(unsigned int)int __builtin_popcountl(unsigned long int)int __builtin_popcountll(unsigned long long)
这三个函数是GCC提供的函数，不属于std
要想自己实现的话，有一个效率比较高的方法
http://www.cnblogs.com/felixfang/category/535191.html 后半部分
数组类
排好序的数组中去重
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
int removeDuplicates(int A[], int n) { if(n <= 1) return n; int p = 0, q = 1; while(q < n){ if(A[p] == A[q]) ++q; else A[++p] = A[q++]; } return p+1; } 如果重复数字允许出现两次
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
只要在++q的条件上增加两项即可。
int removeDuplicates(int A[], int n) { if(n <= 1) return n; int p = 0, q = 1; while(q < n){ if(A[p] == A[q] && p > 0 && A[p] == A[p-1]) ++q; else A[++p] = A[q++]; } return p+1; }
字符串处理类
string a;char* chs = a.c_str(); //string to char*int num = atoi(a.c_str()) //string to int
#include #include string convert(int v){ ostringstream convert; // stream used for the conversion convert << v; // insert the textual representation of 'Number' in the characters in the stream return convert.str(); // set 'Result' to the contents of the stream}