map/unordered_map不允许更改key#

• 原因是我们依靠的是key来进行排序。
  • 而且我们会把key和data合成成为一个value。形式是pair<const key_type, data_type>。然后把这个传入红黑树/哈希表。指定他从中抽取出来pair的第一个值也就是key来排序。
• 所以换句话说就是红黑树/哈希表存的是map的key和value合成的pair。然后通过key排序。这也是为什么map的迭代器返回的是pair。因为我们就是按照pair存进去的。也是为什么用insert存入的时候需要make_pair。
• map不允许更改key是因为保存至红黑树的pair里面的key是const的。
  • 也就是如果有map<k,v> 或 multimap<k,v> 类型的对象，其中的元素类型会是pair<const k, v>

1
if (my_map[4] == 7){
2
    //...
3
}

1
class myobj{
2
    public:
3
        myobj(){
4
            val = 12; //注意这里
5
        }
6
        myobj(int x){
7
            val = x;
8
        }
9
    int val;
10
};
11

12
class comp1{ //自定义排序
13
    public:
14
    bool operator()(const int& lhs, const int& rhs) const{ //注意map的自定义排序是key而不是整个pair。所以自定义排序的函数签名是key
15
        return lhs > rhs;
16
    }
17
};
18
int main()
19
{
20
    map<int,myobj, comp1> we;
21
    myobj a(20);
22
    myobj b(30);
23
    if(we[2].val == a.val){ //key为2的元素的val是否等于a的val
24
        cout << "true1" << endl;
25
    }
26
    for(auto t:we){
27
        cout << t.first << t.second.val << endl; //输出2 12
28
    }
29
    cout << we.size() << endl;
30
}

1
int main(){
2
    unordered_map <string,int> map;
3
    unordered_map <string,int> map2;
4
    vector<string> str = {"a","a","abc","abcd"};
5
    for(string a : str){
6
        cout << map[a] << endl;
7
        map[a] = map[a] + 1;//map[a]是你key对应的value。 a才是你的key。所以这里的意思是 你map[a]的这个val+1。也就是key为a的地方把他的value在原来的基础上加1
8
        //如果map[a]有这个key 比如map里面有a 那么这个val+1。简单来说就是key为a对应的value = key为a对应的value + 1
9
        //如果map[a] 没有这个key。那就加这个key 比如里面没有abc 那就把abc加进去
10
        //map[num];对于这个下标操作，如果存在num关键字，则返回对应的值；如果不存在num关键字，则创建一个键值对，键为num，值为值类型的默认初始化值。
11
       那么这句话的意思是。如果有a这个key，那么把这个key对应的value+1
12
       如果没有，那就先新建a这个key，value设为0+1.
13
       所以map[4] = "ffff" 这一句，如果有4这个key，那就把这个key对应的value改为"ffff"
14
       如果没有，就新建4， "ffff"这个键值对放入map
15
        //等号右侧的map[a]先执行。先在map里面找有没有元素为a的。如果没有就创建一个key=a value=0的元素。然后返回value= 0。之后value+1赋值给key为a的元素的value上面
16
        //先重载=返回自己。然后重载[]返回second也就是value。因为东西是按照pair存的。
17
    }
18
    for(auto x = map.begin(); x!= map.end(); x++){
19
        cout << x->first << x->second << endl;
20
    }
21

22
    pair<string,int> ss = *map.begin();
23
    //map里面的每一个元素可以看为一个pair。注意这里迭代器需要解引用。
24
    因为map的底层是把key和value合成起来成为真正的value。是用一个pair包起来的。
25
    用pair包起来之后，把key和这个包起来的pair放到红黑树里面。
26
    其实这个value应该叫data。没所谓了。
27
    所以map的每一个元素存起来应该长这个样子
28
    key = string
29
    value = pair<string, int>。
30
    所以迭代器的first其实是下面value存的pair的first
31
    迭代器的second是下面的value存的pair的second
32

33

34
    所以说才会有select1st从value里面取key。所以你自己要insert元素的时候需要传一个pair进去。他会把key从pair里面提出来变成key
35

36
}

1
const map<int, int> op{{1,2}};
2
op[1];//不可以。
3
op.at(1);//可以

set不允许更改值#

• 因为set的key和data是同一个东西，也就是value。

  • 我们是依靠这个值进行红黑树排序

  

• 但是set不允许更改值是因为迭代器返回的是常量迭代器也就是const iterator

