STL List by ub40

STL List

A list is a sequential container optimised for insertions and deletions of data elements at arbitrary locations within the collection.

However, a list does not provide index-based access to the elements in the collection. STL list is implemented as a doubly linked list. A doubly linked list is a data structure in which each element has a link to the next element and a link to the previous element. A list should be used when the order of elements within the list and efficient arbitrary insertions and deletions are required by the application.

 

Following are some of the key methods of STL’s list class. These do not include the methods related to iterators, which are described in the next section.

 

Method

Description

list()

Creates an empty list.

list(size_type n)

Creates a list of n elements initialised to their default value.

list(size_type n, const T& value)

Creates a list of n elements initialised to value.

T& back(void)

Returns a reference to the last element in the list.

T& front(void)

Returns a reference to the first element in the list.

void push_back(const T& value)

Inserts a value to the end of the list.

void push_front(const T& value)

Inserts a value to the beginning to the list.

void pop_back(void)

Deletes the last element of the list.

void pop_front(void)

Deletes the first element of the list.

void remove(const T& value)

Deletes all elements that match the value. Comparison is performed using the == operator.

void reverse(void)

Reverses the order of elements in the list.

size_type size(void)

Returns the number of entries contained in the list.

void sort(void)

Sorts the entries contained in the list using the < operator.

Therefore, if all the methods of the list container are to be used on a collection of objects of a specific class, == and < operators must be overloaded for that class.

The following program shows how a list of objects of the Person class is populated and then sorted using the sort function of the list class. The class Person has the < operator overloaded. The sort method of the list class, therefore, arranges the elements in the list in the order of age with the youngest person first. The printAndDelete function removes the elements from the front of the list and prints them. It is possible to access the elements of a list without deleting them from the list using iterators. This is discussed in the next section.

#include <list>
#include <iostream>
#include <string>
using namespace std;

class Person
{
private:
string name;
int age;
string nINumber;

public:
Person(string inName, int inAge, string inNINumber)
{
name = inName;
age = inAge;
nINumber = inNINumber;
}

string& getName(void)
{
return name;
}

int getAge(void)
{
return age;
}

string& getNINumber(void)
{
return nINumber;
}

bool operator == (const Person& p)
{
return (name == p.name);
}

bool operator < (const Person& p)
{
return (age < p.age);
}
};

void populatePeople(list<Person>& peopleList)
{
char continueFlag = 'y';
string name;
int age;
string nINumber;
while (continueFlag == 'y')
{
cout << "Enter name ";
cin >> name;
cout << "Enter age ";
cin >> age;
cout << "Enter National Insurance number ";
cin >> nINumber;

Person p(name, age, nINumber);
peopleList.push_back(p);

cout << "Enter y to add another, any other key to exit:";
cin.get();
continueFlag = cin.get();
cin.get();
}
}

void printAndDeleteList(list<Person>& peopleList)
{
while (peopleList.size() > 0)
{
Person p = peopleList.front();
peopleList.pop_front();
cout << p.getName() << ":" << p.getAge() << ":" << p.getNINumber() << endl;
}
}

int main(void)
{
list<Person> peopleList;
populatePeople(peopleList);
peopleList.sort();
printAndDeleteList(peopleList);
return(0);
}

Following lines list an interaction with this program,

 

Enter name Amna
Enter age 33
Enter National Insurance number 1357
Enter y to add another, any other key to exit:y
Enter name Teymour
Enter age 8
Enter National Insurance number 5319
Enter y to add another, any other key to exit:y
Enter name Shameer
Enter age 12
Enter National Insurance number 2468
Enter y to add another, any other key to exit:y
Enter name Omar
Enter age 38
Enter National Insurance number 1234
Enter y to add another, any other key to exit:y
Enter name Zainab
Enter age 1
Enter National Insurance number 0
Enter y to add another, any other key to exit:n
Zainab:1:0
Teymour:8:5319
Shameer:12:2468
Amna:33:1357
Omar:38:1234