|< C++ STL Container 4| Main| C++ STL Container 6>| Site Index| Download|

MODULE 28

THE C++ STL CONTAINER PART 5

list, set, multiset

What do we have in this STL C++ page?

Lists
list program example
<list> Header Members – operator & template class
list Template Class Members – typedef & member function
list constructors program example
list, insert() program example
list, remove() program example
list, sort() program example
list, splice() program example
list, unique() program example

My Training Period: xx hours

Program examples compiled usingVC++7.0/.Net, win32 empty console mode application. g++ program compilation examples given at the end of this Module. Source code is available inC++ STL Container source code.

The C++ STL container class programming abilities:

Able to understand and uselist sequence container.
Able to understand and useset associative container.
Able to understand and usemultiset associative container.

28.1 Lists

A list is implemented as a doubly linked list of elements. This means each element in a list has its own segment of memory and refers to its predecessor and its successor. Lists do not provide random access. It can be depicted as follow:

For example, to access the tenth element, you must navigate the first nine elements by following the chain of their links. However, a step to the next or previous element is possible in constant time.
Thus, the general access to an arbitrary element takes linear time (the average distance is proportional to the number of elements). This is a lot worse than the amortized constant time provided by vectors and deques.
The advantage of a list is that the insertion or removal of an element is fast at any position. Only the links must be changed. This implies that moving an element in the middle of a list is very fast compared with moving an element in a vector or a deque.
The list member functionsmerge(), reverse(),unique(), remove(), and remove_if() have been optimized for operation on list objects and offer a high-performance alternative to their generic counterparts.
List reallocation occurs when a member function must insert or erase elements of the list. In all such cases, only iterators or references that point at erased portions of the controlled sequence become invalid.
The following general list example creates an empty list of characters, inserts all characters from 'a' to 'z', and prints all elements by using a loop that actually prints and removes the first element of the collection:

// list example

#include <iostream>

#include <list>

using namespace std;

int main()

{

// list container for character elements

list<char> elem;

// append elements from 'a' to 'z'

for(char chs='a'; chs<= 'z'; ++chs)

elem.push_back(chs);

// while there are elements, print and remove the element

while(!elem.empty())

{

cout<<elem.front()<<' ';

elem.pop_front();

}

cout<<endl;

return 0;

}

Output:

C++ STL Container list very simple general program example

With STL, using loop to print the outputs and removes the element is not a proper way. Normally, we would iterate over all elements using iterator. Using loop in the program example just for discussion.
However, direct element access by using operator[ ] is not provided for lists. This is because lists don't provide random access, and thus using operator[ ] would cause bad performance. There is another way to loop over the elements and print them by using iterators.

28.2 <list> Header Members

Operators

Operator	Description
operator!=	Tests if the list object on the left side of the operator is not equal to the list object on the right side.
operator<	Tests if the list object on the left side of the operator is less than the list object on the right side.
operator<=	Tests if the list object on the left side of the operator is less than or equal to the list object on the right side.
operator==	Tests if the list object on the left side of the operator is equal to the list object on the right side.
operator>	Tests if the list object on the left side of the operator is greater than the list object on the right side.
operator>=	Tests if the list object on the left side of the operator is greater than or equal to the list object on the right side.
Table 28.1

list Template Class

Class

Description

list

A template class of sequence containers that maintain their elements in a linear arrangement and allow efficient insertions and deletions at any location within the sequence.

table 28.2

The STL list class is a template class of sequence containers that maintain their elements in a linear arrangement and allow efficient insertions and deletions at any location within the sequence.
The sequence is stored as a bidirectional linked list of elements, each containing a member of some type Type.

list Template Class Members

Typedefs

