标准C++ - 标准 C++

C++11 标准库扩展——容器和算法

算法改进

标准库算法的改进部分通过简单地添加新算法，部分通过新语言特性实现改进的实现，部分通过新语言特性实现更简单的使用

新算法

    bool all_of(Iter first, Iter last, Pred pred);
    bool any_of(Iter first, Iter last, Pred pred);
    bool none_of(Iter first, Iter last, Pred pred);

    Iter find_if_not(Iter first, Iter last, Pred pred);

    OutIter copy_if(InIter first, InIter last, OutIter result, Pred pred);
    OutIter copy_n(InIter first, InIter::difference_type n, OutIter result);

    OutIter move(InIter first, InIter last, OutIter result);
    OutIter move_backward(InIter first, InIter last, OutIter result);

    pair<OutIter1, OutIter2> partition_copy(InIter first, InIter last, OutIter1 out_true, OutIter2 out_false, Pred pred);
    Iter partition_point(Iter first, Iter last, Pred pred);

    RAIter partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last);
    RAIter partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last, Compare comp);
    bool is_sorted(Iter first, Iter last);
    bool is_sorted(Iter first, Iter last, Compare comp);
    Iter is_sorted_until(Iter first, Iter last);
    Iter is_sorted_until(Iter first, Iter last, Compare comp);

    bool is_heap(Iter first, Iter last);
    bool is_heap(Iter first, Iter last, Compare comp);
    Iter is_heap_until(Iter first, Iter last);
    Iter is_heap_until(Iter first, Iter last, Compare comp);

    T min(initializer_list<T> t);
    T min(initializer_list<T> t, Compare comp);
    T max(initializer_list<T> t);
    T max(initializer_list<T> t, Compare comp);
    pair<const T&, const T&> minmax(const T& a, const T& b);
    pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
    pair<const T&, const T&> minmax(initializer_list<T> t);
    pair<const T&, const T&> minmax(initializer_list<T> t, Compare comp);
    pair<Iter, Iter> minmax_element(Iter first, Iter last);
    pair<Iter, Iter> minmax_element(Iter first, Iter last, Compare comp);

    void iota(Iter first, Iter last, T value);  // For each element referred to by the iterator i in the range [first,last), assigns *i = value and increments value as if by ++value

移动的影响：移动可能比复制效率高得多（参见移动语义。例如，基于移动的 std::sort() 和 std::set::insert() 经测量比基于复制的版本快 15 倍。这听起来不如实际那么令人印象深刻，因为对于标准库类型（如 string 和 vector）的此类标准库操作通常会经过手工优化，通过替换复制为优化的交换等技术来获得移动的效果。但是，如果您的类型具有移动操作，您将自动从标准算法中获得性能优势。此外，请考虑使用移动可以简单高效地排序（以及其他算法）智能指针容器，尤其是 unique_ptr

    template<class P> struct Cmp<P> {   // compare *P values
        bool operator() (P a, P b) const { return *a<*b; }
    }

    vector<std::unique_ptr<Big>> vb;
    // fill vb with unique_ptr's to Big objects

    sort(vb.begin(),vb.end(),Cmp<Big>());   // don't try that with an auto_ptr

Lambda 的使用：长期以来，人们一直抱怨不得不编写函数或（更好）函数对象以用作操作，例如上述的 Cmp，用于标准库（及其他）算法。如果您编写大型函数（不推荐），这样做尤其痛苦，因为在 C++98 中，您不能定义局部函数对象作为参数；现在可以了。但是，lambda 允许我们“内联”定义操作

    sort(vb.begin(),vb.end(),[](unique_ptr<Big> a, unique_ptr<Big> b) { return *a<*b; });

初始化列表的使用：有时，初始化列表作为参数会派上用场。例如，假设有 string 变量和 Nocase 为不区分大小写的比较

    auto x = max({x,y,z},Nocase());

另请参见

