Effective STL - 01 - Containers

Containers

条款 1 仔细选择你的容器

vector是一种可以默认使用的序列类型，当很频繁地对序列中部进行插入和删除时应该用list，当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构

连续内存容器（也叫做基于数组的容器）在一个或多个（动态分配）的内存块中保存它们的元素。如果一个新元素被查入或者已存元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率（参见条款5和14）和异常安全（就像我们将会看到的）。标准的连续内存容器是vector、string和deque。

基于节点的容器在每个内存块（动态分配）中只保存一个元素。容器元素的插入或删除只影响指向节点的指针，而不是节点自己的内容。

你要把迭代器、指针和引用的失效次数减到最少吗？如果是，你就应该使用基于节点的容器，因为在这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。一般来说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。

你需要具有有以下特性的序列容器吗：1）可以使用随机访问迭代器；2）只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效？这个一个非常特殊的情况，但如果你遇到这种情况，deque就是你梦想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。）

在 vector 上会插入和删除会导致当前的迭代器失效。如下：

vector<int> v = {1, 2, 3, 4};
auto it = v.begin();
cout << *it << endl;  // 1

v.insert(it, -1);
cout << *it << endl;  // 报错

TODO：对应容器的失效规则。

条款2：小心对“容器无关代码”的幻想

标准的内存相邻容器（参见条款1）都提供随机访问迭代器，标准的基于节点的容器（再参见条款1）都提供双向迭代器。序列容器支持push_front或push_back，但关联容器不支持。关联容器提供对数时间复杂度的lower_bound、upper_bound和equal_range成员函数，但序列容器却没有。

在一个序列容器上用一个迭代器作为参数调用erase，会返回一个新迭代器，但在关联容器上什么都不返回。

既然有了要一次次的改变容器类型的必然性，你可以用这个常用的方法让改变得以简化：使用封装，封装，再封装。其中一种最简单的方法是通过自由地对容器和迭代器类型使用typedef。

class Widget {...};
vector<Widget> vw;
Widget bestWidget;
... // 给bestWidget一个值
vector<Widget>::iterator i = // 寻找和bestWidget相等的Widget
 find(vw.begin(), vw.end(), bestWidget);

class Widget { ... };
typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw;
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget);

如果你不想暴露出用户对你所决定使用的容器的类型，你需要更大的火力，那就是class。

目前有了 auto 操作，大部分 typedef 应该是可以省略的。

条款3：使容器里对象的拷贝操作轻量而正确

一旦一个对象进入一个容器，以后对它的拷贝并不少见。如果你从vector、string或deque中插入或删除了什么，现有的容器元素会移动（拷贝）（参见条款5和14）。如果你使用了任何排序算法（参见条款31）：next_permutation或者previous_permutation；remove、unique或它们的同类（参见条款32）；rotate或reverse等，对象会移动（拷贝）。是的，拷贝对象是STL的方式。

一个使拷贝更高效、正确而且对分割问题免疫的简单的方式是建立指针的容器而不是对象的容器。

所以，对于 容器 来说，大部分都只是保存一个 T* ，而不是数组

和数组对比，STL容器更文明。它们只建立（通过拷贝）你需要的个数的对象，而且它们只在你指定的时候做。是的，我们需要知道STL容器使用了拷贝，但是别忘了一个事实：比起数组它们仍然是一个进步。

条款4：用empty来代替检查size()是否为0

list<int> list1; 
list<int> list2; 
... 
list1.splice( // 把list2中
 list1.end(), list2, // 从第一次出现5到
 find(list2.begin(), list2.end(), 5), // 最后一次出现10
 find(list2.rbegin(), list2.rend(), 10).base() // 的所有节点移到list1的结尾。
); // 关于调用的
 // "base()"的信息，请参见条款28

考虑这部分代码。（其中 splice 是拼接，接合，即把两个 list 合并。上述代码的意思是：在 list1 的末尾，拷贝从 list2 第一次出现 5，到最后一次出现 10 的所有数据）

常数时间的 splice 与常数时间的 size 是相违背的，即：

1. 如果 splice 是常数时间，那么无法在 splice 的过程中更新 size，那么每次调用 size 时就必须以 O(N) 的方式遍历
2. 如果 size 是常数时间，那么 splice 必须更新 size，splice 就会是 O(N)

因此，调用 empty() 可以获得更好的时间复杂度，因为它总是 O(1) 的

条款5：尽量使用区间成员函数代替它们的单元素兄弟

