检查序列容器是否在内存中是连续的

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

不,这没有编译时间特性.

该草案C++标准1Z邻接定义为运行时属性的迭代器的范围.注意,没有std::contiguous_iterator_tag与此迭代器类别对应的编译时间.

24.2迭代器要求[iterator.requirements]

24.2.1一般[iterator.requirements.general]

5迭代器进一步满足对于整数值n和可解除引用的迭代器值a并且(a + n), *(a + n) 等效的要求*(addressof(*a) + n),称为连续迭代器.[注意:例如,类型"指向int的指针"是一个连续的迭代器,但reverse_iterator<int *>不是.对于[a,b)具有可解除引用的有效迭代器范围,a由指针表示的相应范围[addressof(*a),addressof(*a) + (b - a)); b 可能不是可解除引用的. - 结束说明]

在运行时测试这个的一种方法是

#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";
}

实例.这将打印false的list,map并且unordered_multimap,和true对C-阵列,并且std::array,string和vector.它打印true一个deque和false大的子范围内的小子范围.它还打印false一个由反向迭代器组成的迭代器范围.

更新:由@TC评论,原来的N3884提案确实有一个

struct contiguous_iterator_tag : random_access_iterator_tag {};

这样迭代器类别上的tag-dispatching就不会破坏.但是,这会破坏具有类模板特化的非惯用代码random_access_iterator_tag.因此,当前草案不包含新的迭代器类别标记.

Answer 2

不可以.C++标准保证不存在漏报.(即,std::vector,std::string,std::array,和基本阵列答应连续存储).

但是,C++标准并不保证没有误报.

int main() {
   std::unique_ptr<Node> n1(new Node);
   std::unique_ptr<Node> n2(new Node);
   n1->next = n2; // n1 and n2 might be contiguous, but might not be
}

因此,您的类型特征在某些时候可能是错误的.如果在某些时候出错,那就不是一种类型特征; 相反,它是一个实例特征.