25 算法库 [algorithms]
26.7 广义数值运算 [numeric.ops]
Howard E. Hinnant, Peter Dimov, and Dave Abrahams: A Proposal to Add Move Semantics Support to the C++ Language. N1377=02-0035.

容器改进

鉴于新的语言特性和十年的经验，标准容器发生了什么？首先，我们当然得到了几个新的：array（固定大小的容器），forward_list（单向链表），以及无序容器（哈希表）。其次，诸如初始化列表、右值引用、可变参数模板和constexpr[cpp11-constexpr] 等新特性被投入使用。考虑 std::vector。

初始化列表：最明显的改进是使用初始化列表构造函数，允许容器将初始化列表作为其参数

    vector<string> vs = { "Hello", ", ", "World!", "\n" };
    for (auto s : vs ) cout << s;

移动运算符：容器现在具有移动构造函数和移动赋值（除了传统的复制操作）。最重要的含义是我们可以高效地从函数中按值返回容器

    vector<int> make_random(int n)
    {
        vector<int> ref(n);
        for(auto& x : ref) x = rand_int(0,255); // some random number generator
        return ref;
    }

    vector<int> v = make_random(10000);
    for (auto x : make_random(1000000)) cout << x << '\n';

这里的要点是没有 vector 被复制。如果重写此函数以返回自由存储分配的 vector，您将不得不处理内存管理。如果重写此函数以将要填充的 vector 作为参数传递给 make_random()，您将得到一个远不那么明显的代码（再加上一个可能犯错误的机会）。

改进的 push 操作：许多人最喜欢的容器操作是 push_back()，它允许容器优雅地增长

    vector<pair<string,int>> vp;
    string s;
    int i;
    while(cin>>s>>i) vp.push_back({s,i});

这将从 s 和 i 构造一个 pair 并将其移动到 vp 中。注意是“移动”而不是“复制”；有一个 push_back 版本接受一个右值引用参数，以便我们可以利用 string 的移动构造函数。还要注意使用统一初始化语法来避免冗长。

就地构造操作：使用移动构造函数的 push_back() 在重要情况下比传统的基于复制的效率高得多，但在极端情况下我们可以更进一步。为什么要复制/移动任何东西？为什么不在 vector 中腾出空间，然后在该空间中构造所需的值？执行此操作的操作称为“emplace”（意为“就地放置”）。例如 emplace_back()

    vector<pair<string,int>> vp;
    string s;
    int i;
    while(cin>>s>>i) vp.emplace_back(s,i);

一个 emplace 接受一个可变参数模板参数，并使用它来构造所需类型的对象。emplace_back() 是否真的比 push_back() 更高效取决于所涉及的类型和实现（库和可变参数模板的实现）。如果你认为它很重要，就进行测量。否则，根据美观选择：vp.push_back({s,i}); 或 vp.emplace_back(s,i);。目前，许多人更喜欢 push_back() 版本，部分原因是熟悉，但这可能会随着时间而改变。

作用域分配器：容器现在可以持有“真正的分配对象（带状态）”，并使用它们来控制嵌套/作用域分配（例如，容器中元素的分配）。

显然，容器并不是标准库中唯一受益于新语言特性的部分。考虑

编译时求值：constexpr 用于确保、bitset、duration、char_traits、array、atomic 类型、随机数、complex 等的编译时求值。在某些情况下，这意味着性能提升；在其他情况下（没有替代编译时求值），这意味着没有凌乱的低级代码和宏。
元组：没有可变参数模板就不可能实现元组

`unordered_*` 容器

一个 unordered_* 容器是使用哈希表实现的。C++11 提供了四种标准的

unordered_map
unordered_set
unordered_multimap
unordered_multiset

它们本应被称为 hash_map 等，但这些名称有太多不兼容的用法，以至于委员会不得不选择新名称，而 unordered_* 名称很好地突出了 map 和 unordered_map 之间（比如说）的关键区别：当您从 begin() 到 end() 遍历 map 时，您会按照其键类型的 less-than 比较运算符（默认为 <）提供的顺序进行遍历，而 unordered_map 的值类型不需要具有 less-than 比较运算符，并且哈希表自然不提供顺序。还有其他区别；特别是，相反，map 的元素类型不需要具有哈希函数。