Typedef	Description
allocator_type	A type that represents the allocator class for a list object.
const_iterator	A type that provides a bidirectional iterator that can read a const element in a list.
const_pointer	A type that provides a pointer to aconst element in a list.
const_reference	A type that provides a reference to a const element stored in a list for reading and performing const operations.
const_reverse_iterator	A type that provides a bidirectional iterator that can read any const element in a list.
difference_type	A type that provides the difference between two iterators those refer to elements within the same list.
iterator	A type that provides a bidirectional iterator that can read or modify any element in a list.
pointer	A type that provides a pointer to an element in a list.
reference	A type that provides a reference to a const element stored in a list for reading and performing const operations.
reverse_iterator	A type that provides a bidirectional iterator that can read or modify an element in a reversed list.
size_type	A type that counts the number of elements in a list.
value_type	A type that represents the data type stored in a list.
Table 28.3

list Template Class Member Functions

Member function	Description
assign()	Erases elements from a list and copies a new set of elements to the target list.
back()	Returns a reference to the last element of a list.
begin()	Returns an iterator addressing the first element in a list.
clear()	Erases all the elements of a list.
empty()	Tests if a list is empty.
end()	Returns an iterator that addresses the location succeeding the last element in a list.
erase()	Removes an element or a range of elements in a list from specified positions.
front()	Returns a reference to the first element in a list.
get_allocator()	Returns a copy of the allocator object used to construct a list.
insert()	Inserts an element or a number of elements or a range of elements into a list at a specified position.
list()	list constructor, constructs a list of a specific size or with elements of a specific value or with a specific allocator or as a copy of some other list.
max_size()	Returns the maximum length of a list.
merge()	Removes the elements from the argument list, inserts them into the target list, and orders the new, combined set of elements in ascending order or in some other specified order.
pop_back()	Deletes the element at the end of a list.
pop_front()	Deletes the element at the beginning of a list.
push_back()	Adds an element to the end of a list.
push_front()	Adds an element to the beginning of a list.
rbegin()	Returns an iterator addressing the first element in a reversed list.
remove()	Erases elements in a list that match a specified value.
remove_if()	Erases elements from the list for which a specified predicate is satisfied.
rend()	Returns an iterator that addresses the location succeeding the last element in a reversed list.
resize()	Specifies a new size for a list.
reverse()	Reverses the order in which the elements occur in a list.
size()	Specifies a new size for a list.
sort()	Arranges the elements of a list in ascending order or with respect to some other order relation.
splice()	Removes elements from the argument list and inserts them into the target list.
swap()	Exchanges the elements of two lists.
unique()	Removes adjacent duplicate elements or adjacent elements that satisfy some other binary predicate from the list.
Table 28.4

list constructor, constructs a list of a specific size or with elements of a specific value or with a specific allocator or as a copy of all or part of some other list.
All constructors store an allocator object and initialize the list.
get_allocator() returns a copy of the allocator object used to construct a list.
None of the constructors perform any interim reallocations.

// list constructors

#include <list>

#include <iostream>

using namespace std;

int main()

