|
The
List container class is comprised of a linked list type data
structure. The objects in the list class can not be
accessed directly, they follow the usual indirect access method
that we find via pointers and references in typical
linked
lists. The List class is defined as a template, so it can
hold object of any data type. List containers are
designed for optimal efficiency when inserting and deleting
objects frequently. The List class has al the member
functions of the vector class. Linked lists are
implemented with pointers, but STL List containers are
implemented
with iterators. An iterator is a
generalization of a pointer. When you dereference an
iterator, you can retrieve the
node it points to. Examples:
#include <iostream>
#include <vector> // vector class library
#include <list> // list class library
#include <algorithm> // STL algorithms class library
using namespace std;void main() { list<int> IntList;
//Remember that iterators function like pointers, so this is like declaring a pointer
list<int>::iterator NumberIterator; IntList.push_back(100);
IntList.push_back(200);
IntList.push_front(300); NumberIterator = find(IntList.begin(), IntList.end(), 300); //Search the list. if(NumberIterator != IntList.end())
{
//Notice that NumberIterator gets dereferenced like a pointer
cout << "Number " << (*NumberIterator) << " found." << endl; // 3
}
else
{
cout << "Number not found." << endl;
} //If we found the element, erase it from the list.
if(NumberIterator != IntList.end())
IntList.erase(NumberIterator); //The List now contains: 10 7
} //close main | | Output: Number 300 found. |
#include <iostream>
#include <list>
using namespace std; typedef list<int> IntegerList; int main()
{
IntegerList ListOfInts; for(int i = 1; i <= 10; ++i)
ListOfInts.push_back(i * 10);
//Remember that declaring an iterator is like declaring a pointer
IntegerList::const_iterator ConstIter; for(ConstIter = ListOfInts.begin(); ConstIter != ListOfInts.end(); ++ConstIter)
//Again, notice that we dereference the iterator as we would a pointer
cout << *ConstIter << " "; return 0;
} |
| Output: 10 20 30 40 50 60 70 80 90 100 |
#include <iostream>
#include <list> // list class library
using namespace std;
void main() {
//The "list" class does not have the same "random access" capability as the "vector" class,
//but it is possible to add elements at the end of the list and take them off the front.
list<int> ListOfIntegers;
//Add some values at the end of the list, which is initially empty.
//The member function "push_back" adds an item to the end of the list.
int value = 0;
int value1 = 500;
int value2 = 700;
ListOfIntegers.push_back(value1);
ListOfIntegers.push_back(value2);
ListOfIntegers.push_back(600);
ListOfIntegers.push_back(650);
//Output the list values, by repeatedly getting the item from the "front" of the list, outputting it,
//and then removing it from the front of the list.
cout << endl << "List values:" << endl;
//Loop as long as there are still elements in the list.
while(ListOfIntegers.size() > 0)
{
//Get the value of the "front" list item.
value = ListOfIntegers.front();
cout << value << endl;
//Remove the item from the front of the list using the "pop_front" member function.
ListOfIntegers.pop_front();
}
} //close main() | Output:
List values:
500
700
600
650 |
Some useful member functions of the List class are:
size() - returns the
number of elements currently stored in the List:
// Loop as long as there are still elements in the list.
while
(ListName.size() > 0)
{
//...
} |
empty() - returns true
if the number of elements in the List is 0.
if(list1.empty())
{
//...
} |
push_back - adds the
element passed in (x) to the end of the List.
push_front - adds the element passed in (x) to the
beginning of the List.
list<int> nums;
nums.push_back(10);
nums.push_back(20);
nums.push_front(30); |
front() - obtains a
reference to the first element in the List.
back() - obtains a reference to the last element in the
List.
list<int> nums;
nums.push_back(33);
nums.push_back(44);
cout << nums.front() << endl;
cout << nums.back() << endl; |
begin() - returns an
iterator referencing the beginning of the List.
end() - returns an iterator referencing the position just
past the last element in the List.
iterator begin();
iterator end(); |
insert() - inserts an
element into the last at the position specified by the parameter
passed in.
IntegerList::const_iterator nums_iter;
nums_iter = find(nums.begin(), nums.end(), 15);
if(nums_iter != nums.end())
{
nums_iter = nums.insert(nums_iter, -22);
cout << "Inserted element " << (*nums_iter) << endl;
} |
erase() - erases one
specified element or a range of elements from a List.
IntegerList::const_iterator nums_iter;
nums.erase(nums.begin(), nums.end()); // Remove all elements
nums_iter = find(nums.begin(), nums.end(), 3); // Search the list.
//If we found the element, erase it from the list.
if(nums_iter != nums.end())
nums.erase(nums_iter); |
clear() - erases all
elements from a List.
pop_front() - erases
the first element from a List.
pop_back() - erases the last element from a List.
while(list1.size() > 0)
{
list1.pop_front();
} |
remove() - erases all
List elements equal to the value passed in.
sort() - sorts the
List in ascending order.
reverse() - reverses
the order of elements in the List.
Overloaded = operator
- replaces the target list's contents with that of the source
list:
list<int> IntegerList1;
list<int> IntegerList2;
IntegerList1.push_back(1000);
IntegerList2.push_back(2000);
IntegerList2.push_back(3000);
IntegerList1 = IntegerList2;
// The list b now contains two elements: 2000, 3000 |
Overloaded == operator - tests whether two lists have the
same content (element-by-element
comparison for all elements). Lists are
traversed through the employment of iterators. A simple example of iterator use is traversing a
list to print out its elements. Below, the function,
"OutputListOfInts" writes the elements of a list
to an output stream and appends a specified
delimiter string (here, just a newline character)
after each element. The list is passed by constant reference, instead
of by value, so that it does not have to be copied
(along with all its elements). However, it is still safe
from modification since it is constant. A
const iterator
(necessary because the argument is
const)
is used to traverse the list - each element is
written to the specified stream.
#include <iostream>
#include <string>
#include <list>
using namespace std;
void OutputListOfInts(const list<int>& ListObject, ostream & OutObject, const string & delim);
//---------------------------------------------------------------------------------------------------------------------
void main() {
list<int> nums;
nums.push_back(10);
nums.push_back(20);
nums.push_front(30);
cout << endl << "List 'nums' now is:" << endl;
//Function call
OutputListOfInts(nums, cout, "\n");
cout << endl;
} // close main()
//---------------------------------------------------------------------------------------------------------------------
//Function definition
void OutputListOfInts(const list<int>& ListObject, ostream & OutObject, const string & delim)
{
//Create constant iterator for list.
list<int>::const_iterator iter;
//Iterate through the list and output each element.
for(iter=ListObject.begin(); iter != ListObject.end(); iter++)
{
//Again, notice that the iterator is dereferenced
OutObject << (*iter) << delim;
}
} //close function |
Output:
List 'nums' now is:
30
10
20 |
Just as the iterator's
increment operator can be used to move forward in a list,
the decrement operator may be used to "back up." Here, we
search for the first occurrence of a certain element value,
and then print the previous and following elements, if they
exist. Note that we can copy the value of an iterator to
"mark" a list position and that more than one iterator can
be associated with a single container:
#include <iostream>
#include <list> //list class library
#include <algorithm> //STL algorithms class library
using namespace std;
void main() {
list<int> nums;
list<int>::iterator nums_iter;
list<int>::iterator prev_iter;
list<int>::iterator next_iter;
nums.push_back(6);
nums.push_back(7);
nums.push_front(5);
// Search the list.
nums_iter = find(nums.begin(), nums.end(), 6);
if(nums_iter != nums.end())
{
cout << "Number " << (*nums_iter) << " found." << endl;
//If found element is not first, print out previous.
if(nums_iter != nums.begin())
{
//Copy "found" iterator, and back up one position.
prev_iter = nums_iter;
//Prefix decrement and dereference the previous iterator to get the value, not the address
cout << "Previous element is " << (*(--prev_iter)) << endl;
}
//Copy "found" iterator position, and move forward one position.
next_iter = nums_iter;
//Increment iterator without dereferencing to move pointer to next object memory address w/o fetching value
next_iter++;
//If we didn't fall off the end, print out next element.
if(next_iter != nums.end())
{
cout << "Following element is " << (*next_iter) << endl;
}
} //close 1st if
else
{
cout << "Sorry, number not found." << endl;
}
} //close main() |
Output:
Number 6 found.
Previous element is 5
Following element is 7 |
Iterator values may become invalid if the content
of the associated container changes. For example, an
iterator may specify the position of an element that
is subsequently erased; in this case, the iterator
value is no longer valid.
©2004 C. Germany
|
Contact
