小编Leo*_*ruz的帖子

我知道标题很混乱，所以让我以二叉搜索树为例：

使用普通的类定义

# This code passed mypy test
from typing import Generic, TypeVar

T = TypeVar('T')
class BST(Generic[T]):
    class Node:        
        def __init__(
            self,
            val: T,
            left: 'BST.Node',
            right: 'BST.Node'
        ) -> None:
            self.val = val
            self.left = left
            self.right = right

上面的代码通过了mypy测试。

使用dataclass

但是，当我尝试使用dataclass来简化 的定义时Node，代码在 mypy 测试中失败了。

# This code failed to pass mypy test
from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar('T')
class BST(Generic[T]):
    @dataclass
    class Node:
        val: …

当我选择某些内容时，VSCode 会自动突出显示其他内容，如下所示：

在上例中，第pass2 行是选定的行，而其他行会自动突出显示。这是一个非常好的功能，但问题是，那些未选中的事件的背景颜色与选择的背景颜色太接近。如何更改那些未选定的事件的背景颜色？

我意外地发现插入排序的键std::set比插入混洗的键要快得多。这有点违反直觉，因为一棵红黑树（我证实std::set作为自平衡二叉搜索树在我的系统上是作为红黑树实现的）需要做很多重新平衡操作来插入排序的序列键，因此插入排序的键应该比插入混洗的键花费更多的时间。

但事实是，插入排序的键比插入混洗的键快 15 倍！这是我的测试代码和一些结果：

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <set>
#include <vector>
using namespace std;

int64_t insertion_time(const vector<int> &keys) {    
        auto start = chrono::system_clock::now();
        set<int>(keys.begin(), keys.end());
        auto stop = chrono::system_clock::now();
        auto elapsed = chrono::duration_cast<chrono::milliseconds>(stop - start);
        return elapsed.count(); 
}

int main() {
    size_t test_size;
    cout << "test size: ";
    cin >> test_size;
    vector<int> keys(test_size);
    for (int i = 0; i < test_size; ++i) {
        keys[i] = i;
    }
    
    // whether shuffled case …

下面的代码片段（参见 Godbolt）表明大分配器不会增加 STL 容器的内存占用，但大比较器会。为什么会这样？

// compiled with x86-64 gcc 10.3, -std=c++17
#include <functional>
#include <iostream>
#include <memory>
#include <set>

struct MyLess : public std::less<int>
{
    char dummy[1024];
};

struct MyAllocator : public std::allocator<int>
{
    char dummy[1024];
};

int main()
{
    std::cout << sizeof(std::set<int, MyLess>) << std::endl;  // prints 1064
    std::cout << sizeof(std::set<int, std::less<int>, MyAllocator>) << std::endl;  // prints 48
    return 0;
}