{

list <int>::iterator li0Iter, li1Iter, li2Iter, li3Iter, li4Iter, li5Iter, li6Iter;

// create an empty list li0

list <int> li0;

// create a list li1 with 10 elements of default value 0

list <int> li1(10);

// create a list li2 with 8 elements of value 7

list <int> li2(8, 7);

// create a list li3 with 9 elements of value 8 and with the allocator of list li2

list <int> li3(9, 8, li2.get_allocator());

// li4, a copy of list li2

list <int> li4(li2);

// create a list li5 by copying the range of li4[_First, _Last)

li4Iter = li4.begin();

li4Iter++;

list <int> li5(li4.begin(), li4Iter);

// create a list li6 by copying the range of li4[_First, _Last) and with the allocator of list li2

li4Iter = li4.begin();

li4Iter++;

list <int> li6(li4.begin(), li4Iter, li2.get_allocator());

// ----------------------------------------------------

cout<<"Operation: list <int> li0\n";

cout<<"li0 data: ";

for(li0Iter = li0.begin(); li0Iter != li0.end(); li0Iter++)

cout<<" "<<*li0Iter;

cout<<endl;

cout<<"\nOperation: list <int> li1(10)\n";

cout<<"li1 data: ";

for(li1Iter = li1.begin(); li1Iter != li1.end(); li1Iter++)

cout<<" "<<*li1Iter;

cout<<endl;

cout<<"\nOperation: list <int> li2(8, 7)\n";

cout<<"li2 data: ";

for(li2Iter = li2.begin(); li2Iter != li2.end(); li2Iter++)

cout<<" "<<*li2Iter;

cout<<endl;

cout<<"\nOperation: list <int> li3(9, 8, li2.get_allocator())\n";

cout<<"li3 data: ";

for(li3Iter = li3.begin(); li3Iter != li3.end(); li3Iter++)

cout<<" "<<*li3Iter;

cout<<endl;

cout<<"\nOperation: list <int> li4(li2);\n";

cout<<"li4 data: ";

for(li4Iter = li4.begin(); li4Iter != li4.end(); li4Iter++)

cout<<" "<<*li4Iter;

cout<<endl;

cout<<"\nOperation1: li4Iter = li4.begin(), li4Iter++...\n";

cout<<"Operation2: list <int> li5(li4.begin(), li4Iter)\n";

cout<<"li5 data: ";

for(li5Iter = li5.begin(); li5Iter != li5.end(); li5Iter++)

cout<<" "<<*li5Iter;

cout<<endl;

cout<<"\nOperation1: li4Iter = li4.begin(), li4Iter++...\n";

cout<<"Operation2: list <int> li6(li4.begin(), li4Iter,\n"

" li2.get_allocator())\n";

cout<<"li6 data: ";

for(li6Iter = li6.begin(); li6Iter != li6.end(); li6Iter++)

cout<<" "<<*li6Iter;

cout<<endl;

return 0;

}

Output:

The return value is the first insert() function returns an iterator that point to the position where the new element was inserted into the list.
Any insertion operation can be expensive in term of time and resource.

// list, insert()

#include <list>

#include <iostream>

using namespace std;

int main()

{

list <int> lis1, lis2;

list <int>::iterator Iter;

lis1.push_back(13);

lis1.push_back(22);

lis1.push_back(15);

lis2.push_back(9);

lis2.push_back(5);

lis2.push_back(45);

cout<<"lis1 data: ";

for(Iter = lis1.begin(); Iter != lis1.end(); Iter++)

cout<<" "<<*Iter;

cout<<endl;

cout<<"lis2 data: ";

for(Iter = lis2.begin(); Iter != lis2.end(); Iter++)

cout<<" "<<*Iter;

cout<<endl;

cout<<"\nOperation1: lis1.begin() then Iter++...\n";

cout<<"Operation2: lis1.insert(Iter, 55)\n";

Iter = lis1.begin();

Iter++;

lis1.insert(Iter, 55);

cout<<"lis1 data: ";

for(Iter = lis1.begin(); Iter != lis1.end(); Iter++)

cout<<" "<<*Iter;

cout<<endl;

cout<<"\nOperation1: lis1.begin() then Iter++...\n";

cout<<"Operation2: lis1.insert(Iter, 3, 30)\n";

Iter = lis1.begin();

Iter++;

lis1.insert(Iter, 3, 30);

cout<<"lis1 data: ";

for(Iter = lis1.begin(); Iter != lis1.end(); Iter++)

cout<<" "<<*Iter;

cout<<endl;

cout<<"\nOperation2: lis1.insert(++lis1.begin(),\n"

" lis2.begin(),--lis2.end())\n";

lis1.insert(++lis1.begin(), lis2.begin(),--lis2.end());

cout<<"lis1 data: ";

for(Iter = lis1.begin(); Iter != lis1.end(); Iter++)

cout<<" "<<*Iter;

cout<<endl;

return 0;

}

Output:

C++ STL Container list insert()

