Подтвердить что ты не робот

Проверка целостности контейнера последовательностей в памяти

Есть ли способ проверить, является ли контейнер последовательностей непрерывным в памяти? Что-то вроде:

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

Разъяснение

Этот вопрос относится к типам признаков, а не к свойствам конкретного экземпляра типа.

4b9b3361

ОТВЕТЫ

Ответ 1

Нет, для этого нет компиляции.

черновик С++ 1z Standard определяет соприкосновение как свойство времени выполнения диапазон итераторов. Обратите внимание, что для этой категории итераторов нет компиляции 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";
}

Пример Live. Это печатает false для list, map и unordered_multimap и true для C-массива и std::array, string и vector. Он печатает true для небольших поддиапазонов в пределах deque и false для больших поддиапазонов. Он также печатает false для диапазона итератора, состоящего из обратных итераторов.

ОБНОВЛЕНИЕ: как комментирует @T.C. в оригинальном N3884 предложение имело

struct contiguous_iterator_tag : random_access_iterator_tag {};

чтобы тег-диспетчеризация по категориям итераторов не нарушалась. Однако это сломало бы неидиоматический код с помощью специализированных шаблонов классов на random_access_iterator_tag. Таким образом, текущий проект не содержит новый тег категории итератора.

Ответ 2

Нет. Стандарт С++ гарантирует отсутствие ложных негативов. (т.е. std::vector, std::string, std::array, а основные массивы, как предполагается, сохраняются смежно).

Однако стандарт С++ не гарантирует отсутствие ложных срабатываний.

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
}

Таким образом, ваш тип может быть неправильным некоторое время. Если это неправильно в некоторые моменты времени, это не черта типа; скорее, это черта экземпляра.

Ответ 3

Нет.