Skip to content

[C++] STL 中的 deque 筆記

deque 是 C++ 標準模板函式庫（Standard Template Library, STL）中的雙向佇列容器（Double-ended Queue），跟 vector 相似，不過在 vector 中若是要添加新元素至開端，其時間複雜度為 O(N)，但在 deque 中則是 O(1)。同樣地，也能在我們需要儲存更多元素的時候自動擴展空間，讓我們不必煩惱佇列長度的問題。

很容易混淆的是，deque 實際上仍然是使用連續記憶體空間實作而成的，並不是雙向的 linked list。

以下就簡單介紹該如何使用 deque，首先是不同函式使用的示意圖，接著是陳列出我要記錄的函式。

  • push_back()
  • push_front()
  • pop_back()
  • pop_front()
  • back()
  • front()
  • insert()
  • erase()
  • clear()
  • size()
  • empty()
  • begin()
  • end()

push_back()

push_back() 會在 deque 的最尾端新增元素。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    d.push_back(6);
    d.push_back(7);
    d.push_back(8);

    for (auto n: d) {
        cout << n << endl;
    }

    return 0;
}



Output:

1
2
3
4
5
6
7
8

push_front()

跟 push_back() 不同，push_front() 是在 deque 的開頭新增元素。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    d.push_front(0);
    d.push_front(-1);
    d.push_front(-2);

    for (auto n: d) {
        cout << n << endl;
    }

    return 0;
}



Output:

-2
-1
0
1
2
3
4
5

pop_back()

pop_back() 會移除 deque 最尾端的元素。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    d.pop_back();
    d.pop_back();

    for (auto n: d) {
        cout << n << endl;
    }

    return 0;
}



Output:

1
2
3

pop_front()

很相似地，pop_front() 是用於移除 deque 最開頭的元素。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    d.pop_front();
    d.pop_front();

    for (auto n: d) {
        cout << n << endl;
    }

    return 0;
}



Output:

3
4
5

back()

back() 會取出 deque 最尾端的元素（並不是移除的意思）。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // back()
    cout << d.back() << endl;
    cout << d.back() << endl;

    return 0;
}



Output:

5
5

可以看到最尾端的元素並沒有被移除。

front()

front() 跟 back() 很相似，不過 front() 是回傳 deque 最開頭的元素。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // front()
    cout << d.front() << endl;

    return 0;
}



Output:

1

begin()

begin() 返回一個指向 deque 開頭的迭代器，可以用來迭代 deque 內的元素、或是指定特定的 index。

迭代印出所有元素配合 end() 一起示範。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // begin()
    cout << *d.begin() << endl;

    return 0;
}



Output:

1

可以看到，確實指向 deque 開頭。

end()

end() 則是指向 deque 結尾，不是最後一個元素，而是最後一個元素的下一個位置。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // Print
    deque<int>::iterator it = d.begin();
    while (it != d.end()) {
        cout << *it << endl;
        it++;
    }

    return 0;
}



Output:

1
2
3
4
5

insert()

d.insert(position, n, val)
  • position: 插入元素的 index 值
  • n: 元素插入次數
  • val: 插入的元素值

以下看個簡單的範例：

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // insert()
    d.insert(d.begin(), 3, 100);

    // Print
    for (auto n: d) {
        cout << n << endl;
    }

    return 0;
}



Output:

100
100
100
1
2
3
4
5

erase()

跟 insert() 不同，erase() 是刪除元素，需要使用迭代器指定刪除的元素或位置，同時也會返回指向刪除元素下一元素的迭代器。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // erase()
    d.erase(d.begin());

    // Print
    for (auto n: d) {
        cout << n << endl;
    }

    return 0;
}



Output:

2
3
4
5

（本來輸出有誤，感謝網友 CLARE0710 告知）

clear()

清空整個 deque 佇列。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};
    d.clear();

    return 0;
}


size()

檢查 deque 的尺寸。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // size()
    cout << "size: " << d.size() << endl;
    
    return 0;
}



Output:

size: 5

empty()

如果 deque 佇列為空返回 1；若是存在任何元素，則返回 0。

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> d = {1, 2, 3, 4, 5};

    // Not empty
    cout << "Before clearing: " << d.empty() << endl;

    // clear()
    d.clear();

    // Empty
    cout << "After clearing: " << d.empty() << endl;
    
    return 0;
}



Output:

Before clearing: 0
After clearing: 1

References

Read More

Tags:

2 thoughts on “[C++] STL 中的 deque 筆記”

Leave a Reply