The List and Deque Containers in C++

Container Library Sequences in C++ Simplified – Part 10

Forward: In this part of the series, I illustrate the difference between the List and the vector, and the difference between the deque and the vector.

By: Chrysanthus Date Published: 24 Aug 2012

Introduction

This is part 10 of my series, Containers Library Sequences in C++, Simplified. Anything that has the fundamental structure of an array is called a list. However, C++ has a sequence container called the List that behaves like the vector but it is not a vector. There is another container similar to the vector, called, the Deque. These two new containers have been mentioned previously. In this part of the series, I illustrate the difference between the List and the vector, and the difference between the deque and the vector. To use the list you have to include the list header file. I assume you have read all the previous parts of this series. To use the deque you have to include the deque header file.

Note: If you cannot see the code or if you think anything is missing (broken link, image absent), just contact me at forchatrans@yahoo.com. That is, contact me for the slightest problem you have about what you are reading.

Summary of Difference between List and Vector
The list sequence has all of the functionality given for the vector except subscripting (the array [] operator) and the at() method. It has five important new methods called the splice(), merge(), sort(), push_front(), pop_front(). The details of these methods are given below.

When to use which Sequence
The vector is a general-purpose sequence container. The list should be used when there are frequent insertions and deletions from the middle of the sequence. The deque should be used when most insertions and deletions take place at the beginning or at the end of the sequence. When you cannot make a choice between the List and the Deque, use the vector.

Reading the value of a List Element
Dereferencing the iterator gives the value of the element in the list.

void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);

Assume that you have two lists, x and y and y is your list of interest. You can remove a portion of elements from the list, x and insert it at a position in the list of interest, y. This is splicing in C++. The method returns nothing. Remember, an iterator always refers to a next element. The first and last positions for the portion of list x are indicated by two different iterators for x. The insert position for list y is indicated by an iterator for y, which is the first parameter above; the second two parameters are for x; the insertion goes before the element the y iterator is pointing to.

In the following program, the second and third elements of the list, herLst are removed and inserted before the second element of the list, myLst. Read and try the following program:

#include <iostream>
#include <list>

using namespace std;

int main()
    {
        //list of interest
        list<char> myLst;
        myLst.push_back('A');
        myLst.push_back('B');

        //the other list
        list<char> herLst;
        herLst.push_back('C');
        herLst.push_back('D');
        herLst.push_back('E');
        herLst.push_back('F');

        //point an iterator for myLst to index 1, the insert position
        _List_iterator<char> myIter = myLst.begin();
        ++myIter;

        //point an iterator for herLst to index 1, the first position of portion
        _List_iterator<char> herIterF = herLst.begin();
        ++herIterF;

        //point another iterator for herLst to index 3, the last position of portion
        _List_iterator<char> herIterL = herLst.begin();
        ++herIterL;
        ++herIterL;
        ++herIterL;

        //splicing
        myLst.splice(myIter, herLst, herIterF, herIterL);

        //New iterators that point to the beginning of both lists
        _List_iterator<char> mIter = myLst.begin();
        _List_iterator<char> hIter = herLst.begin();

        //display the present values of myLst to confirm splicing
        cout << *mIter << '\n';
        cout << *++mIter << '\n';
        cout << *++mIter << '\n';
        cout << *++mIter << '\n';
        cout << '\n';

        //display the present values of herLst to confirm splicing
        cout << *hIter << '\n';
        cout << *++hIter << '\n';

        return 0;
    }

Note: In the portion extracted, the last element extracted is the element just before the one referred to by “iterator last” in the syntax. Also note that you can instantiate as many iterators as you want from the same list (sequence).

void merge(list<T,Allocator>& x);
This method removes all the elements of the list, x and joins it with the list of interest (y). x becomes empty. Read and try the following code:

#include <iostream>
#include <list>

using namespace std;

