Author : Mumit Khan
Page : << Previous 7 Next >>
list<int> list2(npoints);
list<int>::iterator iter = remove_copy_if(
list1, list1 + npoints, list2.begin(),
bind2nd(equal_to<int> (), 3)
);
copy(list2.begin(), iter, citer);
cout << "===" << endl;
//
// create a new sequence with all elements from list1, but 3's. Note
// that we use a front_insert_iterator in this case.
//
cout << endl << "===> Removing all but 3's" << endl;
list<int> list3;
front_insert_iterator<list<int> > out_iter(list3);
iter = remove_copy_if(
list1, list1 + npoints, out_iter,
not1 (bind2nd(equal_to<int> (), 3))
);
copy(list3.begin(), iter, citer);
cout << "===" << endl;
Data type adaptors
Stack, Queue, Priority Queue fall in this category; these adaptors allow you to use one of the existing container types that provide certain semantics, such as push_back, push_front methods or support specific type of iterator such as random_access_iterator, as Stacks and Queues. For example, you can use either a list or a deque as the underlying container for both stack and queue, but you cannot use a list for priority_queue because list does not support a random_access_iterator needed by priority_queue (use a deque or a vector instead).
Performance Note: When you have a choice between a list and a dequeu for some adaptor, I have found dequeu to give better, and in some cases, much better, performance.
Stack
Queue
Priority Queue
Stack
You can use any container that supports push_back and pop_back methods; eg, list, deque, and vector.
#include <stl.h>
#include <iostream.h>
int main () {
typedef stack<deque<int> > IntStack;
IntStack istack;
istack.push (31);
istack.push (87);
istack.push (13);
istack.push (29);
while (!istack.empty ()) {
cout << istack.top () << endl;
istack.pop ();
}
return 0;
}
And the output:
29
13
87
31
Queue
You can use any container that supports push_back and pop_front methods; eg, list and deque.
#include <stl.h>
#include <iostream.h>
int main () {
typedef queue<deque<int> > IntQueue;
IntQueue iqueue;
iqueue.push (31);
iqueue.push (87);
iqueue.push (13);
iqueue.push (29);
while (!iqueue.empty()) {
cout << iqueue.front() << endl;
iqueue.pop ();
}
return 0;
}
And the output:
31
87
13
29
Priority Queue
You can use any container that supports push_back and pop_back methods and supports a random access iterator; eg, vector and deque.
#include <stl.h>
#include <iostream.h>
int main () {
typedef priority_queue<deque<int>, less<int> > IntPQueue;
IntPQueue ipqueue;
ipqueue.push (31);
ipqueue.push (87);
ipqueue.push (13);
ipqueue.push (29);
while (!ipqueue.empty()) {
cout << ipqueue.top() << endl;
ipqueue.pop();
}
return 0;
}
And the output:
87
31
29
13
remove vs erase
When using algorithms such as remove to remove element from a sequential container, one must also erase the invalidated items from the container. remove does not change the size of the container. The following example shows what kind of surprise this can bring about.
#include <stl.h>
#include <iostream.h>
static bool even(int i) {
return i % 2 == 0;
}
int main(int, char*[]) {
list<int> list1;
for(int i = 0; i < 10; ++i) {
list1.push_back(i * i);
}
ostream_iterator<int> out(cout, " ");
cout << "==> Initial list (x(i) = i**2): [";
copy(list1.begin(), list1.end(), out);
cout << "]" << endl;
list<int>::iterator end = remove_if(list1.begin(), list1.end(), even);
cout << "==> After removing even numbers (Surprise!): [";
copy(list1.begin(), list1.end(), out);
cout << "]" << endl;
list1.erase(end, list1.end());
cout << "==> After erasing removed numbers: [";
copy(list1.begin(), list1.end(), out);
cout << "]" << endl;
return 0;
}
And here's the output:
==> Initial list (x(i) = i**2): [0 1 4 9 16 25 36 49 64 81 ]
==> After removing even numbers (Surprise!): [1 9 25 49 81 25 36 49 64 81 ]
==> After erasing removed numbers: [1 9 25 49 81 ]
List of List's in STL
There was a post in c.l.c++ inquiring how to iterate through the members of a list when the members are also lists. The following code snippet shows how (there is nothing special about a list of lists).
//
// Sample STL program to show how to iterate thru list of list's.
//
#include <stl.h>
#include <iostream.h>
//
// convenience typedefs to save typing.
//
typedef list<int> List;
typedef list<List> ListOfList;
void print_list(const List& list1, int id) {
ostream_iterator<int> out(cout, " ");
cout << "list " << id << ": ";
copy(list1.begin(), list1.end(), out);
cout << endl;
}
int main () {
ListOfList list_of_list1;
//
// create the list of list: total of 3 lists, each with 4 members.
//
for(int i = 0; i < 3; ++i) {
List list1;
for(int j = 0; j < 4; ++j) {
list1.push_back(i * 4 + j);
}
print_list(list1, i+1);
list_of_list1.push_back(list1);
}
cout << endl;
//
// now iterator thru list of lists.
//
ListOfList::iterator it = list_of_list1.begin();
for(int j = 1; it != list_of_list1.end(); ++it, ++j) {
const List& list1 = *it;
print_list(list1, j);
}
return 0;
}
And the output:
list 1: 0 1 2 3
list 2: 4 5 6 7
list 3: 8 9 10 11
list 1: 0 1 2 3
list 2: 4 5 6 7
list 3: 8 9 10 11
Sorting an STL container
STL provides a sort algorithm to sort any container that support random access iterators, such as vector and deque. For the containers that do not support random access iterators, such as list, STL containers typically have a sort member function that does the job. If you'd rather have a single sort algorithm that will do the job regardless of the iterator type, see here for an example.
There are 2 things to look out for:
For containers that support random-access iterators, use the STL sort algorithm which uses quicksort.
If your container objects are non-trivial, you should arm your container object with the appropriate constructors and comparison operators. See here for more info.
Sorting list of user-defined objects
#include <iostream.h>
#include <stdlib.h>
#include <stl.h>
#include <string.h>
inline char* strnew(const char* str) {
char* newstr = 0;
if (str) {
newstr = new char[strlen(str) + 1];
strcpy(newstr, str);
}
return newstr;
}
struct ListElem {
int id_;
char* name_;
ListElem() :
id_(0),
name_(strnew("unknown"))
{ }
ListElem(const ListElem& elem) :
id_(elem.id_),
name_(strnew(elem.name_))
{ }
ListElem(int id, const char* name) :
id_(id),
name_(strnew(name))
{ }
~ListElem() {
delete[] name_;
}
ListElem& operator= (const ListElem& elem) {
id_ = elem.id_;
delete[] name_;
name_ = strnew(elem.name_);
}
bool operator< (const
Page : << Previous 7 Next >>