Skip to content

[C++] How to Use “deque” of STL

deque is the double-ended queue container provided by C++ Standard Template Library (STL), it is similar with vector container, but if you want to add a new element to the beginning in a vector, the time complexity is O(N), but in a deque it is O(1).

deque can automatically expand the space when we need to store more elements, so that we don’t have to worry about the size of the queue.

It is easy to confuse that deque is actually still implemented using contiguous memory space, not a two-way linked list.

The following is a introduce of how to use deque.

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

push_back()

push_back() can add new element in the tail of 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()

Unlike push_back(), push_front() adds elements at the beginning of 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() will pop the last element of 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() will pop the first element of 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() will take out the last element of the deque and will not remove it.

#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

You can see that the last element has not been removed.

front()

front() is similar to back(), but front() is the first element that returns the 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() returns an iterator to point to the beginning of the deque, which can be used to iterate the elements in the deque or specify a specific index.

Print all the elements iteratively with 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

As you can see, it does point to the beginning of deque.

end()

end() refers to the end of the deque, not the last element, but the next position of the last element.

#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: the index value of the inserted element
  • n: number of inserting element
  • val: value of inserting element

Let’s take a simple example:

#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()

erase() deletes an element, you need to use an iterator to point to the deleted element or position, and it will also return an iterator pointing to the next element of the deleted element.

#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

(The original output was wrong, thanks to CLARE0710 for informing)

clear()

Clear all the deque container.

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


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

    return 0;
}


size()

Return the size of the 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()

If deque is empty, return 1; if there are any elements exist, return 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:

Leave a Reply