c++ - 是否可以通过地址访问 STL 双端队列元素？

Question

下午好，我们正在尝试对 Windows 内存映射缓存子系统进行简单仿真。我们正在使用多种 STL 数据结构。

1. STL 双端队列，std::deque<Range>访问，它保存并记录有关最近使用到最近使用的内存映射区域的信息。
2. STL 集，std::set<char *> ranges_pointer 可能包含指向 STL 中元素的指针 deque ..

基本上，当我们从 STL 集合中检索指向有效内存映射区域的指针时，我们希望使用该指针以 O(常数时间)直接访问相应的元素双端队列。然后，我们想将该双端队列元素移动到 STL 双端队列的前面，以便可以在 STL 双端队列访问的前面找到对内存映射地址集群的后续请求。

我们从 Stack Overflow 得知，唯一能保证连续地址的 STL 容器是 STL vector 。但是，每次从 STL vector 中移动一个元素时，都需要 O(linear) 时间来将剩余的项目移动或 memcpy 到正确的位置，这可能会很昂贵。相反，当您从 STL 双端队列中移动一个元素时，所有人都必须重新排列被移动元素两侧的 next 和 prev 指针。

我们想知道是否可以编写一种方法来通过地址访问 STL 双端队列元素。尽管 std::allocator 不保证连续的 STL 双端队列地址，也许我们可以使用自定义内存池分配器来获取一大块连续地址。

此外，BOOST 或其他 C++ 框架是否实现了连续双向链表，它们提供随机访问，就像 STL 双端队列一样。 Range 类包含有关每个缓存内存映射区域的所有基本信息，Range 类存储在 std::deque accessess 成员变量中。谢谢。类Range如下所示:

class Range { 
     public:   
         explicit Range(int item){
            mLow = item;
            mHigh = item;
            mPtr  = 0;
            mMapPtr = 0;
         }
         Range(int low, int high, char* ptr = 0,char* mapptr = 0,  
               int currMappedLength = 0){  
            mLow = low;
            mHigh = high;
            mPtr  = ptr;
            mMapPtr = mapptr;
            mMappedLength = currMappedLength;       
         }
         Range(void){  
            mLow = 0;
            mHigh = 0;
            mPtr  = 0;
            mMapPtr = 0;
         }


         ~Range(){
         }

         bool operator<(const Range& rhs) const{
                return mHigh < rhs.mHigh;
         } 
         int low() const { return mLow; }   
         int high() const { return mHigh; }
         char* getMapPtr() const { return mMapPtr; }
         int getMappedLength() const { return mMappedLength; }
     private:   
         int mLow;   // beginning of memory mapped region
         int mHigh;  // end of memory mapped region 
         char* mMapPtr; // return value from MapViewOfFile
         int mMappedLength; // length of memory mapped region
}; // class Range 

Answer 1

与其使用 set 来保存地址，不如使用包含地址的 map 和 deque 中的迭代器怎么样？

请注意，将元素从双端队列的中间移动到开头或结尾不会比对 vector 执行此操作更快。您可能需要考虑使用 list。