检查序列容器在内存中是否连续
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 << '\n' // true
std::cout << is_contiguous<std::deque<int>>::value << '\n'; // false
std::cout << is_contiguous<std::array<int, 3>>::value << '\n'; // true
}
澄清
这个问题是指类型特征,而不是类型的特定实例的属性。
没有。
没有。 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
}
因此,您的类型特征有时可能是错误的。如果有时它是错误的,那不是类型特征;相反,它是一个实例特征。
否,没有编译时特性。
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。这会为 list
、map
和 unordered_multimap
打印 false
,为 C-array 打印 true
,以及 std::array
、string
和 vector
。它为 deque
内的小子范围打印 true
,为大子范围打印 false
。它还为由反向迭代器组成的迭代器范围打印 false
。
更新:@T.C 评论。最初的 N3884 提案确实有一个
struct contiguous_iterator_tag : random_access_iterator_tag {};
这样迭代器类别上的 tag-dispatching 就不会中断。但是,这会破坏 random_access_iterator_tag
上带有 class 模板特化的 non-idiomatic 代码。因此,当前草案不包含新的迭代器类别标签。
有没有办法检查序列容器在内存中是否连续?类似于:
#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
}
澄清
这个问题是指类型特征,而不是类型的特定实例的属性。
没有。
没有。 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
}
因此,您的类型特征有时可能是错误的。如果有时它是错误的,那不是类型特征;相反,它是一个实例特征。
否,没有编译时特性。
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 valuesa
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, butreverse_iterator<int *>
is not. For a valid iterator range[a,b)
with dereferenceablea
, 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。这会为 list
、map
和 unordered_multimap
打印 false
,为 C-array 打印 true
,以及 std::array
、string
和 vector
。它为 deque
内的小子范围打印 true
,为大子范围打印 false
。它还为由反向迭代器组成的迭代器范围打印 false
。
更新:@T.C 评论。最初的 N3884 提案确实有一个
struct contiguous_iterator_tag : random_access_iterator_tag {};
这样迭代器类别上的 tag-dispatching 就不会中断。但是,这会破坏 random_access_iterator_tag
上带有 class 模板特化的 non-idiomatic 代码。因此,当前草案不包含新的迭代器类别标签。