# Code

**Repository Path**: caohonghai8/code

## Basic Information

- **Project Name**: Code
- **Description**: 刷题的代码
- **Primary Language**: C/C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-03-15
- **Last Updated**: 2022-07-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Cpp

## README

# 刷题常见错误以及心得
## set
- 获取**set最后一个元素** 不能用 `*st.end()` 需要用 `*st.rbegin()`, 使用`*set.end()`只能获取到**最后一个元素**的索引。
- set元素转vector的三种方法:
  ```
  std::set<char> s = { 'a', 'b', 'c', 'd', 'e' };
  std::vector<char> v(s.begin(), s.end());
  ```
  ```
  std::set<char> s = { 'a', 'b', 'c', 'd', 'e' };
  std::vector<char> v(s.size());
  std::copy(s.begin(), s.end(), v.begin());
  ```
  ```
  std::set<char> s = { 'a', 'b', 'c', 'd', 'e' };
  std::vector<char> v;
  v.assign(s.begin(), s.end());
  ```
- set中的count():用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。并且set的find等返回的不是下标，因为没有set不是数组，返回的是迭代器，及对应值为value的指针
- vector 的size函数返回vector大小，返回值类型为**size_type**，`Member type size_type is an unsigned integral type`，即**无符号整数**；
  - `vector<int> A;`
  - `A.size()-1`因为size返回值是无符号类型所以 `A.size()-1`越界，是个很大的数
  - 正确使用 `(int)(A.size()-1)`

## string
### replace
1. `string& replace (size_t pos, size_t len, const string& str); `用str替换指定字符串从起始位置pos开始长度为len的字符,如果第三个参数是想要整非字符串数据，需要调用`to_string()`方法
   ```c++
   int main()  
   {  
      string line = "this@ is@ a test string!";  
      line = line.replace(line.find("@"), 1, ""); //从第一个@位置替换第一个@为空  
      cout << line << endl;     
      return 0;  
   }  
   ```
   ```
   output:this@ is a test string!
   ```
2. `string& replace (const_iterator i1, const_iterator i2, const string& str);`用str替换 迭代器起始位置 和 结束位置 的字符 
   ```c++
    int main()  
   {  
       string line = "this@ is@ a test string!";  
       line = line.replace(line.begin(), line.begin() + 6, "");  //用str替换从begin位置开始的6个字符  
       cout << line << endl;     
       return 0;  
   } 
   ```
   ```
   output:is@ a test string!
   ```
## map
map默认的排序是根据key在自动排序的，如果更具value来排序呢？
### 排序问题(更具Key自动排序和自定义排序)
  ```c++
  #include <map>
  #include <string>
  #include <iostream>
  using namespace std;

  typedef pair<string, int> PAIR;

  ostream &operator<<(ostream &out, const PAIR &p)
  {
      return out << p.first << "\t" << p.second;
  }

  int main()
  {
      map<string, int> name_score_map;
      name_score_map["LiMin"] = 90;
      name_score_map["ZiLinMi"] = 79;
      name_score_map["BoB"] = 92;
      name_score_map.insert(make_pair("Bing", 99));
      name_score_map.insert(make_pair("Albert", 86));
      for (map<string, int>::iterator iter = name_score_map.begin();
           iter != name_score_map.end();
           ++iter)
      {
          cout << *iter << endl;
      }
      return 0;
  }
  ```
  ```
  output:

  Albert  86
  Bing    99
  BoB     92
  LiMin   90
  ZiLinMi 79
  ```
- map的定义
   ```c++
   template < class Key, class T, class Compare = less<Key>,
   class Allocator = allocator<pair<const Key,T> > > class map;
   ```
- 第四个是 Allocator，用来定义存储分配模型的, 第三个参数`class Compare = less<Key> `这也是一个`class`类型的，而且提供了默认值 `less<Key>`
- 实质是对`operator()`操作符的重载
   ```c++
   template <class T> struct less : binary_function <T,T,bool> {
      bool operator() (const T& x, const T& y) const
      {return x<y;}
   };
   ```
- 与`less`相对的还有`greater`：
  ```c++
  template <class T> struct greater : binary_function <T,T,bool> {
    bool operator() (const T& x, const T& y) const
      {return x>y;}
  };
  ```