• map不允许更改key是因为保存至红黑树的pair里面的key是const的。

set不会重复插入且不允许重复元素的原因#

set使用的红黑树的insert_unique

multi_set使用的红黑树的insert_equal

map不会重复插入且不允许重复key的原因#

map使用的红黑树的insert_unique

multi_map使用的红黑树的insert_equal

set容器 和 map容器在插入时会自动排序。所以在使用自定义数据类型的时候就必须要直接指定排序规则仿函数来进行自定义排序。#

1
class myobj{
2
    public:
3
        myobj(){
4
            val = 12; //注意这里
5
        }
6
        myobj(int x){
7
            val = x;
8
        }
9
    int val;
10
};
11

12
class comp1{ //自定义排序
13
    public:
14
    bool operator()(const int& lhs, const int& rhs) const{ //注意map的自定义排序是key而不是整个pair。所以自定义排序的函数签名是key
15
        return lhs > rhs;
16
    }
17
};
18
int main()
19
{
20
    map<int, myobj, comp1> we;
21
    myobj a(20);
22
    myobj b(30);
23
    if(we[2].val == a.val){ //key为2的元素的val是否等于a的val
24
        cout << "true1" << endl;
25
    }
26
    for(auto t:we){
27
        cout << t.first << t.second.val << endl; //输出2 12
28
    }
29
    cout << we.size() << endl;
30
}

c++的map是基于红黑树实现的，它不需要对key进行哈希，所以可以用vector做为key。但是unordered map是基于哈希表实现的，它需要对key进行哈希，但是c++ 默认不对vector提供哈希，所以要么自己写一个哈希函数对vector进行哈希，或不要在unordered map中使用vector做为key。#

注意！随机访问迭代器支持>和<比较！！#

对容器使用下标访问运算符访问或者是对其迭代器解引用返回的是元素的引用。front，back成员函数也是。#

正因为是引用，我们才可以有如下操作，比如：

1
my_vec[0] = 1;
2
*my_vec.begin() = 1;

正因为上面那条，针对容器的常量引用或如果容器本身是常量，提取出来的元素也是常量性质的。#

• 因为常量引用不能绑定到非常量引用。

1
const vector<int> a {1,2,3};
2
int& val = a[0]; //错误
3
const int& vala = a[0]; //正确

1
void functest(const vector<int>& vec){
2
    int& val = vec[0]; //错误
3
    const int& vala = vec[0]; //正确
4
}

为什么没有引用容器，除非使用std::reference_wrapper#

1：容器内的元素必须是可赋值的。引用是不可赋值的（引用只能在声明的同时初始化）

2：没有指向引用的指针。容器有迭代器，迭代器是指针。元素如果是引用，迭代器无法工作，

除非使用std::reference_wrapper

for_each#

1
//这里函数对象对应的函数的形参应该是迭代器指向的容器对象的对应类型。
2
//比如vector<int>的话这里就要int, vector<pair<int,int>>的话就要pair<int, int>
3
void printvector01(int a){
4
    cout << a << endl;
5
}
6

7
//注意这里pair<int a, int b>是错的！！！
8
//pair<>括号里头的是数据类型，外面的才是名字！你不能vector<int a>吧
9
void printvector02(pair<int, int> a){
10
    cout << a.first << " , " << a.second << endl;
11
}
12

13

14
class printvector03{
15
public:
16
    void operator()(int a){
17
        cout << a << endl;
18

19
    }
20
};
21

22
/*
23
template <class _InIt, class _Fn>
24
_CONSTEXPR20 _Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
25
    _Adl_verify_range(_First, _Last);
26
    auto _UFirst      = _Get_unwrapped(_First);
27
    const auto _ULast = _Get_unwrapped(_Last);
28
    for (; _UFirst != _ULast; ++_UFirst) {
29
        _Func(*_UFirst); //这里已经对迭代器对象解引用了，所以直接传入的是迭代器对应的值。
30
        // 注意这里调用函数的方式是直接把参数塞进去。所以传递函数对象就行 不用() 加了括号叫调用
31
    }
32

33
    return _Func; //看好了！！有返回值！！
34
}
35
*/

