Разработка итератора с двумя указателями на вложенные объекты

Question

Цель контейнера

Я создаю контейнер, который предназначен для хранения отсортированных целочисленных значений без знака очень эффективным образом в ОЗУ.Идея состоит в том, чтобы сгруппировать значения по общему основанию.Вместо

std::vector<unsigned int> V = {1234,1254,1264,1265,1267,1268,1271,1819,1832,1856,
                                  1867,1892,3210,3214,3256,3289};

у меня будет что-то вроде

MyContainer V =
{
   {12..
      ..34, ..54, ..64, ..65, ..67, ..68, ..71
   },
   {18..
      ..19, ..32, ..56, ..67, ..92
   }
   {32..
      ..10, ..14, ..56, ..89
   }
};

_{. В приведенном выше примере я сгруппировал значения по блокам по 100. Было бы более логично сгруппироватьданные по группе 2 ^ 16.Предполагая, что каждый unsigned int равен 4 байта, а каждый unsigned short равен 2 байта, первый вектор из 16 элементов будет занимать не менее 16 * 4 = 64 байта, а второй вектор будет занимать 19 * 2 = 38 байтов ОЗУ.}

Краткое описание контейнера

Вкратце, вот организация этого контейнера ...

class MyContainer
{
   // attribute
   std::vector<Block> data;

   // methods
   // ..
};

class Block
{
   // attributes
   unsigned short radix;
   std::vector<unsigned short> suffixs; // contains all the suffix associated with this radix

   // methods
   // ..
};

Хотя совет по поводу этой структуры данных будет приветствоваться, ядроМой вопрос о реализации итератора.

Итератор

У меня возникли проблемы при создании итератора.Мой итератор должен также разрешить прямое исследование и произвольный доступ.Я впервые создаю классический шаблон проектирования итераторов, и, скорее всего, я делаю ошибки.Вот атрибуты моего итератора

class Iterator
{
   // attributes
   std::vector<Block>::iterator bigP;             // points to a Block
   std::vector<unsigned short>::iterator smallP;  // points to an unsigned int within the Block pointed by bigP
   std::vector<Block>::iterator bigPEnd;

  // methods
  // ...
};

Q1: должен ли MyContainer::iterator содержать итераторы (как это в настоящее время имеет место) или он должен содержать указатели?Почему?

Я думал, что когда итератор указывает на последний unsigned int из Block, тогда operator++() должен толкнуть bigP к следующему Block и нажать smallP к первому элементу

Мне кажется неправильным, что я должен включить итератор в data.end () (называемый bigPEnd), но в итоге я добавил его, когда понял, что когдаoperator++() вызывается, в то время как MyContainer::iterator указывает на последние unsigned int из последних Block, я должен был знать, что не могу установить smallP на bigP->begin(), так как это приведет к ошибке сегментации как*bigP не существует.

Q2: мне нужен указатель на последний элемент data?Как этого избежать?

Я также сталкиваюсь с аналогичной проблемой при создании MyContainer::iterator для пустого вектора.Обычно я создаю итератор с

MyContainer::iterator MyContainer::begin()
{
   return iterator(data.begin(), data.front().suffixs.begin(), data.end());
        //            ^^                 ^^                       ^^
        //           bigP              smallP                    bigPEnd
}

Однако data.front() приведет к ошибке сегментации, когда data пусто.Если бы я использовал указатели, я мог бы установить smallP на nullptr, когда данные пусты и когда bigP == data.end() независимо от того, пустые данные или нет.

Q3: Как я могу справиться с smallPкогда не на что указывать?

Не могли бы вы дать мне несколько советов по реализации этого итератора?

Answer 1

Q1

Должен ли MyContainer::iterator содержать итераторы (как это происходит в настоящее время) или он должен содержать указатели? Почему?

Производительность и память не имеет значения, используются ли указатели или итераторы. Итераторы - это просто объектно-ориентированные эквиваленты логики указателя. Как и все объектно-ориентированные, они предназначены для того, чтобы облегчить чтение и сопровождение кода, то есть уменьшить вероятность появления ошибок.