The order of the elements remaining is not affected.

// list, remove()

#include <list>

#include <iostream>

using namespace std;

int main( )

{

list <int> lis1;

list <int>::iterator lis1Iter, lis2Iter;

lis1.push_back(7);

lis1.push_back(12);

lis1.push_back(25);

lis1.push_back(7);

lis1.push_back(9);

lis1.push_back(7);

lis1.push_back(21);

cout<<"The initial lis1 data is: ";

for(lis1Iter = lis1.begin(); lis1Iter != lis1.end(); lis1Iter++)

cout<<" "<<*lis1Iter;

cout<<endl;

cout<<"\nOperation1: list <int> lis2 = lis1\n";

cout<<"Operation2: lis2.remove(7)\n";

list <int> lis2 = lis1;

lis2.remove(7);

cout<<"Removing elements of value 7, \nthe list data, lis2 is: ";

for(lis2Iter = lis2.begin(); lis2Iter != lis2.end(); lis2Iter++)

cout<<" "<<*lis2Iter;

cout<<endl;

return 0;

}

Output:

C++ STL Container list remove()

The first member function puts the elements in ascending order by default.
The member template function orders the elements according to the user-specified comparison operation _Comp of classTraits.

// list, sort()

#include <list>

#include <iostream>

using namespace std;

int main()

{

list <int> ls1;

list <int>::iterator ls1Iter;

ls1.push_back(31);

ls1.push_back(12);

ls1.push_back(40);

ls1.push_back(15);

ls1.push_back(9);

ls1.push_back(44);

cout<<"Before sorting, ls1 data: ";

for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

cout<<" "<<*ls1Iter;

cout<<endl;

cout<<"\nOperation: ls1.sort()\n";

ls1.sort();

cout<<"After sorting, ls1 data: ";

for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

cout<<" "<<*ls1Iter;

cout<<endl;

cout<<"\nOperation: ls1.sort(greater<int>())\n";

ls1.sort(greater<int>());

cout<<"Re sort with 'greater than' operation,\nls1 =";

for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

cout<<" "<<*ls1Iter;

cout<<endl;

return 0;

}

Output:

C++ STL Container list sort()

// list, splice()

#include <list>

#include <iostream>

using namespace std;

int main( )

{

list <int> ls1, ls2, ls3, ls4;

list <int>::iterator ls1Iter, ls2Iter, ls3Iter, ls4Iter, PIter, QIter, RIter;

ls1.push_back(7);

ls1.push_back(15);

ls2.push_back(9);

ls2.push_back(22);

ls2.push_back(12);

ls3.push_back(29);

ls3.push_back(30);

ls4.push_back(33);

ls4.push_back(25);

ls4.push_back(51);

cout<<"ls1 data: ";

for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

cout<<" "<<*ls1Iter;

cout<<endl;

cout<<"ls2 data: ";

for(ls2Iter = ls2.begin(); ls2Iter != ls2.end(); ls2Iter++)

cout<<" "<<*ls2Iter;

cout<<endl;

cout<<"ls3 data: ";

for(ls3Iter = ls3.begin(); ls3Iter != ls3.end(); ls3Iter++)

cout<<" "<<*ls3Iter;

cout<<endl;

cout<<"ls4 data: ";

for(ls4Iter = ls4.begin(); ls4Iter != ls4.end(); ls4Iter++)

cout<<" "<<*ls4Iter;

cout<<endl;

cout<<"\nOperation: ls2.splice(PIter, ls1)\n";

PIter = ls2.begin();

PIter++;

ls2.splice(PIter, ls1);

cout<<"ls2 data, after splicing \nls1 into ls2: ";

for(ls2Iter = ls2.begin(); ls2Iter != ls2.end(); ls2Iter++)

cout<<" "<<*ls2Iter;

cout<<endl;

cout<<"\nOperation: ls2.splice(PIter, ls3, QIter)\n";

QIter = ls3.begin();

ls2.splice(PIter, ls3, QIter);

cout<<"ls2 data, after splicing the first \nelement of ls3 into ls2: ";

for(ls2Iter = ls2.begin(); ls2Iter != ls2.end(); ls2Iter++)

cout<<" "<<*ls2Iter;

cout<<endl;

cout<<"\nOperation: ls2.splice(PIter, ls4, QIter, RIter)\n";

QIter = ls4.begin();

RIter = ls4.end();

RIter--;

ls2.splice(PIter, ls4, QIter, RIter);

cout<<"ls2 data, after splicing a range \nof ls4 into ls2: ";

for(ls2Iter = ls2.begin(); ls2Iter != ls2.end(); ls2Iter++)

cout<<" "<<*ls2Iter;

cout<<endl;

return 0;

}

