检查序列容器在内存中是否连续 [英] Checking if a sequence container is contiguous in memory

问题描述

有没有办法检查序列容器是否在内存中是连续的？像：

  #include< iostream> 
 #include< vector> 
 #include< deque> 
 #include< array> 
 
 int main（）
 {
 std :: cout< std :: boolalpha; 
 std :: cout<< is_contiguous< std :: vector< int>> :: value< '\\\
'// true 
 std :: cout<< is_contiguous< std :: deque< int>> :: value< '\\\
'; // false 
 std :: cout< is_contiguous< std :: array< int，3>> :: value<< '\\\
'; // true 
} 
  

澄清 b
$ b

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

解决方案

没有，因此没有这样的compiletime trait。

草案C ++ 1z标准 将连续性定义为运行时属性。请注意，没有与此迭代器类别对应的合并项 std :: contiguous_iterator_tag 。

24.2迭代器要求[iterator.requirements]

24.2.1一般来说[iterator.requirements.general] / p>

5进一步满足对整数
值 n 和可解引用迭代器值 a 和（a + n），*（a + n）
等效于 *（addressof（* a）+ n），称为连续
迭代器。 [注意：例如，类型指向int是一个
连续迭代器，但 reverse_iterator< int *> 不是。对于有效的
迭代器范围 [a，b）与可引用的 a ，相应的范围
由指针表示 [addressof（* a），addressof（* a）+（b-a））; b
可能不是可解引用的。 - 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  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（））<< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（m.begin（），m.end（））< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（u.begin（），u.end（））<< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（d.begin（），d.end（））<< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（d.begin（），d.begin（）+ 1000）<< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（std :: begin（c），std :: end（c））<< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（a.begin（），a.end（））< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（s.begin（），s.end（））<< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（v.begin（），v.end（））<< \\\
; 
 std :: cout<< std :: boolalpha< is_contiguous（v.rbegin（），v.rend（））< \\\
; 
} 
  

在线示例 。它为列表，映射和<$打印 false C-array的 unordered_multimap 和 true ，以及 std :: array ， string 和向量。它为 deque 和 false 中的小子范围打印 true 对于大子范围。它还为由反向迭代器组成的迭代器范围打印 false 。

UPDATE ：如@TC所评论原 N3884 提案确实有

  struct contiguous_iterator_tag：random_access_iterator_tag {}; 
  

，以便迭代器类别上的标签调度不会中断。然而，这会破坏非模式代码与类模板专业化在 random_access_iterator_tag 。因此，当前草稿不包含新的迭代器类别标记。

Is there a way to check if a sequence container is contiguous in memory? Something like:

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

Clarification

This question is referring to type traits, rather than the properties of a specific instance of a type.

解决方案

No, there is not compiletime trait for this.

The draft C++1z Standard defines contiguity as a runtime property of an iterator range. Note there is no compiletime std::contiguous_iterator_tag corresponding to this iterator category.

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 ]

One way to test for this at runtime would be

#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. This prints false for the list, map and unordered_multimap, and true for the C-array, and the std::array, string and vector. It prints true for small subranges within a deque and false for large subranges. It also prints false for an iterator range consisting of reverse iterators.

UPDATE: as commented by @T.C. the original N3884 proposal did have a

struct contiguous_iterator_tag : random_access_iterator_tag {};

so that tag-dispatching on iterator categories would not break. However, this would have broken non-idiomatic code with class template specializations on random_access_iterator_tag. The current draft hence does not contain a new iterator category tag.

这篇关于检查序列容器在内存中是否连续的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！