用于按需加载元素的容器的 C++ 随机访问迭代器

Question

我目前正在做一个需要从文件加载消息的小项目。消息按顺序存储在文件中，文件可能会变得很大，因此将整个文件内容加载到内存中是没有意义的。

因此我们决定实现一个 FileReader 类，它能够快速移动到文件中的特定元素并根据请求加载它们。常用的有以下几行

SpecificMessage m;
FileReader fr;
fr.open("file.bin");
fr.moveTo(120); // Move to Message #120
fr.read(&m);    // Try deserializing as SpecificMessage 

FileReader 本身工作得很好。因此，我们也考虑过添加符合 STL 的迭代器支持:一个随机访问迭代器，它提供对特定消息的只读引用。使用方法如下

for (auto iter = fr.begin<SpecificMessage>(); iter != fr.end<SpecificMessage>(); ++iter) {
  // ...
}

备注:以上假定文件仅包含 SpecificMessage 类型的消息。我们一直在使用 boost::iterator_facade 来简化实现。

现在我的问题归结为:如何正确实现迭代器？因为 FileReader 实际上并不在内部保存消息序列，而是根据请求加载它们。

到目前为止我们尝试了什么:

将消息存储为迭代器成员

此方法将消息存储在迭代器实例中。这对于简单的用例非常有用，但对于更复杂的用途却失败了。例如。 std::reverse_iterator 有一个看起来像这样的解引用操作

 reference operator*() const
 {  // return designated value
   _RanIt _Tmp = current;
   return (*--_Tmp);
 }

这打破了我们的方法，因为返回了对来自临时迭代器的消息的引用。

使引用类型等于值类型

@DDrmmr 在评论中建议使引用类型等于值类型，以便返回内部存储对象的拷贝。但是，我认为这对于将 -> 运算符实现为

的反向迭代器无效

pointer operator->() const {
  return (&**this);
}

它自己取消引用，调用 *operator，然后返回一个临时文件的拷贝，最后返回这个临时文件的地址。

在外部存储消息

或者，我考虑将消息存储在外部:

SpecificMessage m;
auto iter = fr.begin<SpecificMessage>(&m);
// ...

这似乎也有缺陷

auto iter2 = iter + 2

这将使 iter2 和 iter 指向相同的内容。

Answer 1

正如我在其他回答中暗示的那样，您可以考虑使用内存映射文件。在您询问的评论中:

As far as memory mapped files is concerned, this seems not what I want to have, as how would you provide an iterator over SpecificMessages for them?

好吧，如果您的 SpecificMessage 是 POD 类型，您可以只是直接迭代原始内存。如果没有，你可以有一个反序列化助手(因为你已经有了)并使用 Boost transform_iterator 按需进行反序列化。

请注意，我们可以使内存映射文件托管，这实际上意味着您可以将其用作常规堆，并且可以存储所有标准容器。这包括基于节点的容器(例如 map<>)、动态大小的容器(例如 vector<>)以及固定大小的容器(array<>)——以及它们的任意组合。

这是一个演示，它采用简单的 SpecificMessage包含一个字符串，并将其直接(反)反序列化到共享内存中:

using blob_t       = shm::vector<uint8_t>;
using shared_blobs = shm::vector<blob_t>;

您感兴趣的部分是消费部分:

bip::managed_mapped_file mmf(bip::open_only, DBASE_FNAME);
shared_blobs* table = mmf.find_or_construct<shared_blobs>("blob_table")(mmf.get_segment_manager());

using It = boost::transform_iterator<LazyLoader<SpecificMessage>, shared_blobs::const_reverse_iterator>;

// for fun, let's reverse the blobs
for (It first(table->rbegin()), last(table->rend()); first < last; first+=13)
    std::cout << "blob: '" << first->contents << "'\n";

// any kind of random access is okay, though:
auto random = rand() % table->size();
SpecificMessage msg;
load(table->at(random), msg);
std::cout << "Random blob #" << random << ": '" << msg.contents << "'\n";

所以这会以相反的顺序打印第 13 条消息，然后是一个随机的 blob。

完整演示

在线示例使用来源的行作为“消息”。

Live On Coliru

#include <boost/interprocess/file_mapping.hpp>
#include <boost/interprocess/managed_mapped_file.hpp>
#include <boost/container/scoped_allocator.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <iostream>

#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/iterator_range.hpp>

static char const* DBASE_FNAME = "database.map";

namespace bip = boost::interprocess;

namespace shm {
    using segment_manager = bip::managed_mapped_file::segment_manager;
    template <typename T> using allocator = boost::container::scoped_allocator_adaptor<bip::allocator<T, segment_manager> >;
    template <typename T> using vector    = bip::vector<T, allocator<T> >;
}

using blob_t       = shm::vector<uint8_t>;
using shared_blobs = shm::vector<blob_t>;

struct SpecificMessage {
    // for demonstration purposes, just a string; could be anything serialized
    std::string contents;

    // trivial save/load serialization code:
    template <typename Blob>
    friend bool save(Blob& blob, SpecificMessage const& msg) {
        blob.assign(msg.contents.begin(), msg.contents.end());
        return true;
    }

    template <typename Blob>
    friend bool load(Blob const& blob, SpecificMessage& msg) {
        msg.contents.assign(blob.begin(), blob.end());
        return true;
    }
};

template <typename Message> struct LazyLoader {
    using type = Message;

    Message operator()(blob_t const& blob) const {
        Message result;
        if (!load(blob, result)) throw std::bad_cast(); // TODO custom excepion
        return result;
    }
};

///////
// for demo, create some database contents
void create_database_file() {
    bip::file_mapping::remove(DBASE_FNAME);
    bip::managed_mapped_file mmf(bip::open_or_create, DBASE_FNAME, 1ul<<20); // Even sparse file size is limited on Coliru

    shared_blobs* table = mmf.find_or_construct<shared_blobs>("blob_table")(mmf.get_segment_manager());

    std::ifstream ifs("main.cpp");
    std::string line;
    while (std::getline(ifs, line)) {
        table->emplace_back();
        save(table->back(), SpecificMessage { line });
    }

    std::cout << "Created blob table consisting of " << table->size() << " blobs\n";
}

///////

void display_random_messages() {
    bip::managed_mapped_file mmf(bip::open_only, DBASE_FNAME);
    shared_blobs* table = mmf.find_or_construct<shared_blobs>("blob_table")(mmf.get_segment_manager());

    using It = boost::transform_iterator<LazyLoader<SpecificMessage>, shared_blobs::const_reverse_iterator>;

    // for fun, let's reverse the blobs
    for (It first(table->rbegin()), last(table->rend()); first < last; first+=13)
        std::cout << "blob: '" << first->contents << "'\n";

    // any kind of random access is okay, though:
    auto random = rand() % table->size();
    SpecificMessage msg;
    load(table->at(random), msg);
    std::cout << "Random blob #" << random << ": '" << msg.contents << "'\n";
}

int main()
{
#ifndef CONSUMER_ONLY
    create_database_file();
#endif

    srand(time(NULL));
    display_random_messages();
}