1
int main(){
2
    vector<int> test = {1,2,3,4,5};
3
    for_each(test.begin(), test.end(), printvector01); //注意这里传递的是函数对象，不是函数。因为printvector01是个函数不是类，所以printvector01()加了括号的叫调用！！
4
    for_each(test.begin(), test.end(), printvector03()); //注意这里传递的是函数对象，不是类型名。因为printvector03是个类(仿函数)不是函数。所以printvector01()加了括号的是类的匿名对象，这里因为是仿函数所以叫函数对象，而不是调用！！
5
    //注意区分类和普通函数的对象。普通函数不加括号叫对象，加了括号叫调用。仿函数（类）要加括号。加了括号叫类的匿名对象，不加括号叫类型名。
6
    vector<pair<int,int>> test2{ {1,1}, {2,2}, {3,3}, {4,4}, {5,5} };
7
    for_each(test2.begin(),test2.end(), printvector02);
8
}

• for_each是可以有返回值的。也就是可以施加一个有状态的函数对象。
  • 比如下面的代码目的是获取所有性别为1的人的id，并放入容器。

1
class Person{
2
    public:
3
        int id;
4
        int sex;
5
        Person() = default;
6
        Person(int x, int y):id(x), sex(y){};
7

8
};
9

10
struct myfind{
11
    vector<int> persons;
12
    void operator()(const Person& item){ //这里不需要bool了。void即可。
13
        if(item.sex == 1){
14
            persons.push_back(item.sex);
15
        }
16
    }
17
};
18

19
int main(){
20
    vector<Person> my_vec{Person(1,1),Person(2,1),Person(3,1),Person(4,2),Person(5,2)};
21
    myfind t = for_each(my_vec.begin(), my_vec.end(), myfind());
22

23
    for(auto&i:t.persons){
24
        cout << i << endl;
25
    }
26
    return 0;
27
}

迭代器种类#

迭代器分为五种：

• 输入迭代器（Input Iterator）：通过对输入迭代器解除引用，它将引用对象，而对象可能位于集合中。最严格的输入迭代只能以只读方式访问对象。例如：istream。
• 输出迭代器（Output Iterator）：该类迭代器和Input Iterator极其相似，也只能单步向前迭代元素，不同的是该类迭代器对元素只有写的权力。例如：ostream, inserter。
• 前向迭代器（Forward Iterator）：该类迭代器可以在一个正确的区间中进行读写操作，它拥有Input Iterator的所有特性，和Output Iterator的部分特性，以及单步向前迭代元素的能力。
  • 假设 p 是一个前向迭代器，则 p 支持 ：
    • ++p
    • p++
    • *p
    • 复制
    • 赋值
    • 可以用 == 和 != 运算符进行比较。
    • 此外，两个正向迭代器可以互相赋值。
• 双向迭代器（Bidirectional Iterator）：该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。例如：list, set, multiset, map, multimap。
  • 假设 p 是一个双向迭代器，则 p 支持 ：
    • 正向迭代器的全部功能 和
    • --p
    • p-- （即一次向后移动一个位置）。
• 随机迭代器（Random Access Iterator）：该类迭代器能完成上面所有迭代器的工作，它自己独有的特性就是可以像指针那样进行算术计算，而不是仅仅只有单步向前或向后迭代。例如：vector, deque, string, array。
  • 假设 p 是一个随机迭代器，则 p 支持 ：
    • 双向迭代器的全部功能 和
    • p+=i：使得 p 往后移动 i 个元素。
    • p-=i：使得 p 往前移动i个元素。
    • p+i：返回 p 后面第i个元素的迭代器。
    • p-i：返回 p 前面第i个元素的迭代器。
    • p[i]：返回 p 后面第 i 个元素的引用。
    • 此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。
    • 另外，表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是p2和p1之间的元素个数减一）。

• 所以我们说，除了vector，deque，string和array以外，其他的容器都不支持如begin()+n的操作。

为什么迭代器的类型不是简单的T*，而一般都带了很长的包装器#

https://quuxplusone.github.io/blog/2022/03/03/why-isnt-vector-iterator-just-t-star/

不同容器不同操作的平均时间复杂度#

*list的sort是成员函数。因为list不提供随机访问迭代器。

• 需要随机访问或只在尾部进行插入或删除使用vector。
• 需要随机访问和头尾插入使用deque
• 如果不需要随机访问但频繁插入和删除使用list
• 如果内存格外受限则使用forward_list
• 如果需要搜索且保持排序则使用map/set
• 如果需要搜索但不需要排序使用unordered_map/unordered_set

原始数组的初始化#

• 静态数组 int array[100];
  • 定义了数组array，但并未对数组初始化；