基本思想是简单地将 unordered_map 用作 map 的优化版本，在可能和合理的情况下进行优化。例如

    map<string,int> m {
        {"Dijkstra",1972}, {"Scott",1976}, {"Wilkes",1967}, {"Hamming",1968}
    };
    m["Ritchie"] = 1983;
    for(auto& x : m) cout << '{' << x.first << ',' << x.second << '}';

    unordered_map<string,int> um {
        {"Dijkstra",1972}, {"Scott",1976}, {"Wilkes",1967}, {"Hamming",1968}
    };
    um["Ritchie"] = 1983;
    for(auto& x : um) cout << '{' << x.first << ',' << x.second << '}';

对 m 的迭代将按字母顺序呈现元素；对 um 的迭代不会（除非发生意外）。m 和 um 的查找实现方式非常不同。对于 m，查找涉及 log2(m.size()) 次小于比较，而对于 um，查找涉及对哈希函数的一次调用和一次或多次相等操作。对于少数元素（比如几十个），很难判断哪个更快。对于大量元素（例如数千个），unordered_map 中的查找可能比 map 快得多。

另请参见

标准：23.5 无序关联容器。

`std::array`

标准容器 array 是在中定义的固定大小的随机访问元素序列。除了存储元素所需的空间外，它没有额外的空间开销，不使用自由存储，可以用初始化列表初始化，知道其大小（元素数量），并且除非您明确要求，否则不会转换为指针。换句话说，它非常类似于内置数组，但没有内置数组的问题。

    array<int,6> a = { 1, 2, 3 };
    a[3]=4;
    int x = a[5];       // x becomes 0 because default elements are zero initialized
    int* p1 = a;        // error: std::array doesn't implicitly convert to a pointer
    int* p2 = a.data(); // ok: get pointer to first element

请注意，您可以拥有零长度的 array，但不能从初始化列表中推断出 array 的长度

    array<int> a3 = { 1, 2, 3 };    // error: size unknown/missing
    array<int,0> a0;        // ok: no elements
    int* p = a0.data();     // unspecified; don't try it

标准 array 的特性使其在嵌入式系统编程（以及类似的受限、性能关键或安全关键任务）中具有吸引力。它是一个序列容器，因此它提供常用的成员类型和函数（就像 vector 一样）

    template<class C> typename C::value_type sum(const C& a)
    {
        return accumulate(a.begin(),a.end(),0);
    }

    array<int,10> a10;
    array<double,1000> a1000;
    vector<int> v;
    // ...
    int x1 = sum(a10);
    double x2 = sum(a1000);
    int x3 = sum(v);

此外，您不会得到（可能有害的）派生到基类的转换

    struct Apple : Fruit { /* ... */ };
    struct Pear : Fruit { /* ... */ };

    void nasty(array<Fruit*,10>& f)
    {
        f[7] = new Pear();
    };

    array<Apple*,10> apples;
    // ...
    nasty(apples);  // error: can't convert array<Apple*,10> to array<Fruit*,10>;

如果允许那样做，apples 现在会包含一个 Pear。

另请参见

标准：23.3.1 类模板 array

`forward_list`

标准容器 forward_list，在中定义，基本上是一个单向链表。它仅支持向前迭代，并保证如果您插入或擦除一个元素，元素不会移动。它占用最小空间（空列表可能只有一个字），并且不提供 size() 操作（因此它不必存储大小成员）

    template <ValueType T, Allocator Alloc = allocator<T> >
        // requires NothrowDestructible<T>
    class forward_list {
    public:
        // the usual container stuff
        // no size()
        // no reverse iteration
        // no back() or push_back()
    };

另请参见

标准：23.3.3 类模板 forward_list

C++11 标准库扩展——容器和算法

算法改进

容器改进

unordered_* 容器

std::array

forward_list

`unordered_*` 容器

`std::array`

`forward_list`