首页 > 代码库 > C++ 基本数据结构整理

C++ 基本数据结构整理

Hash Map (Unordered_map)

  • Insert
    #include <unordered_map>using namespace std;unordered_map <char, bool> hash_map;hash_map.insert(make_pair<char,bool>(a,true));
  • find
    if(hash_map.find(num) == hash_map.end())cout << "not found" << endl;
    unordered_map <char, bool> :: iterator got = hash_map.find(‘a‘);
    got->first 指向key
    got->second 指向value

 

String

  1. 如何遍历string里每个元素
    //sa is a stringfor( string::iterator p = sa.begin() ; p!= sa.end() ; p++ )         cout << *p ;     cout << endl;

     

  2. 如何使用string里的find

    string:size_type pos = str.find(0);        // pos is the position in string you find.if(pos==string::npos) cout << "cannt find";else cout << pos;

     

  3.  

     

 

Type Conversion

  1. Char -> Int
    char s = ‘5‘int a = s-‘0‘;
  2. Int -> String
    string s = std::to_string(5);
  3. String -> Int 
    std::string myString = "45";int value = http://www.mamicode.com/atoi(myString.c_str()); //value = http://www.mamicode.com/45 

     

  4. You cann‘t do switch-case statement on string by C++


     

Stack

  1. 如何压入一个pair
    stack<pair<TreeNode*, int> > s;s.push(make_pair(root,1));TreeNode *tmp = s.top().first;int len = s.top().second; 
  2. 用STL stack中的push(),pop(),top()

    // STL 栈适配器(stack)#include <iostream>#include <stack>using namespace std;int main(){ stack<int> is;               //定义栈对象  for (int i = 0; i < 100; ++i)  is.push(i+100);          //将100~199一次顺序入栈   cout<<"top element:"<<is.top()<<endl; //查看栈顶元素 is.pop();                    //出栈操作 cout<<"new top element:"<<is.top()<<endl; //查看栈顶元素 cout<<"size:"<<is.size()<<endl;   //查看栈高度    return 0;   } 

     

Heap

  • 如何用已有的数据结构实现heap的操作包括push_head, pop_head, sort_heap
    // range heap example#include <iostream>     // std::cout#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap#include <vector>       // std::vectorint main () {  int myints[] = {10,20,30,5,15};  std::vector<int> v(myints,myints+5);  std::make_heap (v.begin(),v.end());  std::cout << "initial max heap   : " << v.front() << \n;  std::pop_heap (v.begin(),v.end()); v.pop_back();                 //pop_heap()用于弹出堆中的第一个元素&#65292;并把它放到区间的最后一个位置&#65292;然后重新将前面的元素构建成一个堆&#12290;  std::cout << "max heap after pop : " << v.front() << \n;  v.push_back(99); std::push_heap (v.begin(),v.end());             // push_heap()用于将指定区间的最后一个元素加入堆中并使整个区间成为一个新的堆&#12290;注意前提是最后一个元素除外的所有元素已经构成一个堆&#12290;  std::cout << "max heap after push: " << v.front() << \n;  std::sort_heap (v.begin(),v.end());  std::cout << "final sorted range :";  for (unsigned i=0; i<v.size(); i++)    std::cout <<   << v[i];  std::cout << \n;  return 0;}Output:initial max heap   : 30max heap after pop : 20max heap after push: 99final sorted range : 5 10 15 20 99

     

 Array & Vector

  • 多维vector如何判断行和列的大小
    vector<vector<int> > matrixint rowSize = matrix.size();int colSize = matrix[0].size()
  • 使用insert()在一个指定的position前插入一个元素
    #include<iostream>#include<vector>using namespace std; int main(){    vector<int> v(3);    v[0]=2;    v[1]=7;    v[2]=9;        //在最前面的元素前插入8    v.insert(v.begin(),8);        //在第二个元素前插入新元素1    v.insert(v.begin()+2,1);        //在末尾插入新元素1    v.insert(v.end(),3);             for(vector<int>::iterator it=v.begin();it!=v.end();it++)    cout<<*it<<endl;    system("pause");    return 0;   }
  • 用STL查找vector中最小元素的方法
    cout<<"maxinum:"<<*min_element(v.begin(),v.end())<<endl;int index = min_element(v.begin(),v.end())-v.begin();
  • 用vector创建多维数组. 多维的数组被写做 vector<vector<int>空格>. 其实是描述了一个二维数组/矩阵 a。其初始化可以参考下面的代码
    std::vector<std::vector<int> > a;   vector< vector<int> > intVV;      vector<int> intV;      int i,j;      for(i=0;i<10;++i){        intV.clear();        for(j=0;j<10;++j)        intV.push_back(i*10+j);        intVV.push_back(intV);
  • 一个遍历数组的简单写法
    int num[] = {2,2,3};    for(int i:num)   // You must define i here.        cout << i << endl;
  • vector中的pop/push
     #include <vector>using namespace std;vector<char> array;array.push_back(‘9‘);char num = array.back();array.pop_back();

     

STL操作符重载来改变sort算法

// 排序元素&#65292;比较的对象  struct Person  {    Person(int id, const string& name, int age): id_(id), name_(name), age_(age)    {}        int id_;    string name_;    int age_;  };  // 方式1&#65306;重载operator<用于排序时的比较(写在函数体内)  bool operator< (const Person& rt)  {    return this->id_ < rt.id_;  }    // 排序函数写法&#65292;默认调用operator<  sort(members.begin(), members.end());  // 方式2&#65306;写比较函数  bool CompAge(const Person& pl, const Person& pr)  {    return pl.age_ < pr.age_;  }    // 排序时传入比较函数指针  sort(members.begin(), members.end(), CompAge);  // 方式3&#65306;仿函数  struct CompName  {    bool operator()(const Person& pl, const Person& pr)    {      return pl.name_ < pr.name_;    }  };    // 排序时传入函数对象  sort(members.begin(), members.end(), CompName());  


Leetcode中数据结构的定义

Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */

 

C++ 基本数据结构整理