int main()
    {
        //list of interest
        list<int> myLst;
        myLst.push_back(30);
        myLst.push_back(40);
        myLst.push_back(50);
        myLst.push_back(60);

        //the other list
        list<int> herLst;
        herLst.push_back(10);
        herLst.push_back(20);

        //merge herLst into myLst
        myLst.merge(herLst);

        //display the present values of myLst
        _List_iterator<int> myIter = myLst.begin();
        cout << *myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << '\n';

        //display the size of myLst
        cout << herLst.size() << '\n';

        return 0;
    }

Note: with this method the way the resulting merged list of interest is sorted, is not guaranteed.

Note the way the iterator type for list has been written here. It is from the namespace standard. There is another version of merge that will do some sorting; however, I will not go into that. Do not worry: after merging, you can still sort the whole resulting list, thanks to the sort() method of the List sequence.

void sort();
This method sorts the list of interest in ascending order. The function returns nothing. Any method returning void returns nothing. Read and try the following code:

#include <iostream>
#include <list>
#include <string>

using namespace std;

int main()
    {
        //list of interest
        list<string> myLst;
        myLst.push_back("orange");
        myLst.push_back("pear");
        myLst.push_back("cucumber");
        myLst.push_back("apple");
        myLst.push_back("pineapple");

        //sort
        myLst.sort();

        //display the present values of myLst
        _List_iterator<string> myIter = myLst.begin();
        cout << *myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';

        cout << '\n';

        return 0;
    }

void push_front(const T& x);
This method forces a new element at the beginning of the list, pushing the other elements one step downward. Read and try the following code:

#include <iostream>
#include <list>

using namespace std;

int main()
    {
        //list of interest
        list<char> myLst;
        myLst.push_back('B');
        myLst.push_back('C');
        myLst.push_back('D');
        myLst.push_back('E');

        //add element at the beginning
        myLst.push_front('A');

        //display the present values of myLst
        _List_iterator<char> myIter = myLst.begin();
        cout << *myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';

        return 0;
    }

void pop_front();
This method removes the first element off the list (and throw away) bringing the rest of the elements one step upward and reducing the size of the list by one. Read and try the following code:

#include <iostream>
#include <list>

using namespace std;

int main()
    {
        //list of interest
        list<char> myLst;
        myLst.push_back('A');
        myLst.push_back('B');
        myLst.push_back('C');
        myLst.push_back('D');
        myLst.push_back('E');

        //remove element at the beginning
        myLst.pop_front();

        //display the present values of myLst
        _List_iterator<char> myIter = myLst.begin();
        cout << *myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << *++myIter << '\n';
        cout << '\n';

        //display the size of the list
        cout << myLst.size();

        return 0;
    }

Note: The iterator type for list is _List_iterator<T>

We have seen the important differences between the List and the Vector. Let us now talk about the deque (there is not much to say about it).

The Deque
The deque sequence container is like an amalgam of the vector and the list classes. In particular it supports all the vector methods and for the list it supports the push_front() and pop_front() methods. So if you can use the vector and the list, you can use the deque. Remember, always use the vector; however, when most of your insertions and deletions take place at the beginning or at the end of the sequence, use the deque, and when most of your insertions and deletions are in the middle of the sequence, use the list. Let us just look at a simple use of the deque, just to give you confidence, and then end this part of the series. Read and try the following code:

#include <iostream>
#include <deque>

using namespace std;

int main()
    {
        //deque of interest
        deque<char> myDeq;
        myDeq[0] = 'B';
        myDeq[1] = 'C';

        _Deque_iterator<char, char&, char*> iter = myDeq.begin();
        myDeq.insert(iter, 'A');

        cout << myDeq[0] << '\n';
        cout << myDeq[1] << '\n';
        cout << myDeq[2] << '\n';

        return 0;
    }

Note: The iterator type for deque is _Deque_iterator<T, T&, T*>. Do not forget to include the deque header before you use the deque.

We have finished with this part of the series. We take a break and continue in the next part.

Chrys

Broad Network

Related Articles

The List and Deque Containers in C++

Container Library Sequences in C++ Simplified – Part 10

Introduction

Related Courses

Comments