|< 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?

 

  1. Lists

  2. list program example

  3. <list> Header Members – operator & template class

  4. list Template Class Members – typedef & member function

  5. list constructors program example

  6. list, insert() program example

  7. list, remove() program example

  8. list, sort() program example

  9. list, splice() program example

  10. list, unique() program example

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

My Training Period: xx hours

 

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

 

The C++ STL container class programming abilities:

 

  • Able to understand and use list sequence container.

  • Able to understand and use set associative container.

  • Able to understand and use multiset 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:

 

C++ STL Container list

 

  • 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 functions merge(), 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

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

 

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 a const 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 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++;

    li4Iter++;

    li4Iter++;

    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++;

    li4Iter++;

    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:

C++ STL Container list constructor  

// 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++;

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

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

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

// 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(12);

    ls1.push_back(22);

    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:

 

  1. Source code is available in C++ STL Container source code.

  2. Check the best selling C / C++ books at Amazon.com.

  3. A complete C & C++ Standard Library documentation that includes STL.

 

 

 

 

 

 

|< 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