区间成员函数指的是使用 range 的成员函数，使用一个开头迭代器，一个结尾迭代器标识区间。然后根据不同的操作，有不同的变化。单元素兄弟，就是直接访问数据。

区间成员函数 和 单元素兄弟 写法的对比：

vector<int> v1, v2;
// ...

// 单元素写法
v1.clear();
for (auto it = v2.begin() + v2.size() / 2; it != v2.end(); it++) {
  v1.push_back(*it);
}

vector<int>::iterator insertLoc(v1.begin());
for (int i = 0; i < numValues; ++i) {
 insertLoc = v1.insert(insertLoc, data[i]);
 ++insertLoc;  // 迭代器失效, 必须更新
}

// 区间成员函数写法
v1.assgin(v2.begin() + v2.size() / 2, v2.end());
v1.insert(v1.begin(), v2.begin() + v2.size() / 2, v2.end());
copy(v2.begin() + v2.size() / 2, v2.end(), inserter(v1. v1.end()));

v1.insert(v1.begin(), data, data + numValues);

copy 仍然比写 assign 的调用要做更多的工作。此外，虽然在这段代码中没有表现出循环，在copy中的确存在一个循环(参见条款43）。结果，效率损失仍然存在。我也会在下面讨论。在这里，我要离题一下来指出几乎所有目标区间是通过插入迭代器（比如，通过inserter，back_inserter或front_inserter）指定的copy的使用都可以——应该——通过调用区间成员函数来代替。

本条款的主题：几乎所有目标区间被插入迭代器指定的copy的使用都可以用调用的区间成员函数的来代替。

原因：1、减少函数调用；2、数据移动的开销（单元素每次都要移动一次数组，区间可以直接移动到最终位置，减少了 N - 1 次的 移动/拷贝 开销）；3、vector 扩容机制。

支持区间成员函数的写法：

• 构造函数：Container::Container(InputIterator begin, OutputIterator end);
• 插入：
  • 序列容器需要指定插入位置： void Container::insert(iterator position, InputIterator begin, InputIterator end);
  • 关联容器由于是通过比较元素的大小来决定插入位置的，所以不需要插入位置： void Container::insert(InputIterator begin, InputIterator end);
• 删除：
  • 序列容器由于迭代器失效，因此会返回一个迭代器： iterator Container::erase(iterator begin, iterator end);
  • 关联容器不会返回（是因为返回会导致不必要的性能开销？）： void Container::erase(iterator begin, iterator end);
• 赋值：
  • void Container::assign(InputIterator begin, InputIterator end);

条款6：警惕C++最令人恼怒的解析

C++ 中会首先解析函数，因此：

// 被解析为一个函数
list<int> lFunc(istream_iterator<int>(iss), istream_iterator<int>());

// 被成功解析
list<int> l((istream_iterator<int>(iss)), istream_iterator<int>());
for_each(l.begin(), l.end(), [] (int& a) { cout << a << " "; });
cout << endl;

第一个变量的定义被解析为一个单纯的函数声明，但是第二个定义被解析为变量定义。（通过添加一个括号的形式，但是这样可能导致 未来的编译器 报错）

还有另一种不使用匿名对象的方式：

istream_iterator<int> dataBegin(iss), dataEnd();
list<int> l(dataBegin, dataEnd);

缺点就是不够符合 C++ STL 的风格。

条款7：当使用new得指针的容器时，记得在销毁容器前delete那些指针

当一个指针的容器被销毁时，会销毁它（那个容器）包含的每个元素，但指针的“析构函数”是无操作！它肯定不会调用delete。即，只回收了指针占用的内存，而没有回收指针指向的内容占用的内存。因此，对于 指针的容器，我们需要手动 delete 回收。

void doSth() {
    vector<int*> vi;
    vi.reserve(10'000'000);
    for (int i = 0; i < 10'000'000; i++)  vi.push_back(new int{12});
    // 回收内存之后, 没有内存泄漏
    for_each(vi.begin(), vi.end(), [] (int*& a) { delete a; });  
}

// 使用智能指针
void doSthSmart() {
    vector<unique_ptr<int>> vui;
    vui.reserve(10'000'000);
    for (int i = 0; i < 10'000'000; i++)  vui.push_back(make_unique<int>(12));
}

int main() {
    for (int i = 0; i < 10; i++) {
        doSth();            // 内存泄漏 6129 MB
        // doSthSmart();    // 无泄漏 4.2 MB
    }

    return 0;
}

上面还使用仿函数，构建了一个自动回收内存的仿函数类。

条款8：永不建立auto_ptr的容器

auto_ptr 不可移植，并且 对 auto_ptr 的拷贝会改变它本身的值。

条款9：在删除选项中仔细选择

如何选择一个合适的删除选项？分情况讨论如下：

• 去除一个容器中有特定值的所有对象：
  • 如果容器是vector、string或deque，使用erase-remove惯用法
  • 如果容器是list，使用list::remove
  • 如果容器是标准关联容器，使用它的erase成员函数。
• 去除一个容器中满足一个特定判定式的所有对象：
  • 如果容器是vector、string或deque，使用erase-remove_if惯用法。
  • 如果容器是list，使用list::remove_if。
  • 如果容器是标准关联容器，使用remove_copy_if和swap，或写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。
• 在循环内做某些事情（除了删除对象之外）：
  • 如果容器是标准序列容器，写一个循环来遍历容器元素，每当调用erase时记得都用它的返回值更新你的迭代器。
  • 如果容器是标准关联容器，写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它

// 必须加上这部分 `class...`
// 因为 vector 的实际签名是 vector<T, _Allocator<T>>
// 不能只加入一个 template parameter
// 由于 cout 中似乎无法添加 constant
// 因此必须自己建一个类, 来让 C++ 完成类型推导
template<template <class...> class Container, typename... T>
ostream& operator<<(ostream& os, Container<T...>& c) {
    using ValueType = typename Container<T...>::value_type;
    for_each(c.begin(), c.end(), [&os] (const ValueType& t) {
        os << t << " ";
    });

    return os;
}

int main() {
    vector<int> v = {-1, 0, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8};
    list<int> l{v.begin(), v.end()};
    set<int> s{v.begin(), v.end()};

    // 删除某一个数值
    // vector 使用 erase-remove 技术
    int toBeRemoved = 1;
    v.erase(remove(v.begin(), v.end(), toBeRemoved), v.end());

    // list 使用 remove
    l.remove(toBeRemoved);

    // set 使用 erase
    s.erase(toBeRemoved);

    // ===============
    // 条件删除

    // vector 使用 erase-remove_if 技术
    int upperBound = 2;
    auto pred = [&] (const int& a) { return a <= upperBound; };

    v.erase(remove_if(v.begin(), v.end(), pred), v.end());

    // list 使用 remove_if
    l.remove_if(pred);

    // set 使用 remove_copy_if-swap 技术
    set<int> tmp;
    // 可以使用 inserter(tmp, tmp.end())
    // 不能使用 back_inserter(tmp), 它会调用 push_back 方法
    // 导致 set 容器报错
    // 这里报错很奇怪, 报错的地方在 `set<in>s` 中, 而不是调用的地方
    remove_copy_if(s.begin(), s.end(), inserter(tmp, tmp.end()), pred);
    s.swap(tmp);

    // ===============
    // 删除的过程中执行操作

    // 序列容器  ---  需要更新 迭代器
    for (auto it = v.begin(); it != v.end();) {
        if (pred(*it)) {
            // 此时已经更新了 迭代器, 因此不需要 ++
            it = v.erase(it);
        } else {
            // 对于不满足条件的值, 直接 ++
            it++;
        }
    }

    // set 使用 for 循环  ---  需要及时更新 迭代器
    for (auto it = s.begin(); it != s.end(); ) {
        // 对于所有非法的值, 删除之后再移动迭代器到下一个位置
        if (pred(*it))  s.erase(it++);
        // 合法的值, 直接移动即可
        else  it++;
    }

    return 0;
}

条款10：注意分配器的协定和约束

因此，如果你想要写自定义分配器，让我们总结你需要记得的事情。

• 把你的分配器做成一个模板，带有模板参数T，代表你要分配内存的对象类型。
• 提供pointer和reference的typedef，但是总是让pointer是T*，reference是T&。
• 决不要给你的分配器添加对象状态。通常，分配器不能有非静态的数据成员。
• 记得应该传给分配器的allocate成员函数需要分配的对象个数而不是字节数。也应该记得这些函数返回T*指针（通过pointer typedef），即使还没有T对象被构造。
• 一定要提供标准容器依赖的内嵌rebind模板。

为什么不能添加对象状态？因为编译器认为两个相同的类型的分配器，总是相同的。因此分配器只能拥有静态成员。

为什么需要 rebind？因为对于基于节点的容器（如 list、set、map 等），他们需要的数据结构是 Node<T> ，而不是 T 。为了分配节点的内存，因此提出了 rebind。通过 rebind 分配这部分的节点内存，rebind 的签名也变成了 allocator<T>::rebind<Node<T>>::other ，其中的 other 就是 <Node<T> 。

MSVC 的 allocator 实现如下：

_INLINE_VAR constexpr size_t _Asan_granularity = 8;

template <class _Ty>
class allocator {
public:
    static_assert(!is_const_v<_Ty>, "The C++ Standard forbids containers of const elements "
                                    "because allocator<const T> is ill-formed.");

    using _From_primary = allocator;

    using value_type = _Ty;

#if _HAS_DEPRECATED_ALLOCATOR_MEMBERS
    using pointer _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS       = _Ty*;
    using const_pointer _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS = const _Ty*;

    using reference _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS       = _Ty&;
    using const_reference _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS = const _Ty&;
#endif // _HAS_DEPRECATED_ALLOCATOR_MEMBERS

    using size_type       = size_t;
    using difference_type = ptrdiff_t;

    using propagate_on_container_move_assignment           = true_type;
    using is_always_equal _CXX20_DEPRECATE_IS_ALWAYS_EQUAL = true_type;

#if _HAS_DEPRECATED_ALLOCATOR_MEMBERS
    // rebind 的实现
    template <class _Other>
    struct _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS rebind {
        using other = allocator<_Other>;
    };

    _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS _NODISCARD _Ty* address(_Ty& _Val) const noexcept {
        return _STD addressof(_Val);
    }

    _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS _NODISCARD const _Ty* address(const _Ty& _Val) const noexcept {
        return _STD addressof(_Val);
    }
#endif // _HAS_DEPRECATED_ALLOCATOR_MEMBERS

    constexpr allocator() noexcept {}

    // 分配内存 或者 rebind 的内存
    constexpr allocator(const allocator&) noexcept = default;
    template <class _Other>
    constexpr allocator(const allocator<_Other>&) noexcept {}
    _CONSTEXPR20 ~allocator()                           = default;
    _CONSTEXPR20 allocator& operator=(const allocator&) = default;

    _CONSTEXPR20 void deallocate(_Ty* const _Ptr, const size_t _Count) {
        _STL_ASSERT(_Ptr != nullptr || _Count == 0, "null pointer cannot point to a block of non-zero size");
        // no overflow check on the following multiply; we assume _Allocate did that check
        _Deallocate<_New_alignof<_Ty>>(_Ptr, sizeof(_Ty) * _Count);
    }

    _NODISCARD_RAW_PTR_ALLOC _CONSTEXPR20 __declspec(allocator) _Ty* allocate(_CRT_GUARDOVERFLOW const size_t _Count) {
        static_assert(sizeof(value_type) > 0, "value_type must be complete before calling allocate.");
        return static_cast<_Ty*>(_Allocate<_New_alignof<_Ty>>(_Get_size_of_n<sizeof(_Ty)>(_Count)));
    }

#if _HAS_CXX23
    _NODISCARD_RAW_PTR_ALLOC constexpr allocation_result<_Ty*> allocate_at_least(
        _CRT_GUARDOVERFLOW const size_t _Count) {
        return {allocate(_Count), _Count};
    }
#endif // _HAS_CXX23

#if _HAS_DEPRECATED_ALLOCATOR_MEMBERS
    _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS _NODISCARD_RAW_PTR_ALLOC __declspec(allocator) _Ty* allocate(
        _CRT_GUARDOVERFLOW const size_t _Count, const void*) {
        return allocate(_Count);
    }

    template <class _Objty, class... _Types>
    _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS void construct(_Objty* const _Ptr, _Types&&... _Args) {
        ::new (_Voidify_iter(_Ptr)) _Objty(_STD forward<_Types>(_Args)...);
    }

    template <class _Uty>
    _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS void destroy(_Uty* const _Ptr) {
        _Ptr->~_Uty();
    }

    _CXX17_DEPRECATE_OLD_ALLOCATOR_MEMBERS _NODISCARD size_t max_size() const noexcept {
        return static_cast<size_t>(-1) / sizeof(_Ty);
    }
#endif // _HAS_DEPRECATED_ALLOCATOR_MEMBERS

    static constexpr size_t _Minimum_allocation_alignment = _Asan_granularity;
};

条款11：理解自定义分配器的正确用法

自定义前提：

• 你用了基准测试，性能剖析，而且实验了你的方法得到默认的STL内存管理器（即allocator ）在你的STL需求中太慢、浪费内存或造成过度的碎片的结论，并且你肯定你自己能做得比它好。
• 或者你发现allocator对线程安全采取了措拖，但是你只对单线程的程序感兴趣，你不想花费你不需要的同步开销。
• 或者你知道在某些容器里的对象通常一同被使用，所以你想在一个特别的堆里把它们放得很近使引用的区域性最大化。（hint，提高局部性）
• 或者你想建立一个相当共享内存的唯一的堆，然后把一个或多个容器放在那块内存里，因为这样它们可以被其他进程共享。

一个自定义 allocator 的实现：

/*
本文的例子是创建一个在  共享内存区  的对象, malloc 分配的内存在堆区
共享内存区 主要跟 多线程/多进程 有关, Linux 中由 SharedMemory 决定
*/
void* makeShared(size_t size) {
    return malloc(size);
}

void freeShared(void* ptr) {
    free(ptr);
}

template <typename T>
struct MyAllocator {
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using value_type = T;
    using size_type = size_t;
    using difference_type = std::ptrdiff_t;

    pointer allocate(size_t numObjects, const void *localityHint = 0) {
        auto ptr = makeShared(numObjects * sizeof(T));
        // print message and allocate memory with global new
        std::cerr << "allocate " << numObjects << " element(s)"
            << " of size " << sizeof(T) 
            << " at " << ptr << std::endl;
        return static_cast<pointer>(ptr);
    }

    // initialize elements of allocated storage p with value value
    void construct (pointer p, const T& value) {
        // initialize memory with placement new
        new((void*)p)T(value);
    }

    // destroy elements of initialized storage p
    void destroy (pointer p) {
        // destroy objects by calling their destructor
        p->~T();
    }

    void deallocate(pointer dataPtr, size_t numObjects) {
        // print message and deallocate memory with global delete
        std::cerr << "deallocate " << numObjects << " element(s)"
                    << " of size " << sizeof(T)
                    << " at: " << (void*)dataPtr << std::endl;
        freeShared(dataPtr);
    }

    template <typename U>
    struct rebind {
        using other = MyAllocator<U>;
    };

    // return address of values
    pointer address (reference value) const { return &value; }
    const_pointer address (const_reference value) const { return &value; }

    /* constructors and destructor
    * - nothing to do because the allocator has no state
    */
    MyAllocator() throw() { }
    MyAllocator(const MyAllocator&) throw() { }
    template <class U>
        MyAllocator (const MyAllocator<U>&) throw() { }
    ~MyAllocator() throw() { }

    // return maximum number of elements that can be allocated
    size_type max_size () const throw() {
        return std::numeric_limits<std::size_t>::max() / sizeof(T);
    }

};

// return that all specializations of this allocator are interchangeable
template <class T1, class T2>
bool operator== (const MyAllocator<T1>&,
                const MyAllocator<T2>&) throw() { return true; }

template <class T1, class T2>
bool operator!= (const MyAllocator<T1>&,
                const MyAllocator<T2>&) throw() { return false;}

必须满足以上条件，该分配器才会自动工作。参考：

myalloc.hpp

条款12：对STL容器线程安全性的期待现实一些

C++ 中的容器并不是多线程安全的，因为这会带来很大的开销。容器在多线程情况下能够实现的操作如下：

• 多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能有任何写入者操作这个容器。
• 对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。

如果想要实现一个多线程安全的容器，要求如下：

• 在每次调用容器的成员函数期间都要锁定该容器。
• 在每个容器返回的迭代器（例如通过调用begin或end）的生存期之内都要锁定该容器。
• 在每个在容器上调用的算法执行期间锁定该容器。（这事实上没有意义，因为，正如条款32所解释的，算法没有办法识别出它们正在操作的容器。不过，我们将在这里检验这个选项，因为它的教育意义在于看看为什么即使是可能的它也不能工作。）

这带来很大的线程锁（同步原语，如信号量机制）的资源开销。

在 Morden C++ 中，可以使用信号量保证多线程的同步：

#include <mutex>

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};
    mutex m;

    {
        // 使用互斥锁 必须手动  lock  unlock
        m.lock();
        for_each(v.begin(), v.end(), [] (int& a) { cout << a << " "; });
        m.unlock();
    }
    {
        // unique_lock 使用 RAII, 保证锁会 自动上锁 和 释放
        unique_lock<mutex> lock(m);
        for_each(v.begin(), v.end(), [] (int& a) { cout << a << " "; });
    }
}