list and deque in STL

दो और sequence containers

[vector](/tutorial/cpp/vector/?lang=hi) के बाद STL दो और general-purpose sequence containers देती है:

• **std::list** (header <list>) — doubly linked list। हर element अपने node में रहता है, जिसमें पिछले और अगले node के pointers होते हैं।
• **std::deque** (header <deque>, उच्चारण "डेक") — double-ended queue। Elements कई fixed-size blocks में रखे जाते हैं, इसलिए यह आगे और पीछे दोनों तरफ़ बढ़ सकती है।

list :  [78] <-> [91] <-> [66] <-> [84]      (nodes memory में कहीं भी)
deque:  [ block ][ block ][ block ]          (दोनों सिरों पर तेज़ बढ़त)
vector: [ 78 | 91 | 66 | 84 | ... ]          (एक लगातार block)

std::list

List के आम functions

operator[] नहीं है — 5वें element तक पहुँचने के लिए शुरुआत से चलना पड़ता है।

List उदाहरण

#include <iostream>
#include <list>

void print(const std::list<int>& l) {
    for (int x : l) std::cout << x << " ";
    std::cout << "\n";
}

int main() {
    std::list<int> tokens = {40, 10, 30};
    tokens.push_front(5);           // 5 40 10 30
    tokens.push_back(20);           // 5 40 10 30 20
    print(tokens);

    auto it = tokens.begin();
    std::advance(it, 2);            // 10 की ओर इशारा
    tokens.insert(it, 99);          // 10 से पहले जोड़ो
    print(tokens);

    tokens.remove(40);              // हर 40 हटाओ
    tokens.sort();                  // list::sort, std::sort नहीं
    print(tokens);

    tokens.reverse();
    print(tokens);
    return 0;
}

std::deque

Deque के आम functions

Deque उदाहरण: हाल के marks की sliding window

#include <iostream>
#include <deque>

int main() {
    std::deque<int> lastThree;
    int tests[] = {62, 70, 58, 81, 77};

    for (int m : tests) {
        lastThree.push_back(m);
        if (lastThree.size() > 3) lastThree.pop_front();   // सिर्फ 3 रखो

        int sum = 0;
        for (int x : lastThree) sum += x;
        std::cout << "after " << m << ": average of last "
                  << lastThree.size() << " = " << sum / lastThree.size() << "\n";
    }
    std::cout << "oldest kept: " << lastThree[0]
              << ", newest: " << lastThree.back() << "\n";
    return 0;
}

पीछे जोड़ना और आगे से हटाना दोनों O(1) हैं — vector में erase(begin()) पर हर element खिसकाना पड़ता।

vector vs list vs deque

कौन-सा चुनें?

• Default: vector।
• दोनों सिरों पर तेज़ push/pop (queues, sliding windows, सीमित undo): deque।
• Iterators valid रखते हुए बीच में बहुत insert/delete, या splice से हिस्से ले जाने हों: list।

असल में list students की उम्मीद से कम चुनी जाती है: छोटे और मध्यम sizes में cache के कारण बीच के insertions में भी vector अक्सर जीतता है।

आम गलतियाँ

• list पर std::sort(l.begin(), l.end()) — compile error; l.sort() लें।
• List पर l[2] चलने की उम्मीद करना।
• खाली container पर front() या pop_front() — undefined behaviour; पहले empty() check करें।
• Unsorted list पर unique() से सारे duplicates हटने की उम्मीद — यह सिर्फ *लगातार* duplicates हटाता है।
• Deque के elements को लगातार मानकर &d[0] किसी array वाले C function को भेजना।

सारांश

• list = doubly linked list: iterator के साथ कहीं भी O(1) insert/erase, indexing नहीं।
• deque = double-ended queue: दोनों सिरों पर O(1) और O(1) indexing।
• list के अपने sort, remove, unique, merge, splice हैं।
• Default अब भी vector; दोनों सिरों के काम के लिए deque, बीच में ज़्यादा बदलाव के लिए list।

संबंधित: STL परिचय, vector, stack और queue, iterators।