stl deque الوصول إلى الفهرس هل O (1)؟

Question

لقد قرأت أن الوصول إلى العناصر حسب فهرس الموضع يمكن أن يتم في وقت ثابت في Deque STL. على حد علمي ، قد يتم تخزين العناصر الموجودة في عملية إزالة في العديد من المواقع غير المتجددة ، مما يلغي الوصول الآمن من خلال حساب المؤشر. علي سبيل المثال:

abc-> defghi-> jkl-> mnop

تتكون عناصر deque أعلاه من شخصية واحدة. تشير مجموعة الأحرف في مجموعة واحدة إلى أنه يتم تخصيصها في ذاكرة متجاورة (على سبيل المثال ABC في كتلة واحدة من الذاكرة ، يقع Defhi في كتلة أخرى من الذاكرة ، وما إلى ذلك). هل يمكن لأي شخص أن يشرح كيف يمكن الوصول إلى فهرس الموضع في وقت ثابت ، خاصة إذا كان العنصر الذي سيتم الوصول إليه في الكتلة الثانية؟ أم هل لدى deque مؤشر إلى مجموعة من الكتل؟

تحديث: أو هل هناك أي تطبيق مشترك آخر ل deque؟

Answer 1

لقد وجدت هذا التنفيذ deque من ويكيبيديا:

تخزين المحتويات في صفائف أصغر متعددة ، وتخصيص صفائف إضافية في البداية أو النهاية حسب الحاجة. يتم تنفيذ الفهرسة عن طريق الحفاظ على صفيف ديناميكي يحتوي على مؤشرات لكل من المصفوفات الأصغر.

أعتقد أنه يجيب على سؤالي.

Answer 2

البيانات في deque يتم تخزينها بواسطة chuncks من ناقل الحجم الثابت ، وهو

مشهور من قبل أ map(وهو أيضًا جزء كبير من المتجه ، لكن حجمه قد يتغير)

رمز الجزء الرئيسي ل deque iterator كما أدناه:

/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
    typedef __deque_iterator<T, buff_size>              iterator;
    typedef T**                                         map_pointer;

    // pointer to the chunk
    T* cur;       
    T* first;     // the begin of the chunk
    T* last;      // the end of the chunk

    //because the pointer may skip to other chunk
    //so this pointer to the map
    map_pointer node;    // pointer to the map
}

رمز الجزء الرئيسي ل deque كما أدناه:

/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
    public:
        typedef T              value_type;
        typedef T&            reference;
        typedef T*            pointer;
        typedef __deque_iterator<T, buff_size> iterator;

        typedef size_t        size_type;
        typedef ptrdiff_t     difference_type;

    protected:
        typedef pointer*      map_pointer;

        // allocate memory for the chunk 
        typedef allocator<value_type> dataAllocator;

        // allocate memory for map 
        typedef allocator<pointer>    mapAllocator;

    private:
        //data members

        iterator start;
        iterator finish;

        map_pointer map;
        size_type   map_size;
}

أدناه سأعطيك الكود الأساسي لـ deque, ، بشكل رئيسي حول جزأين:

1. التكرار

2. كيفية الوصول العشوائي deque تدرك

1. التكرار (__deque_iterator)

المشكلة الرئيسية للتكرار هي ، عندما ++ ، - التكرار ، قد تتخطى الجزء الآخر (إذا كان مؤشرًا إلى حافة الجزء). على سبيل المثال ، هناك ثلاث قطع بيانات: chunk 1,chunk 2,chunk 3.

ال pointer1 مؤشرات لبدء chunk 2, ، عندما المشغل --pointer سوف مؤشر حتى نهاية chunk 1, ، حتى pointer2.

أدناه سأقدم الوظيفة الرئيسية لـ __deque_iterator:

أولاً ، تخطي أي قطعة:

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + chunk_size();
}

نلاحظ أن chunk_size() الوظيفة التي تحسب حجم القطعة ، يمكنك التفكير في إرجاع 8 لتبسيط هنا.

operator* احصل على البيانات في الجزء

reference operator*()const{
    return *cur;
}

operator++, --

// أشكال بادئة الزيادة

self& operator++(){
    ++cur;
    if (cur == last){      //if it reach the end of the chunk
        set_node(node + 1);//skip to the next chunk
        cur = first;
    }
    return *this;
}