Output:

C++ STL Container list splice()

This function assumes that the list is sorted, so that all duplicate elements are adjacent. Duplicates that are not adjacent will not be deleted.
The first member function removes every element that compares equal to its preceding element.
The second member function removes every element that satisfies the predicate function when compared with its preceding element.

// list, unique()

#include <list>

#include <iostream>

using namespace std;

int main()

{

list <int> ls1;

list <int>::iterator ls1Iter, ls2Iter, ls3Iter;

not_equal_to<int> mypred;

ls1.push_back(-12);

ls1.push_back(12);

ls1.push_back(22);

ls1.push_back(13);

ls1.push_back(-12);

ls1.push_back(14);

cout<<"ls1 data, the initial list:\n";

for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

cout<<" "<<*ls1Iter;

cout<<endl;

cout<<"\nOperation1: list <int> ls2 = ls1\n";

cout<<"Operation2: ls2.unique()\n";

list <int> ls2 = ls1;

ls2.unique();

cout<<"ls2 data, after removing successive duplicate\nelements: ";

for(ls2Iter = ls2.begin(); ls2Iter != ls2.end(); ls2Iter++)

cout<<" "<<*ls2Iter;

cout<<endl;

cout<<"\nOperation1: list <int> ls3 = ls2\n";

cout<<"Operation2: ls3.unique(mypred)\n";

list <int> ls3 = ls2;

ls3.unique(mypred);

cout<<"ls3 data, after removing successive unequal\nelements: ";

for(ls3Iter = ls3.begin(); ls3Iter != ls3.end(); ls3Iter++)

cout<<" "<<*ls3Iter;

cout<<endl;

return 0;

}

Output:

C++ STL Container list unique()

---------------------------------------------------End of list---------------------------------------------

tenouk C++ STL List programming tutorial

Further C++ container related reading:

Source code is available inC++ STL Container source code.
Check thebest selling C / C++ books at Amazon.com.
Acomplete C Standard Library.
Acomplete C++ Standard Library documentation that includes STL.

|< C++ STL Container 4| Main| C++ STL Container 6>| Site Index| Download|

|< C++ STL Container 4| Main| C++ STL Container 6>| Site Index| Download|

MODULE 28

THE C++ STL CONTAINER PART 5

list, set, multiset

What do we have in this STL C++ page?

Lists

list program example

<list> Header Members – operator & template class

list Template Class Members – typedef & member function

list constructors program example

list, insert() program example

list, remove() program example

list, sort() program example

list, splice() program example

list, unique() program example

My Training Period: xx hours

The C++ STL container class programming abilities:

Able to understand and uselist sequence container.

Able to understand and useset associative container.

Able to understand and usemultiset associative container.

28.1 Lists

Output:

28.2 <list> Header Members

Operators

list Template Class

list Template Class Members

Typedefs

list Template Class Member Functions

Output:

Output:

Output:

Output:

Output:

Further C++ container related reading:

|< C++ STL Container 4| Main| C++ STL Container 6>| Site Index| Download|

C++ STL Container Classes: Part 1 | Part 2 |Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 | Part 9 | Part 10 | Part 11