Please refer Lesson 8..
9. STANDARD TEMPLATE LIBRARY (STL)
9.1 Introduction to Container
9.2 Iterator
9.3 Iterator Types
9.4 Iterator Capabilities
9.5 Iterator Capabilities Supported by Different Containers
9.6 IO Iterators
9.7 Operations Supported by Different Iterators
9.8 Sequence Containers
9.9 vector
9.10 Binary Predicate Function
9.11 List
9.12 Deque
9.13 Comparison of vector, list and deque
9.14 Associative Containers
9.15 Class pair
9.16 multiset
9.17 set
9.18 multimap
9.19 map
9.20 Container Adapters
9.21 Stack
9.22 queue
9.23 priority_queue
9.24 Introduction to Algorithms
9.25 Fill Container with Objects
9.26 Compare Elements
9.27 Remove Elements
9.28 Replace Elements
9.29 Mathematical Algorithms
9.30 Searching and Sorting Elements
9.31 Swap Elements
9.32 Copy Elements
9.33 Merge Containers
9.34 Unify Elements
9.35 Reverse Elements
9.36 Locate Element in Sorted Container
9.37 Heapsort
9.38 min & max
9. STANDARD TEMPLATE LIBRARY (STL)
9.1 Introduction to Container
Containers are objects that contains objects. In STL, containers only encapsulates some primitive operations. The algorithms are independent of the containers. They manipulate containers using iterators.
=>Containers Categories
Sequence Containers: organize a collection of objects into a strictly linear arrangement. There are four types of sequence containers: normally arrays, vectors, lists and deques.
Sorted Associative Containers: a collection which is kept sorted with keys. There are four kinds of associative containers: sets, multisets, maps and multimaps.
Adapters: inherit from the two first-class containers and modify their interfaces. There are three major types: stack, queue, priority_queue
=>Common methods of all containers
default constructor, copy constructor, destructor;
operator =, <, <=, >, >=, ==, !=;
empty: return true if container has no element
max_size: maximum number of elements for a container
size: number of elements currently in the container
swap: swaps the elements
=>Common methods of all containers
begin: returns an iterator or const_iterator to the first element of the container
end: returns an iterator or const_iterator to the next position after the end of the container
rbegin: returns an reverse_iterator or const_reverse_iterator to the last element of the container.
rend: returns an reverse_iterator or const_reverse_iterator to the position before the first element of the container
erase: erases one or more elements from the container
clear: erases all elements from the container
=>Type of Container Element
Container element can be of any type, both built-in types or user-defined types. However, user-defined types which is to be stored in containers must support a minimum set of methods. When an element is inserted into a container, a copy of the element is made. If default memberwise copy can not do the job, then the type must provide its own copy constructor and assignment operator. Also, associative containers and many algorithms require elements to be compared. So the element type should provide overloaded operator = = and <.
9.2 Iterator
Iterators are sophisticated pointers pointing to container elements. Except for vectors which can manipulate its elements through integer subscripts (such as v[1], v[2]), all container methods and STL algorithms manipulate container elements through iterators.
There are two kinds of container methods: methods which return iterators and methods which modifies the elements.
Iterator-returning methods return iterators pointing to some special elements such as the first or the last element, or an element which conforms to a certain rule (e.g., the one pointing to an element which is equal to the passed object). With these returned iterators, container’s element modifying methods and STL algorithms can then modify the elements through them.
Element-modifying methods have quite limited functionality - much of the job is done through independent STL algorithms, which are more abstracted from containers.
Iterators are designed to act as a medium to separate “how” from “what”: new STL algorithms and client applications are supposed to be developed with only iterators, without knowing the type of the container and the type of its elements. Java achieved this goal. All containers hold only one type: class Object, and all containers use one type of iterator.
However, C++ did not achieve such a complete abstraction. When you create an iterator, you have to specify the type of container it belongs to - a vector, a map, a multiset, etc., and the type of the container element - integer, string, or other user-defined types.
We can not create an iterator pointing to a certain element in a container. We can only ask a container to return an interator pointing to a certain element.
Normal arrays are random access containers, pointer to arrays i.e. array names are random access iterators.
9.3 Iterator Types
iterator: refer to objects which can be modified
const_iterator: refer to objects which can not be modified
reverse_iterator
const_reverse_iterator
To create an iterator, Three kinds of information need to be provided: container type, element type and iterator type. It is not abstracted enough.
vector::reverse_iterator p1;
9.4 Iterator Capabilities
Input iterator: used to read an element from a container. It can only move in the forward direction one element at a time, and only support one-pass algorithms.
Output iterator: used to write an element to a container. It can only move in the forward direction one element at a time, and only support one-pass algorithms.
Forward iterator: combines the capabilities of the input and output iterator, and retains their position in the container as state information.
bidirectional iterator: add the ability to move in both backward and forward directions.
Random access iterator: add the ability to directly access any element - such as a pointer to an array.
The capability of an iterator is is decided by the container to which it belongs. Different kinds of containers provide iterators of different capabilities.
9.5 Iterator Capabilities Supported by Different Containers
vector: random access
list: bidirectional
deque: random access
set: bidirectional
multiset: bidirectional
map: bidirectional
multimap: bidirectional
stack: no iterator supported
queue: no iterator supported
priority_queue: no iterator supported
Different types of STL algorithms requires iterators of different capabilities.
9.6 IO Iterators
There are other two types of iterators which do not belong to any container: istream_iterator and ostream_iterator. They are used to input and output a certain type of object in a type-safe manner from/to an IO object such as cin and cout.
9.7 Operations Supported by Different Iterators
All iterators:
++p
p++
Input iterators:
*p
p1 = p2
p1 == p2
p1 != p2
Output iterators:
*p
p1 = p2
Forward iterators:
provide all the methodality of both input and output iterators.
Bidirectional iterators:
- - p
p - -
Random access iterators
p + i
p - i
p += i
p -= i
p[i]
p1 < p2
p1 <= p2
p1 > p2
p1 >= p2
9.8 Sequence Containers
Sequence containers include vector, list and deque. vector stores elements contiguously in memory, list is linked with double pointers, and deque combines the advantages of vector and deque.
They have some common methods:
front: return an iterator to the first element in the container
back: return an iterator to the last element in the container
push_back: insert a new element at the end of the container
pop_back: remove the last element of the container
insert: insert one or a range of elements into the container - before the indicated location.
9.9 vector
vector is the most commonly used container in STL.
Class vector provides a data structure with contiguous memory locations. This enables efficient, direct access to any element via subscript operator [ ] like arrays. So a vector is a more intelligent and complex array.
A vector returns random access iterators.
Because only random access iterators support “<" operator. So it is always safer to use "!=" operator, which is supported by all iterators except for output iterators.
Header file of vectors is .
=>Element insertion and deletion
Because vector elements occupies contiguous memory, it is OK to insert or delete new element at the back, but expensive at the front or middle, for the entire portion of the vector after the inserted or deleted element have to be moved to keep it contiguous.
Suppose you have a vector of 9 elements, now you delete the 5th. The vector will call element’s assignment operator to assign the 6th element to the 5th, the 7th to 6th, … , finally the 9th to the 8th. Then it will delete the last element. So you can see, to keep a contiguous memory a great deal of work needs to be done if you delete or add from the middle. In contrast, for a linked list, all you need to do is to point the pointer in the 4th element to the 6th. Therefore, if you need to frequently insert and delete from the middle, use a linked list.
When an element is inserted, the compiler will first call copy constructor to create a new element at the end, and use assignment operator to assign the second last to the last, and so on, and finally assign the object which is to be inserted to the original object which is at the insertion point.
vector’s elements can be accessed with subscription just like arrays. Operator [ ] does not perform range check, but method at does.
If a new element is added to a full vector, the vector increases its size automatically - some would double its size, so would increase a certain amount.
=>Two more methods of its own
vector has two more methods of its own:
capacity: vector’s capacity is not always its number of elements. When a full vector receives a new element, it may double its size. So if a vector has 4 elements and one is added, it will have a size of 5 and capacity of 8.
resize: if you think the doubled capacity consumes too much memory, you can use it to resize the vector.
=>Sample codes and explanations:
const int SIZE = 6;
int a[SIZE] = {1,2,3,4,5,6};
vector<int> v1; // create an empty vector
vector<int> v2(a, a + size); // create a vector using part of an array
v1.push_back(11); // insert an element at the back of the vector
v1.push_back(22);
vector<int>::iterator p1; // create an iterator
// traverse a vector with iterator:
for(p1 = v1.begin(); p1 != v1.end(); p1++)
cout << *p1;
vector<int>::reverse_iterator p2; // create a reverse_iterator
// traverse a vector with reverse_iterator
for(p2 = v2.rbegin(); p2 != v2.rend(); p2++)
cout << *p2;
cout << v2.size(); // size of vector
cout << v2.capacity(); // capacity of vector
v1[0] = 7; // set first element to 7 - no range checking
v1.at(2) = 7; // set third element to 7 - with range checking
If the argument at receives is out of range, it will throw a “out_of_range” exception, which is in .
v1.insert(v1.begin()+3, 22); // insert 22 as 4th element
v2.insert(v1.begin()+3, v2.begin(),v2.begin()+5);
This is to insert the first 6 elements of vector v2 into the vector v1, to start as from the 4th element of vector.
istream_iterator<int> input(cin);
int a, b;
a = *input;
++ input;
b = *input;
This is to declare an istream_iterator to input integers from cin.
ostream_iterator<int> output(cout, " ");
*output = a + b;
This is to declare an ostream_iterator to output integers to cout. Each outputted value is to be separated by a space character specified as the second argument.
v1.erase(v1.begin()+3); // remove the 4th element from vector
v1.erase(v1.begin(), v1.end()); // remove a range of elements from vector
v1.clear(); // remove all elements from vector
9.10 Binary Predicate Function
A function supplied as an argument to other functions such as container methods and STL algorithms, which takes two arguments, performs a comparison, and returns a bool value indicating the result. The algorithms only call the passed function to perform the comparison, but how to implement the comparison is customized with this function. This technique is also called “call back”, which is an effort to separate “what to do” from “how to do”.
template < class T >
bool myCompare(T a, T b)
{ return a < b; }
9.11 List
Class list is implemented as a doubly-linked list, so it can not be randomly accessed, and it only supports bidirectional iterators. As said before, because the list elements are not stored contiguous and only connected one by one through doubly links, it is convenient to insert or delete an element at any location of the list.
Header file of lists is
.
=>Methods
splice: remove elements from a list and insert into another
push_front: insert an element at the front
pop_front: remove an element at the front
remove
unique
merge
reverse
sort
=>Sample program
list<int> l1, l2; // create an empty list
l1.sort();
Method “sort” sorts the elements in the list in ascending order by calling element’s operator “<". If the element type does not provide a "<" operator, or you want to compare two elements in a different way, or the list elements are pointers to other objects, you will need to provide a comparing method yourself. The second version of "sort" allows the programmer to supply a binary predicate function.
This is to remove all the elements of l2 and insert them into l1 before the iterator position, which is the end.
l1.splice(l1.end(), l2, l2.begin() + 1);
This is to remove the l2’s second element, and insert it into l1 as the last element.
l1.splice(l1.begin(), l2, l2.begin(), l2.begin() + 2);
This is to remove l2’s first three elements and insert them into l1 at the beginning.
This is to remove all elements from l2 and insert them into l2, and the result is in sorted order. Before this operation, the two lists must already be in sorted order. The second version of “merge” takes another argument - a binary predicate method to determine the actually sorting order.
This is to remove duplicated elements in the list. Before this operation the list must already be in sorted order. A second version of “unique” method takes an argument as a predicate method, to determine whether two elements are equal.
l1.swap(l2); // exchange the contents of l1 with l2
l1.assign(l2.begin(), l2.end());
This is to replace the content of l1 with content of l2 in the specified range.
v1.remove(44); // remove all elements with value 44
You can see that list has much more methods than vector. It is because vector can access its elements randomly via subscripts, most of these functionality can be done very easily by clients. There is no need to provide such methods.
9.12 Deque
Class deque is designed to combine the advantages of vector and list together. Like a vector, a deque can be randomly accessed via subscripts, and like a list, elements can be conveniently inserted and deleted at both ends of the deque. Because of this combination, a deque iterator must be more intelligent than a vector iterator. Insertion and deletion at the middle of a deque is optimized to minimize the number of elements copied.
Header file of deque is .
deque has two more methods of its own:
push_front
pop_front
9.13 Comparison of vector, list and deque
Vector has the best random access performance. So a vector is always the first choice if delete and insert only happens at the back of the collection. If insertion and deletion frequently happens at both ends, a deque is preferred than a list because it is more efficient. If frequent insertion and deletion also happens in the middle of the collection, then we should use a list.
9.14 Associative Containers
All associative containers store and retrieve elements essentially in pairs: one is the key, one is the value. Multisets and sets use their values as keys, while multimaps and maps use a separate key for each of the value.
In an associative container, the way to quickly search for an element by its key is to put all the keys and the addresses of the elements or records in a look-up table arranged with searching algorithms such as binary tree, b tree or b+ tree. The size of the look-up table should be minimal to speed up the searching process, so the size of the key itself must be minimal. Because sets uses elements themselves as keys, its elements must be of minimal size. If the element size is too big to be a key, then you should use a separate key to represent the value, that is to say, you have to use maps. The separate key may very probably be a field of the element, such as the employee number of class Employee.
Therefore, the key difference between sequential containers and associative containers is: sequential container elements are stored in by themselves, while associative container elements are stored with a look-up table.
Regardless of the sequence in which the elements are inserted, they are always in sorted order.
=>Common Methods
find
lower_bound
upper_bound
count
Because associative containers can only be accessed through keys, all their methods are key-related.
9.15 Class pair
Class pair has two public data members of any two types:
template<class T1, class T2>
class pair
{
public:
T1 first;
T2 second;
pair() {}
pair(const T1 & x, const T2 & y)
: first(x), second(y) {}
};
It is used to store a pair of values so that a method can return a pair of values. In .
9.16 multiset
The elements themselves are used as keys. The ordering of the elements is decided by a comparator method object such as “less“.
The type of the key must support appropriate comparison, e.g., keys sorted with “less” must support operator<.
A multiset container supports bidirectional iterators.
Header file of multiset is .
=>Sample Program
typedef multiset<int, less<int> > ims1; // declare an alias of multiset type
ims1 m1; // create an empty multiset
cout << m1.count(15); // count the number of keys with value of 15
m1.insert(15);
This is to insert 15 into the multiset. The second version of insert takes an iterator and a value as arguments and begins the search for the insertion point from the iterator position specified.
The above third version takes two iterators as arguments to specify a range of values from another container to add into the multiset:
ims1 const_iterator result;
result = m1.find(15);
Method “find” returns an iterator or a const_iterator pointing to the first element with value 15. If not found, it will return an iterator to the position after the last element.
cout << *( m1.upper_bound(15) ) << *( m1.lower_bound(15) );
Method “upper_bound” returns an iterator or const_iterator to the first element with value 15, while method “lower_bound” returns an iterator or const_iterator to the location after the last element with value 15. If not found, they both return an iterator to the position after the last element.
pair< ims1::const_iterator, ims1::const_iterator > p1;
p = m1.equal_range(22);
cout << *(p1.first) << *(p1.second);
Method “equal_range” returns a pair object containing the lower_bound and upper_bound of 22. Then we can access the two elements through the two iterators stored in the pair.
9.17 set
The methods of set are identical to multiset, except that a set must not have duplicated keys.
typedef set< double, less<double> > double_set;//define an alias of a set type
double_set s1(a, a + size); // create a set out of part of an array
pair< double_set1::const_iterator, bool > p;
p = s1.insert(13.8);
Method “insert” will first search for the element of 13.8. If element found, it will return an iterator to the found element and a false value to indicate that the value was not inserted. If the element is not found, it will insert that value in the set, return an iterator to the inserted element and a true value to indicate the successful insertion.
9.18 multimap
Elements of maps are sorted and organized very similar to sets. Many of their methods are the same. The only difference is that in a map a separate key is used to represent a value. Both the key and the value can be of any type. Just as the sets, the ordering of the keys is determined by a predicate method such as less. The maps support bidirectional iterators.
Multimaps allows duplicated keys, so you can have duplicated values with the same key. This is called “one-to-many” relationship.
typedef multimap< int, double, less<int> > mmid1;
mmid1 m1;
m1.insert( mmid1::value_type( 15, 2.73 ) );
“value_type” is one of those pre-defined types just like iterators, const_iterators. It represents the type used in the container.
for(mmid1::const_iterator i = m1.begin(); i != m1.end(); i++)
cout << i->first << i->second;
This is to traverse the multiset with a const_iterator and print out the key and the value of each element.
Header file of both multimap and map is
9.19 map
Duplicated keys are not allowed in a map, so only a single value can be associated with each key. This is called a “one-to-one mapping”.
Because of this “one-to-one mapping”, you can specify the key and get back the associated value quickly. A map is also called an “associative array”, for you can provide the key in subscript operator [] and locate the element. Insertion and deletion can be done anywhere efficiently.
typedef map< int, double, less<int> > mid;
mid m1;
m1.insert( mid::value_type(15, 2.73) );
m1[13] = 8.93;
When key 13 is in the map, operator[ ] returns a reference to the element, so that it can be assigned 8.93. If key 13 is not in the map, operator[ ] inserts the key and returns a reference to the value.
9.20 Container Adapters
Container adapters are implemented upon first-class containers, just like shrinking inheritance. Some extra implementations can also be added to achieve more specific task, such as the sorting of priority_queue. They don’t support iterators. There are three types of adapters: stack, queue and priority_queue. Their common methods are push and pop.
9.21 Stack
A stack enables insertion and deletion at the same end of the underlying data structure, commonly referred to as a last-in-first-out data structure. A stack can be implemented with any of the sequence containers: vector, list and deque. By default it is deque. For best performance, use vector or deque as the underlying container.
All stack methods are implemented as inline to avoid an extra method call.
Header file of stack is .
=>Methods
push: insert an element by calling underlying container method push_back
pop: remove an element by calling pop_back
top: return a reference to the top element by calling back
empty: determine if the stack is empty by calling empty
size: return the size of the stack by calling stack
=>Sample Program
stack<int> s1; // using a deque<int> as underlying container
stack<int, vector<int>> s2; // using a vector<int> as underlying container
stack<int, list<int>> s3; // using a list<int> as underlying container
9.22 queue
A queue enables insertion at one end of the underlying container, and deletion from the other end. This is referred to as FIFO data structure. A queue can be implemented with deque and list. By default it is deque. It can perform better than list.
All queue methods are implemented as inline to avoid an extra method call.
Header file of queue is .
=>Methods
push: insert at the back by calling underlying container method push_back
pop: remove at the front by calling pop_front (that is the reason why vector can not be used)
front: return a reference to the first element by calling front
back: return a reference to the last element by calling back
empty
size
9.23 priority_queue
A priority_queue can be implemented with vector and deque. By default it is vector. A priority_queue is a sorted vector. When adding elements to priority_queue, the elements are automatically inserted in priority order, so that the highest priority element i.e. the largest element is always the first to be removed. This is accomplished by using a sorting technique called “heapsort”, and such a data structure is called a “heap”.
The ordering of the elements is performed with comparator method object less. Programmer can also supply their own comparator.
=>Methods
push: insert an element at the proper location, by calling push _back then sorting the container using heapsort pop: remove the highest-priority element by calling pop_back top: return a reference to the top element by calling front empty size
9.24 Introduction to Algorithms
Only some basic functionality is implemented through container’s methods, while most of the implementations are provided by independent STL algorithms. Such separation makes it easier to add new algorithms without modifying containers. Algorithms operate on containers through iterators, and many of them use a pair of iterators specifying a range of elements in a container. This pair of iterators is most commonly provided by container method begin and end. Header file of algorithms is or .
=>Common Non-mutating Algorithms
adjacent-find
count
count-if
equal
find
for_each
mismatch
search
search_n
=>Numerical algorithms from
accumulate
inner_product
partial_sum
adjacent_difference
9.25 Fill Container with Objects
fill(c1.begin(), c1.end(), ‘A’);
set every element to be ‘A’. Takes at least forward iterators.
fill_n(c1.begin(), 5, ‘A’);
set the first 5 elements to be ‘A’. Takes at least output iterators.
generate(c1.begin(), c1.end(), myFill);
char myFill() // generator method
{
static char c = 'A';
return c++;
}
set all elements of the container with objects provided by a generator method. Takes at least forward iterators.
generate_n(c1.begin(), 5, generate);
set first 5 elements. Takes at least output iterator.
9.26 Compare Elements
bool result = equal( c1.begin(), c1.end(), c2.begin() );
compare elements of two containers using their operator = =. Takes at least input iterators.
typedef vector::iterator vv1;
pair location;
location = mismatch( c1.begin(), c1.end(), c2.begin() );
compare elements of two containers using their operator = =, and return a pair of iterators pointing to the mismatching element in both containers. If all equal, the pair will be equal to the last iterator. Takes at least input iterators.
char c1[8] = “Hello”, c2[8] = “Good-bye”;
bool result = lexicographical_compare(c1, c1 + 8, c2, c2 + 8);
return true if first is greater than second.
if( includes(a1, a1 + SIZE1, a2, a2 + SIZE2) )
method “includes” compares the two sets of sorted values, and returns true if set is include in set 1. Takes at least input iterators.
9.27 Remove Elements
vector::iterator i = remove( c1.begin(), c1.end(), 10);
eliminate all elements with value of 10. It doesn’t erase the element like erase method, it only move all untouched elements forward, leaving all eliminated elements at the back, with undefined values. It returns an iterator pointing to the last retained element. So the size of the container is not changed. Takes at least forward iterators.
i = remove_copy(c1.begin(), c1.end(), c2.begin(), 10);
copy all elements that DO NOT have the value of 10 from container c1 into container c2. It returns an iterator to the last copied element in c2. The first two arguments must be at least input iterators, while the third must be at least output iterators.
i = remove_if(c1.begin(), c1.end(), myJudge);
bool myJudge(int x)
{ return x > 9; }
eliminates all elements that the user-defined unary predicate method will return true. It does the same thing on eliminated elements like remove. Takes at least forward iterators.
i = remove_copy_if(c1.begin(), c1.end(), c2.begin(), judge);
combination of remove_if and remove_copy.
9.28 Replace Elements
replace(c1.begin(), c1.end(), 10, 100);
replace all elements with a value of 10 with 100. Takes at least forward iterators.
replace_copy(c1.begin(), c1.end(), c2.begin(), 10, 100);
copy all elements in c1 in the specified range into c2, replacing all values of 10 with 100. Returns an iterator to the last copied element in c2. The first two arguments must be at least input iterators, while the third must be at least output iterators.
replace_if(c1.begin(), c1.end(), judge, 100);
replace all elements that the user-defined unary predicate method returns true with value 100. Takes at least forward iterators.
replace_copy_if(c1.begin(), c1.end(), c2.begin(), judge, 100);
combination of replace_if and replace_copy.
9.29 Mathematical Algorithms
random_shuffle(c1.begin(), c1.end());
randomly shuffle the elements in the specified range. Takes random-access iterators.
int result = count(c1.begin(), c1.end(), 8);
count the number of elements with value of 8. Takes at least input iterators.
result = count_if(c1.begin(), c1.end(), myJudge);
count the number of elements that the user-defined unary predicate method will return true. Takes at least input iterators.
vector::iterator i1, i2;
i1 = min_element(c1.begin(), c1.end());
i2 = max_element(c1.begin(), c1.end());
return an iterator to the smallest/largest element in the specified range. Takes at least input iterators.
result = accumulate(c1.begin(), c1.end(), 0);
sums up the elements, with initial value as the third argument. Operator += should be implemented. Takes at least input iterators.
result = accumulate(c1.begin(), c1.end(), myCalculate, 0);
int myCalculate(int accumulation, int element)
{ return accumulation += element * element; }
A second version of accumulate takes as its third argument a name of a user-defined method which determines how to accumulate.
for_each(c1.begin(), c1.end(), myMethod);
applies myMethod which takes one element as argument to each element. The method can not modify the elements. If you want to modify, use method transform. Takes at least input iterators.
transform(c1.begin(), c1.end(), c2.begin(), myMethod);
applies myMethod to each of the elements in c1, and place result in c2. c2 can be also c1. Takes at least input iterators.
9.30 Searching and Sorting Elements
vector::iterator i;
i = find(c1.begin(), c1.end(), 16);
return an iterator to the element of value 16. Takes at least input iterators.
i = find_if(c1.begin(), c1.end(), myJudge);
return an iterator to the element that the user-defined unary predicate method returns true. Takes at least input iterators.
sort(c1.begin(), c1.end());
sort the elements in ascending order. A second version takes a third argument as a binary predicate method which returns a bool type to decide the sorting order.
bool result = binary_search(c1.begin(), c1.end(), 223);
use binary search to determine whether 223 is in the specified range.
9.31 Swap Elements
swap(a[0], a[1]);
//swap the two arguments.
iter_swap(v1.begin(), v1.begin + 3);
//exchange the first and fourth element.
swap_ranges(a, a+5, a+10);
//exchange a range of elements from a to (but not including)
//a + 5, with a range of elements starting from a + 10.
//Takes three forward iterators.
9.32 Copy Elements
copy_backward(v1.begin(), v1.end(), v2.end());
copy a range of elements from one container to another, starting from the element before v1.end to v1.begin, returning an iterator at the last elements copied (v1.begin). Takes three bidirectional iterators.
The main difference between algorithm copy and copy_backward is: copy returns an iterator after the last copied element, while copy_backward returns an iterator at the last copied element.
unique_copy(v1.begin(), v1.end(), back_inserter(v2));
use back_inserter to insert all unique values into container v2. Takes at least output iterators.
reverse_copy(v1.begin(), v1.end(), back_inserter(v2));
make a reversed copy of v1 and insert into v2. First two iterators to be at least bidirectional, and third to be output.
i = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3);
copy the elements in v1 which are not in v2 into v3. Both v1 and v2 must be in ascending order. It returns an output iterator at the last copied element in v3. The first four iterators must be at least input iterators, while the last output iterator.
i = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3);
copy the elements in v1 which are also in v2 into v3. Both v1 and v2 must be in ascending order. It returns an output iterator at the last copied element in v3. The first four iterators must be at least input iterators, while the last output iterator.
i = set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3);
copy elements in v1 that are not in v2 and elements in v2 that are not in v1 into v3. Both v1 and v2 must be in ascending order. It returns an output iterator at the last copied element in v3. The first four iterators must be at least input iterators, while the last output iterator.
i = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3);
copy elements that are either in one of v1 and v2 or in both of them into v3. Elements that are both in v1 and v2 are only copied from v1. Both v1 and v2 must be in ascending order. It returns an output iterator at the last copied element in v3. The first four iterators must be at least input iterators, while the last output iterator.
9.33 Merge Containers
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
combine two sorted ascending sequences of values into a third sorted ascending sequence. The first four iterators must be at least input iterators, while the last output iterator.
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), front_inserter(v3));
merge(v1.begin(), v1.end(), v2.begin(), v2.end(),inserter(v3, v3.begin() + 2));
template method back_inserter is in . It calls the container’s method push_back to insert an element at the back of the container v3. There are two other inserters.
inplace_merge(v1.begin(), v1.begin + 5, v1.begin() + 10);
Reorders the sequences designated by iterators in the two ranges [0, 5) and [5, 10), each ordered by operator<, to form a merged sequence of length 10 beginning at first, also ordered by operator<. The merge occurs without altering the relative order of elements within either original sequence. Moreover, for any two elements from different original sequences that have equivalent ordering, the element from the ordered range [0, 5) precedes the other. Takes at least bidirectional iterators.
9.34 Unify Elements
i = unique(v1.begin(), v1.end());
after unique is applied to the range of elements, only a single copy of each value is left. It returns an iterators after the last legal element in the sequence - the rest of values are undefined. Takes at least forward iterators.
9.35 Reverse Elements
reverse(v1.begin(), v1.end());
reverse the elements. Takes at least bidirectional iterators.
9.36 Locate Element in Sorted Container
i = lower_bound(v1.begin(), v1.end(), 233);
return an iterator to locate the first right location in an ascending-order sequence, at which the value 233 can be inserted, while still keeping the new sequence in ascending order. Takes at least forward iterators.
i = upper_bound(v1.begin(), v1.end(), 233);
return an iterator to locate the last right location in an ascending-order sequence, at which the value 233 can be inserted, while still keeping the new sequence in ascending order. Takes at least forward iterators.
typedef vector<int>::iterator vv1;
pair<vv1, vv1> p1;
p1 = equal_range(v1.begin(), v1.end(), 233);
return a pair of iterators to locate both the first and the last right location in an ascending-order sequence, at which the value 233 can be inserted, while still keeping the new sequence in ascending order. Takes at least forward iterators.
These three algorithms are usually used to locate insertion point in sorted sequences.
9.37 Heapsort
Heapsort is a sorting method, in which an array of elements is arranged into a special binary tree called a heap. The key features of a heap are that the largest element is always at the top of the heap, and the values of the children of any node in the binary tree are always less than or equal to that node’s value. Such a heap is called a maxheap.
make_heap(v1.begin(), v1.end());
take the values and create a heap, so that it can be sorted. Only takes random-access iterators - therefore only can be used on arrays, vectors and deques.
sort_heap(v1.begin(), v1.end());
sort a sequence which had been arranged in a heap. Only takes random-access iterators.
push_heap(v1.begin(), v1.end());
add a new value into a heap. Each time push_heap is called, it assumes that the last element in the vector is the one newly added and all the rest elements have already been arranged as a heap. Only takes random-access iterators.
for ( i = 0; i < v1.size(); ++i)
pop_heap(v1.begin(), v1.end() - i);
swap the top element with the one before v1.end - i. Finally results in a sorted sequence. The method assumes that the range of values specified by the two arguments has already been a heap.
9.38 min & max
determine the minimum and maximum of two containers.
Popularity: 26%