- `map`这里指定`less`作为其默认比较函数(对象)，所以我们通常如果不自己指定`Compare`，`map`中键值对就会按照`Key`的`less`顺序进行组织存储，因此我们就看到了上面代码输出结果是按照学生姓名的字典顺序输出的，即`string`的`less`序列
  ```c++
  #include <map>
  #include <string>
  #include <iostream>
  using namespace std;

  typedef pair<string, int> PAIR;

  ostream &operator<<(ostream &out, const PAIR &p)
  {
      return out << p.first << "\t" << p.second;
  }

  int main()
  {
      map<string, int, greater<string> > name_score_map;
      name_score_map["LiMin"] = 90;
      name_score_map["ZiLinMi"] = 79;
      name_score_map["BoB"] = 92;
      name_score_map.insert(make_pair("Bing", 99));
      name_score_map.insert(make_pair("Albert", 86));
      for (map<string, int>::iterator iter = name_score_map.begin();
           iter != name_score_map.end();
           ++iter)
      {
          cout << *iter << endl;
      }
      return 0;
  }
  ```
  ```
  output:

  ZiLinMi  79
  LiMin    90
  BoB      92
  Bing     99
  Albert   86
  ```
- 写一个compare的类，让map按照自己想要的顺序来存储，比如，按照学生姓名的长短排序进行存储
  ```c++
  struct CmpByKeyLength {
     bool operator()(const string& k1, const string& k2) {
        return k1.length() < k2.length()
     }
  }
  ```
  ```c++
  int main()
  {
      map<string, int, CmpByKeyLength> name_score_map;
      name_score_map["LiMin"] = 90;
      name_score_map["ZiLinMi"] = 79;
      name_score_map["BoB"] = 92;
      name_score_map.insert(make_pair("Bing", 99));
      name_score_map.insert(make_pair("Albert", 86));
      for (map<string, int>::iterator iter = name_score_map.begin();
           iter != name_score_map.end();
           ++iter)
      {
          cout << *iter << endl;
      }
      return 0;
  }
  ```
   ```
  output:

  BoB      92
  Bing     99
  LiMin    90
  Albert   86
  ZiLinMi  79
  ```
### 排序问题(更具Value自定义排序)
借助map提供的参数接口，为它指定相应Compare类，就可以实现对map按Key排序，是在创建map并不断的向其中添加元素的过程中就会完成排序。

> **如何实现Map的按Value排序呢？**

第一反应是利用stl中提供的sort算法实现，但是sort算法有个限制，利用sort算法只能对序列容器进行排序，就是线性的（如vector，list，deque）。map也是一个集合容器，它里面存储的元素是pair，但是它不是线性存储的（像红黑树），所以利用sort不能直接和map结合进行排序。
虽然不能直接用sort对map进行排序，那么可不可以把map中的元素放到序列容器（如vector）中，然后再对这些元素进行排序呢？要对序列容器中的元素进行排序，也有个必要条件：就是容器中的元素必须是可比较的，也就是实现了< 操作的。那么现在就来看下map中的元素满足这个条件么？

- map中的元素类型为pair，定义如下：
```c++
template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;
    pair() : first(T1()), second(T2()) {}
    pair(const T1 &x, const T2 &y) : first(x), second(y) {}
    template <class U, class V>
    pair(const pair<U, V> &p) : first(p.first), second(p.second) {}
}
```
`pair`也是一个模板类，这样就实现了良好的通用性。它仅有两个数据成员**first** 和 **second**，即 `key` 和 `value`，而且
在`<utility>`头文件中，还为`pair`重载了 `< `运算符， 具体实现如下： 
```c++
template <class _T1, class _T2>
inline bool
operator<(const pair<_T1, _T2> &__x, const pair<_T1, _T2> &__y)
{
    return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second);
}
```
其中`__x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second)`
这个less在两种情况下返回true，
- 第一种情况：`__x.first < __y.first`  这个好理解，就是比较`key`，如果`__x的key` 小于`__y的key` 则返回$true$。
- `!(__y.first < __x.first) && __x.second < __y.second`
  - 当然由于||运算具有短路作用，即当前面的条件不满足是，才进行第二种情况的判断 。第一种情况`__x.first < __y.first` 不成立，即`__x.first >= __y.first` 成立，在这个条件下，我们来分析下  `!(__y.first < __x.first)  && __x.second < __y.second`,`!(__y.first < __x.first)` ，看清出，这里是$y$的$key$不小于$x$的$key$ ，结合前提条件，`__x.first < __y.first` 不成立，即$x$的$key$不小于$y$的$key$
即：  `!(__y.first < __x.first)  &&   !(__x.first < __y.first ) `  等价于   `__x.first == __y.first` ,也就是说，第二种情况是在key相等的情况下，比较两者的`value（second）`。