• 静态数组 int array[100] = {0};
  • 定义了数组array，并将数组元素全部初始化为0；
• 静态数组 int array[100] = {1};
  • 定义了数组array，并将数组第一个元素初始化为1，后面99个元素初始化为0；
• 静态数组int array[100] = {4,5};
  • 定义数组array，并初始化前两个元素为4,5，后面剩余元素初始化为0；

int a[5] = { 1 }; 曾经我认为这是把数组全部初始化为１，事实却是，只有数组的第一个元素被初始化为１，其他全为０；

• 数组初始化列表中的元素个数小于指定的数组长度时，不足的元素补以默认值。

  • 对应基本类型int来说，就是补0
  • 非基本类型的数组就是调用默认构造函数。如string
  • string a[5] = { "foo" }; 等同于 string a[5] = { "foo", "", "", "", "" };
  • 如果不明确指出初始化列表，那么基本类型是不会被初始化的（除全局变量和静态变量外），所有的内存都是“脏的”；
  • 而类类型则会为每个元素调用默认构造函数或使用默认值进行初始化。

  1
  class testnum{
  2
      public:
  3
          testnum(){
  4
          }
  5
          int val = 200;
  6
  };
  7
  class testnum1{
  8
      public:
  9
          testnum1(){
  10
              val = 23333;
  11
          }
  12
          int val;
  13
  };
  14
  int main()
  15
  {
  16
      testnum arr[10]; //全是200
  17
      testnum1 arr1[10]; //全是23333
  18
      int arr2[10]; //没有初始化，脏数据，乱糟糟
  19
      int arr3[10]; //初始化为默认值 10个0
  20
  }
  

• 注意，在C++11中，中间的赋值号可以省略，即

  • int a[5]{1};是合法的，但依旧是只初始化第一个元素为1，剩下的都是默认0

• 并且，如果初始化列表为空，如 int a[5]{}，那将初始化所有元素为默认值，即等同于int a[5]{0};

再次重申容器是值语义。拷贝进来拷贝出去。#

1
int main(){
2
    vector<int>my_vec;
3
    int a = 100;
4
    my_vec.push_back(a); //拷贝进
5
    a = 40000;
6
    cout << my_vec[0] <<endl; //还是100
7
}

为什么呢？我们看看push_back的源代码就好了

1
void push_back(const T& x) {
2
    if (finish != end_of_storage) {
3
        construct(finish, x);
4
        ++finish;
5
    } else
6
        insert_aux(end(), x);
7
}

我们先不管其他的，我们只看construct这个部分

1
template <class T1, class T2>
2
inline void construct(T1* p, const T2& value) {
3
    new (p) T1(value);
4
}

new (p) T1(value);是一个placement new的用法，new的这个用法是在一个已分配好内存的地方调用构造函数来初始化一下。

• 我们这里看到了，我们拿了一个value的值来在一块特定的地方调用拷贝构造来构造了一个元素。这就是为什么我们说是拷贝进。

https://blog.csdn.net/jmh1996/article/details/77968364

• 针对是否拷贝出来，这个地方要综合分析

1
int main(){
2
    vector<int>my_vec;
3
    int a = 100;
4
    my_vec.push_back(a); //拷贝进
5
    int b = my_vec.front();
6
    b = 12345;
7
    cout << my_vec[0] <<endl; //肯定还是100
8

9
    int& c = my_vec.front();
10
    c = 12345;
11
    cout << my_vec[0] <<endl; //变成12345
12
}

因为front返回第一个元素的引用。我们如果用一个引用来初始化一个值，那么会调用其拷贝构造。因为需要独立开来。

容器不能储存常量对象#

没有vector<const int>。因为常量对象不是可拷贝赋值的。而且使用cosnt vector<int>可以达到同一效果。

1
const int a = 200;
2
const int b = 300;
3
b = a; //不可修改常量对象。所以是不可拷贝赋值的。

deque的使用提示#

• 在空容器上对 deque.front()/back() 的调用是未定义的。
  • 因为它返回的是容器首元素的引用。

map不同接口的使用推荐#

依旧来自Raymond Chen的这篇文章

这么多接口，想实现如果没有就插入，如果有不要浪费构造这种逻辑，怎么做？

依旧是Raymond的这篇文章，来自这里。 代码就是一坨。

实现vector<T>#

https://quantdev.blog/posts/implementing_vector/index.html