c++ - 检查序列容器在内存中是否连续

Question

有没有办法检查序列容器在内存中是否连续？比如:

#include <iostream>
#include <vector>
#include <deque>
#include <array>

int main()
{
    std::cout << std::boolalpha;
    std::cout << is_contiguous<std::vector<int>>::value   << '\n'  // true
    std::cout << is_contiguous<std::deque<int>>::value    << '\n'; // false
    std::cout << is_contiguous<std::array<int, 3>>::value << '\n'; // true
}

澄清

这个问题是指类型特征，而不是类型的特定实例的属性。

Answer 1

否，没有编译时特性。

draft C++1z Standard 将连续性定义为迭代器范围的运行时属性。注意没有对应这个迭代器类别的编译时std::contiguous_iterator_tag。

24.2 Iterator requirements [iterator.requirements]

24.2.1 In general [iterator.requirements.general]

5 Iterators that further satisfy the requirement that, for integral values n and dereferenceable iterator values a and (a + n), *(a + n) is equivalent to *(addressof(*a) + n), are called contiguous iterators. [ Note: For example, the type “pointer to int” is a contiguous iterator, but reverse_iterator<int *> is not. For a valid iterator range [a,b) with dereferenceable a, the corresponding range denoted by pointers is [addressof(*a),addressof(*a) + (b - a)); b might not be dereferenceable. — end note ]

在运行时对此进行测试的一种方法是

#include <array>
#include <deque>
#include <list>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <string>
#include <unordered_set>
#include <vector>

template<class I>
auto is_contiguous(I first, I last)
{ 
    auto test = true;
    auto const n = std::distance(first, last);
    for (auto i = 0; i < n && test; ++i) {
        test &= *(std::next(first, i)) == *(std::next(std::addressof(*first), i));
    }        
    return test;        
}

int main()
{
    auto l = std::list<int> { 1, 2, 3 };
    auto m = std::map<int, int>  { {1, 1}, {2,2}, {3,3} };
    auto u = std::unordered_multiset<int> { 1, 1, 1 };
    auto d = std::deque<int>(4000);
    int c[] = { 1, 2, 3 };
    auto a = std::array<int, 3> {{ 1, 2, 3 }};
    auto s = std::string {"Hello world!"};
    auto v = std::vector<int> { 1, 2, 3, };

    std::cout << std::boolalpha << is_contiguous(l.begin(), l.end()) << "\n";
    std::cout << std::boolalpha << is_contiguous(m.begin(), m.end()) << "\n";
    std::cout << std::boolalpha << is_contiguous(u.begin(), u.end()) << "\n";
    std::cout << std::boolalpha << is_contiguous(d.begin(), d.end()) << "\n";
    std::cout << std::boolalpha << is_contiguous(d.begin(), d.begin() + 1000) << "\n";
    std::cout << std::boolalpha << is_contiguous(std::begin(c), std::end(c)) << "\n";
    std::cout << std::boolalpha << is_contiguous(a.begin(), a.end()) << "\n";
    std::cout << std::boolalpha << is_contiguous(s.begin(), s.end()) << "\n";
    std::cout << std::boolalpha << is_contiguous(v.begin(), v.end()) << "\n";
    std::cout << std::boolalpha << is_contiguous(v.rbegin(), v.rend()) << "\n";
}

Live Example 。这将为 false 、 list 和 map 打印 unordered_multimap ，为 C 数组打印 true ，以及 std::array 、 string 和 vector 。它为 true 中的小子范围打印 deque，为大子范围打印 false。它还打印由反向迭代器组成的迭代器范围的 false。

更新:由@T.C. 评论。最初的 N3884 提案确实有一个

struct contiguous_iterator_tag : random_access_iterator_tag {};

以便迭代器类别上的标签调度不会中断。但是，这会破坏 random_access_iterator_tag 上的类模板特化的非惯用代码。因此，当前草案不包含新的迭代器类别标签。