STL structures and functions

在数据结构和大数据部分，提到了set， hash_set, map, hash_map。 关于这4种数据结构需要重点掌握，set和map是使用RB树（红黑树，一种平衡二叉树）实现，所以插入、查找、删除的时间复杂度都是O(logn)；而hash_set和hash_map是使用hash表实现，所以插入、查找、删除的时间复杂度都是O(1)。

简单看来好像hash_set和hash_map优势大，set和map好像不值得使用。实际上，因为set和map是使用红黑树实现，所以其中的元素是排好序的，方便查找最大值和最小值（时间复杂度O(logn)）。因而，要根据具体情况选用合适的数据结构。

在C++中，set和map分别对应STL中set和map，hash_set和hash_map分别对应STL中unordered_set和unordered_map（C++11标准引入）。

unordered_set

  1. undordered_set里保存的元素都是唯一的，一旦插入，就不能修改。
  2. 元素值同时也是key，可以通过常数时间查询到。
  3. 构造：std::unordered_set myset;
  4. 插入emplace：myset.emplace ("potatoes");//return a pair
  5. 查找find：myset.find("asfd")==myset.end说明没有找到
  6. 删除erase：myset.erase ("potatoes");

什么时候用unordered_set，判断元素是否存在的时候，用unordered_map也可以，这种情况下不如用unordered_set

priority_queue

priority_queue是堆在c++里的实现，push插入元素，top返回堆顶元素，top删除堆顶元素。

默认是最大堆，堆顶是最大值。

priority_queue 对于基本类型的使用方法相对简单。 他的模板声明带有三个参数，priority_queue Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。 Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list. STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个 参数缺省的话，优先队列就是大顶堆，队头元素最大。

int main(){
    int myints[]= {10,60,50,20};
  std::priority_queue<int> second (myints,myints+4);//copy from array
    priority_queue<int> q;
    for( int i= 0; i< 10; ++i ) q.push( rand() );
    while( !q.empty() ){
        cout << q.top() << endl;
        q.pop();
    }
    getchar();
    return 0;
}

如果要用到小顶堆，则一般要把模板的三个参数都带进去。 STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明小顶堆

int main(){
    priority_queue<int, vector<int>, greater<int> > q;
    for( int i= 0; i< 10; ++i ) q.push( rand() );
    while( !q.empty() ){
        cout << q.top() << endl;
        q.pop();
    }
    getchar();
    return 0;
}

自定义一个Comparison object

在需要自定义比较函数的地方使用，比如priority_queue, sort(sort里用的是com(), 是object）等。

struct cmp{
        bool operator() (const pair<int, string> &a, const pair<int, string> &b) const{
            if(a.first == b.first) return a.second > b.second;
            return a.first < b.first;
        }
    };

重载操作符

bool operator< (const Node &rhs) const {
        if(cnt == rhs.cnt) return word > rhs.word;
        return cnt < rhs.cnt;
    }

##STL--集和多集（set/multiset）

  • 内部它实现: 红黑树
  • 插入删除查找复杂度log(n)，但是查找或添加末尾的元素时会有些慢
  • 其中所包含的元素的值是唯一的(map)
  • 允许重复元素
  • 定义变量 set myset;
  • myset.insert(elem) 向集合中插入数据,如果已经存在则不插入
  • myset.erase(elem) 删除集合中值等于 elem的元素
  • myset.find(elem) 查找值等于elem的元素,若找到返回指向elem的迭代器，否则返回end()
  • mymulset.count(elem) 返回多重集合中数据elem出现的次数

vector 去重

unique + resize

sort(result.begin(), result.end());
vector<vector<int> >::iterator it = unique(result.begin(), result.end());
result.resize(it-result.begin());

string

  1. append 

    Extends the string by appending additional characters at the end of its current value:
* ```string& append (const string& str);``` //append a string
* ```string& append (const string& str, size_t subpos, size_t sublen);``` //append a substring
* ```string& append (const char* s);``` // append a c-string
* ```string& append (const char* s, size_t n); ``` //append a buffer
* ```string& append (size_t n, char c); ``` //fill 
* ```template <class InputIterator>
   string& append (InputIterator first, InputIterator last);```   //append a range

  1. to_string

    std::string pi = "pi is " + std::to_string(3.1415926);

  2. erase 删除

     sequence (1) basic_string& erase (size_type pos = 0, size_type len = npos);
 character (2)  iterator erase (iterator p);
 range (3)  iterator erase (iterator first, iterator last);

  3. push_back(char c) vs pop_back() 在尾部加入一个元素，删除最后一个char

list

  1. 不能随机访问，只能用iterator，比如：
    list<int> mylist = { 1, 2, 3, 4, 5 };
 for (auto it = mylist.begin(); it != mylist.end(); it++) {
     auto it2 = it;
     //it2++; //CANNOT it2 = it+1
     for (it2; it2 != mylist.end(); it2++)
         cout << *it2 << endl;
     cout << endl;
 }

  2. list的container是 bidirectional iterator，跟 random-access iterator相比，它不支持+=， +n, >, <, 仅支持!=, ++, --。可以用advance来move iterator，但是要注意move以后要有所指。

  3. 插入元素用emplace，emplace_back, emplace_front

  4. 删除元素用pop_back, pop_front, remove
  5. 在list里移动某个元素到另一个位置，用splice函数。例如：list1.splice(list1.begin(), list1, list1.begin()+i);

About sort function

  • 上面是定义了一个comparison structure，然后sort函数里comparison oject是sort的第三个参数，cmpInterval()代表一个object。
  • 也可以用一个function pointer来取代cmpInterval(), as follows:
    bool CompareInterval(Interval A, Interval B) {
      if(A.start == B.start) return A.end < B.end;
          return A.start < B.start;
  }
  • 诡异的是A B不能像cmpInterval里面那样引用传递。
  • 更诡异的是这个function的定义不能放到solution里面，只能放到Solution class外面。

results matching ""

    No results matching ""