// postfix forms of increment
self operator++(int){
    self tmp = *this;
    ++*this;//invoke prefix ++
    return tmp;
}
self& operator--(){
    if(cur == first){      // if it pointer to the begin of the chunk
        set_node(node - 1);//skip to the prev chunk
        cur = last;
    }
    --cur;
    return *this;
}

self operator--(int){
    self tmp = *this;
    --*this;
    return tmp;
}

ITerator تخطي الخطوات / الوصول العشوائي

self& operator+=(difference_type n){ // n can be postive or negative
    difference_type offset = n + (cur - first);
    if(offset >=0 && offset < difference_type(buffer_size())){
        // in the same chunk
        cur += n;
    }else{//not in the same chunk
        difference_type node_offset;
        if (offset > 0){
            node_offset = offset / difference_type(chunk_size());
        }else{
            node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
        }
        // skip to the new chunk
        set_node(node + node_offset);
        // set new cur
        cur = first + (offset - node_offset * chunk_size());
    }

    return *this;
}

// skip n steps
self operator+(difference_type n)const{
    self tmp = *this;
    return tmp+= n; //reuse  operator +=
}

self& operator-=(difference_type n){
    return *this += -n; //reuse operator +=
}

self operator-(difference_type n)const{
    self tmp = *this;
    return tmp -= n; //reuse operator +=
}

// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
    return *(*this + n);
}

2. وصول عشوائي deque عناصر

وظيفة مشتركة deque

iterator begin(){return start;}
iterator end(){return finish;}

reference front(){
    //invoke __deque_iterator operator*
    // return start's member *cur
    return *start;
}

reference back(){
    // cna't use *finish
    iterator tmp = finish;
    --tmp; 
    return *tmp; //return finish's  *cur
}

reference operator[](size_type n){
    //random access, use __deque_iterator operator[]
    return start[n];
}

ترى أيضًا هذا السؤال الذي يعطي الكود الرئيسي لـ deque

https://stackoverflow.com/a/50959796/6329006

Answer 3

يمكن أن يكون أحد التطبيقات المحتملة عبارة عن مجموعة ديناميكية من المصفوفات ذات الحجم الكتاب ؛ يمكن إضافة مثل هذا الصفيف الحجم إلى أي من الطرفين عند الحاجة إلى مزيد من المساحة. جميع المصفوفات ممتلئة باستثناء ، ربما ، لأول مرة والأخير التي يمكن أن تكون فارغة جزئيا. هذا يعني معرفة حجم كل صفيف وعدد العناصر المستخدمة في الصفيف الأول يمكن للمرء بسهولة العثور على موضع لعنصر حسب الفهرس.
http://cpp-tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html

Answer 4

إذا تم تنفيذ Deque ك المخزن المؤقت حلقة في قمة ال std::vector, ، الذي يعيد نفسه عندما ينمو في الحجم ، ثم الوصول إلى الفهرس هو بالفعل O (1).

يقدم المعيار دليلًا على أن هذا التنفيذ كان مقصودًا-على الأقل يتوافق مع المعيار في تقديرات التعقيد. الجمل 23.2.1.3/4 و 23.2.1.3/5 تتطلب ذلك

• يتطلب الإدراج في البداية أو إلى نهاية عملية التخلص وقتًا ثابتًا ، بينما يتطلب الإدراج في الوسط وقتًا خطيًا لحجم Deque

• عند محو العناصر من Deque ، قد يطلق على أكبر عدد ممكن من مشغلي المهام ، حيث أن المسافة من العناصر التي يتم محوها إلى نهاية deque هي.

وبالطبع ، يجب أن تعتمد على المتطلبات القياسية بدلاً من رؤيتك الخاصة حول كيفية تنفيذ الحاويات والخوارزميات.

ملاحظة أن المعيار يتطلب أكثر من هاتين النقطتين المدرجة أعلاه. كما يطرح شرط أن تظل الإشارات إلى العناصر صالحة بين الإدراج في الجزء الخلفي أو الأمامي من deque. يمكن أن يكون هذا الأمر راضياً إذا كان المخزن المؤقت الحلقي يحتوي على مؤشرات للعناصر الفعلية بدلاً من العناصر نفسها. على أي حال ، توضح إجابتي فكرة أن التطبيقات المتعددة قد تلبي متطلبات معينة.