Is it possible to access a STL deque element by its address?

Good afternoon , We are trying to make a simple emulation of the Windows memory mapped caching subsystem. We are using several STL data structures.

1. A STL deque , std::deque<Range> accesses, which holds and records information about the last recently used to the most recently used memory mapped regions.
2. A STL set, std::set<char *> ranges_pointer which might hold pointers to the elements in the STL deque..

Basically, when we retrieve a pointer to a valid memory mapped region from the STL set , we would like to use that pointer to direcly access the corresponding element deque in O(constant time). Then, we would like to move that deque element to the front of the STL deque so that that subsequent reguests for clusters of memory mapped addreses can be found at the front of the STL deque accesses.

We know from Stack Overflow that the only STL container that guarantees contingous addresses is STL vector. However, every time one moves a element from a STL vector, it takes O(linear) time to shift or memcpy the remaining items into the right location,This could be expensive. In contrast, when you move a element from STL deque, all one has to rearrange the next and prev pointers on both sides of the element that is moved.

We were wondering if one could write a method to access a STL deque element by its address. Although the std::allocator does not guarantee contiguous STL deque adresses, perhaps we could use a custom memory pool allocator to get a chunk of contiguous addresses.

Also, do BOOST or other C++ frameworks implement contiguous doubly linked lists which offer random access just like STL deque. The class Range holds all the essential information about every cached memory mapped region, The class Range is stored in the the std::deque accessess member variable. Thank you. The class Range is shown below:

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 

---

Rather than using a set to hold the addresses, how about a map that contains the address and an iterator into the deque?

Note that moving an element from the middle of a deque to the beginning or end is going to be no faster than doing it for a vector. You might want to think about using a list.