Если вы используете STL, имеет смысл также использовать итераторы. Это две концепции, основанные на одной и той же основной идее - расширении C концепциями объектно-ориентированного программирования. Это также промышленный стандарт, предпочитающий итераторы указателям.

Q2

Нужен ли мне указатель на последний элемент data? Как этого избежать?

Вы можете хранить ссылку на базовый vector из Block s и получить конечный итератор через ссылку. Смотрите код ниже. Это предпочтительнее, чем сохранение постоянного конечного значения, потому что итерация не прервется, если новые элементы будут сдвинуты назад к vector из Block s после того, как итератор создан. Я не нашел никаких гарантий в документации C ++, что значение vector::end() не изменяется при изменении vector. Также стоит подумать, что произойдет, если vector будет изменен на другой базовый тип контейнера в будущих версиях вашего кода.

Q3

Как я могу справиться с smallP, когда не на что указывать?

Вы можете оставить все как есть и назвать его неопределенным значением. Этот подход согласуется с подходом стандартной библиотеки к неинициализированным итераторам - они также имеют неопределенное значение, которое не следует разыменовывать.

---

Вы можете поиграть с работающим минимальным примером ниже, вы можете найти его полезным:

Детская площадка: https://ideone.com/eeAKYN

#include<initializer_list>
#include<iostream>
#include<vector>


// Declarations:

// Stores a collection of numbers in the form radix*RADIX_MULTIPLIER + suffix,
// where 0 <= suffix < RADIX_MULTIPLIER.
class Block {
public:
    using SUFFIX_VECTOR_T = std::vector<unsigned short>;

    constexpr static unsigned int RADIX_MULTIPLIER = 100;

private:
    const unsigned short radix;

    // Contains all the suffixes associated with this radix.
    SUFFIX_VECTOR_T suffixes;

public:
    Block(unsigned short radix);
    unsigned short getRadix() const;
    void pushSuffix(const unsigned short suffix);
    std::size_t size() const;
    unsigned int operator[](std::size_t idx) const;
    SUFFIX_VECTOR_T::const_iterator begin() const;
    SUFFIX_VECTOR_T::const_iterator cbegin() const;
    SUFFIX_VECTOR_T::const_iterator end() const;
    SUFFIX_VECTOR_T::const_iterator cend() const;
};

using DATA_VECTOR_T = std::vector<Block>;

class MyIterator :
    public std::iterator<std::input_iterator_tag, unsigned int> {
    const DATA_VECTOR_T& data;
    DATA_VECTOR_T::const_iterator block_it;

    Block::SUFFIX_VECTOR_T::const_iterator suffix_it;

public:
    MyIterator(
        const DATA_VECTOR_T& data,
        const DATA_VECTOR_T::const_iterator start_block_it);
    MyIterator& operator++();
    MyIterator operator++(int);
    bool operator==(const MyIterator& rhs) const;
    bool operator!=(const MyIterator& rhs) const;
    unsigned int operator*() const;
};

// Read-only container which stores a sorted collection of numbers
// memory-efficiently in Blocks.
class MyContainer {
public:
    using const_iterator = MyIterator;

private:
    DATA_VECTOR_T data;

public:
    // The initializer list must be sorted in non-descending order.
    MyContainer(std::initializer_list<unsigned int> il);
    unsigned int operator[](std::size_t idx) const;
    MyContainer::const_iterator begin() const;
    MyContainer::const_iterator cbegin() const;
    MyContainer::const_iterator end() const;
    MyContainer::const_iterator cend() const;
};


// Definitions:

// class Block
Block::Block(unsigned short radix): radix(radix) {}

unsigned short Block::getRadix() const {
    return radix;
}

void Block::pushSuffix(const unsigned short suffix) {
    suffixes.push_back(suffix);
}

std::size_t Block::size() const {
    return suffixes.size();
}

unsigned int Block::operator[](std::size_t idx) const {
    return
        (unsigned int)(radix)*RADIX_MULTIPLIER +
        (unsigned int)(suffixes[idx]);
}

Block::SUFFIX_VECTOR_T::const_iterator Block::begin() const {
    return suffixes.begin();
}

Block::SUFFIX_VECTOR_T::const_iterator Block::cbegin() const {
    return begin();
}

Block::SUFFIX_VECTOR_T::const_iterator Block::end() const {
    return suffixes.end();
}

Block::SUFFIX_VECTOR_T::const_iterator Block::cend() const {
    return end();
}

// class MyContainer
// The initializer list must be sorted in non-descending order.
MyContainer::MyContainer(std::initializer_list<unsigned int> il) {
    if (il.size() == 0) {
        return;
    }

    unsigned short radix = *il.begin() / Block::RADIX_MULTIPLIER;
    data.push_back(Block(radix));
    for (const auto x : il) {
        radix = x / Block::RADIX_MULTIPLIER;
        if (data.back().getRadix() != radix) {
            data.push_back(Block(radix));
        }

        unsigned short suffix = x % Block::RADIX_MULTIPLIER;
        data.back().pushSuffix(suffix);
    }
}

unsigned int MyContainer::operator[](std::size_t idx) const {
    auto data_it = data.begin();

    // Similarly to std::vector::operator[], if idx is out of bounds of the
    // container, the behavior is undefined.
    while (idx >= data_it->size()) {
        idx -= data_it->size();
        ++data_it;
    }

    return (*data_it)[idx];
}

MyContainer::const_iterator MyContainer::begin() const {
    return MyIterator(data, data.cbegin());
}

MyContainer::const_iterator MyContainer::cbegin() const {
    return begin();
}

MyContainer::const_iterator MyContainer::end() const {
    return MyIterator(data, data.end());
}

MyContainer::const_iterator MyContainer::cend() const {
    return end();
}

// class MyIterator
MyIterator::MyIterator(
        const DATA_VECTOR_T& data,
        const DATA_VECTOR_T::const_iterator start_block_it):
        data(data), block_it(start_block_it) {
    if (data.cend() != block_it) {
        suffix_it = block_it->cbegin();
    }
}

MyIterator& MyIterator::operator++() {
    if (data.cend() == block_it) {
        return *this;
    }

    ++suffix_it;

    if (block_it->cend() == suffix_it) {
        ++block_it;

        if (data.cend() != block_it) {
            suffix_it = block_it->cbegin();
        }
    }

    return *this;
}

MyIterator MyIterator::operator++(int) {
    MyIterator tmp = *this;
    operator++();
    return tmp;
}

bool MyIterator::operator==(const MyIterator& rhs) const {
    // If this iterator has reached the end:
    if (data.cend() == block_it) {
        // Only return true if both iterators point to the end of the same
        // object.
        return data.cend() == rhs.block_it;
    }

    return block_it == rhs.block_it
        && suffix_it == rhs.suffix_it;
}

bool MyIterator::operator!=(const MyIterator& rhs) const {
    return !(*this == rhs);
}

unsigned int MyIterator::operator*() const {
    const std::size_t idx = suffix_it - block_it->cbegin();
    return (*block_it)[idx];
}


// Entry point:

int main() {
    std::vector<unsigned int> v = {
        1234, 1254, 1264, 1265, 1267, 1268, 1271, 1819, 1832, 1856, 1867, 1892,
        3210, 3214, 3256, 3289
    };

    // Print the entire vector.
    for (const auto x: v) {
        std::cout << x << "\t";
    }
    std::cout << std::endl;

    // Print a randomly accessed element from the vector.
    std::cout << v[10] << std::endl;


    MyContainer c = {
        1234, 1254, 1264, 1265, 1267, 1268, 1271, 1819, 1832, 1856, 1867, 1892,
        3210, 3214, 3256, 3289
    };

    // Print the entire container.
    for (const auto x: c) {
        std::cout << x << "\t";
    }
    std::cout << std::endl;

    // Print a randomly accessed element from the container.
    std::cout << c[10] << std::endl;

    return 0;
}

---

Ресурсы:

• Перегрузка (c) начало / (c) конец
• cplusplus.com: итератор
• Как правильно реализовать пользовательские итераторы и const_iterators?
• cppreference.com: корректная перегрузка операторов ++
• cplusplus.com: vector :: end
• Каково значение по умолчанию для итератора?