c++ homework help assignment 11
homeworkhelp325
csc_262_day_18.pptx1
CSC 262 Programming in C++ II Sykes Day 18
22.1 Introduction to the Standard Template Library (STL)
We’ve repeatedly emphasized the importance of software reuse.
Recognizing that many data structures and algorithms are commonly used, the C++ standard committee added the Standard Template Library (STL) to the C++ Standard Library.
The STL defines powerful, template-based, reusable components that implement many common data structures and algorithms used to process those data structures.
2
22.1 Introduction to the Standard Template Library (STL) (Cont.)
As you’ll see, the STL was conceived and designed for performance and flexibility.
This chapter introduces the STL and discusses its three key components—containers (popular templatized data structures), iterators and algorithms.
The STL containers are data structures capable of storing objects of almost any data type (there are some restrictions).
We’ll see that there are three styles of container classes—first-class containers, adapters and near containers.
3
4
22.1 Introduction to the Standard Template Library (STL) (Cont.)
STL iterators, which have properties similar to those of pointers, are used by programs to manipulate the STL-container elements.
In fact, standard arrays can be manipulated by STL algorithms, using standard pointers as iterators.
We’ll see that manipulating containers with iterators is convenient and provides tremendous expressive power when combined with STL algorithms—in some cases, reducing many lines of code to a single statement.
There are five categories of iterators, each of which we discuss in Section 22.1.2 and use throughout this chapter.
5
22.1 Introduction to the Standard Template Library (STL) (Cont.)
STL algorithms are functions that perform such common data manipulations as searching, sorting and comparing elements (or entire containers).
The STL provides approximately 70 algorithms.
Most of them use iterators to access container elements.
Each algorithm has minimum requirements for the types of iterators that can be used with it.
We’ll see that each first-class container supports specific iterator types, some more powerful than others.
A container’s supported iterator type determines whether the container can be used with a specific algorithm.
6
22.1 Introduction to the Standard Template Library (STL) (Cont.)
Iterators encapsulate the mechanism used to access container elements.
This encapsulation enables many of the STL algorithms to be applied to several containers without regard for the underlying container implementation.
As long as a container’s iterators support the minimum requirements of the algorithm, then the algorithm can process that container’s elements.
This also enables you to create new algorithms that can process the elements of multiple container types.
7
8
22.1 Introduction to the Standard Template Library (STL) (Cont.)
In Chapter 20, we studied data structures.
We built linked lists, queues, stacks and trees.
We carefully wove link objects together with pointers.
Pointer-based code is complex, and the slightest omission or oversight can lead to serious memory-access violations and memory-leak errors with no compiler complaints.
Implementing additional data structures, such as deques, priority queues, sets and maps, requires substantial extra work.
An advantage of the STL is that you can reuse the STL containers, iterators and algorithms to implement common data representations and manipulations.
9
10
11
Iterators
Recall: generalization of a pointer
Typically even implemented with pointer!
"Abstraction" of iterators
Designed to hide details of implementation
Provide uniform interface across different container classes
Each container class has "own" iterator type
Similar to how each data type has own pointer type
19-12
12
Manipulating Iterators
Recall using overloaded operators:
++, --, ==, !=
*
So if p is iterator variable, *p gives access to data pointed to by p
Vector template class
Has all above overloads
Also has members begin() and end() c.begin(); //Returns iterator for 1st item in c c.end(); //Returns "test" value for end
19-13
13
Cycling with Iterators
Recall cycling ability: for (p=c.begin();p!=c.end();p++) process *p //*p is current data item
Big picture so far…
Keep in mind:
Each container type in STL has own iterator types
Even though they’re all used similarly
19-14
14
Display 19.1 Iterators Used with a Vector (1 of 2)
19-15
1 //Program to demonstrate STL iterators.
2 #include <iostream>
3 #include <vector>
4 using std::cout;
5 using std::endl;
6 using std::vector;
7 int main( )
8 {
9 vector<int> container;
10 for (int i = 1; i <= 4; i++)
11 container.push_back(i);
12 cout << "Here is what is in the container:\n";
13 vector<int>::iterator p;
14 for (p = container.begin( ); p != container.end( ); p++)
15 cout << *p << " ";
16 cout << endl;
17 cout << "Setting entries to 0:\n";
18 for (p = container.begin( ); p != container.end( ); p++)
19 *p = 0;
15
Display 19.1 Iterators Used with a Vector (2 of 2)
19-16
20 cout << "Container now contains:\n";
21 for (p = container.begin( ); p !=
container.end( ); p++)
22 cout << *p << " ";
23 cout << endl;
24 return 0;
25 }
Sample Dialogue
Here is what is in the container:
1 2 3 4
Setting entries to 0:
Container now contains:
0 0 0 0
16
Vector Iterator Types
Iterators for vectors of ints are of type: std::vector<int>::iterator
Iterators for lists of ints are of type: std::list<int>::iterator
Vector is in std namespace, so need: using std::vector<int>::iterator;
19-17
17
Kinds of Iterators
Different containers different iterators
Vector iterators
Most "general" form
All operations work with vector iterators
Vector container great for iterator examples
19-18
18
Random Access: Display 19.2 Bidirectional and Random-Access Iterator Use
19-19
19
Iterator Classifications
Forward iterators:
++ works on iterator
Bidirectional iterators:
Both ++ and – work on iterator (“--“)
Random-access iterators:
++, --, and random access all work with iterator
These are "kinds" of iterators, not types!
19-20
20
Constant and Mutable Iterators
Dereferencing operator’s behavior dictates
Constant iterator:
* produces read-only version of element
Can use *p to assign to variable or output, but cannot change element in container
E.g., *p = <anything>; is illegal
Mutable iterator:
*p can be assigned value
Changes corresponding element in container
i.e.: *p returns an lvalue
19-21
21
Reverse Iterators
To cycle elements in reverse order
Requires container with bidirectional iterators
Might consider: iterator p; for (p=container.end();p!=container.begin(); p--) cout << *p << " " ;
But recall: end() is just "sentinel", begin() not!
Might work on some systems, but not most
19-22
22
Reverse Iterators Correct
To correctly cycle elements in reverse order: reverse_iterator p; for (rp=container.rbegin();rp!=container.rend(); rp++) cout << *rp << " " ;
rbegin()
Returns iterator at last element
rend()
Returns sentinel "end" marker
19-23
23
Compiler Problems
Some compilers problematic with iterator declarations
Consider our usage: using std::vector<char>::iterator; … iterator p;
Alternatively: std::vector<char>::iterator p;
And others…
Try various forms if compiler problematic
19-24
24
22.1.2 Introduction to Iterators (Cont.)
STL first-class containers provide member functions begin and end.
Function begin returns an iterator pointing to the first element of the container.
Function end returns an iterator pointing to the first element past the end of the container (an element that doesn’t exist).
25
22.1.2 Introduction to Iterators (Cont.)
If iterator i points to a particular element, then ++i points to the “next” element and *i refers to the element pointed to by i.
The iterator resulting from end is typically used in an equality or inequality comparison to determine whether the “moving iterator” (i in this case) has reached the end of the container.
An object of type iterator refers to a container element that can be modified.
An object of type const_iterator refers to a container element that cannot be modified.
26
22.1.2 Introduction to Iterators (Cont.)
Figure 22.9 shows the predefined iterator typedefs that are found in the class definitions of the STL containers.
Not every typedef is defined for every container.
We use const versions of the iterators for traversing read-only containers.
We use reverse iterators to traverse containers in the reverse direction.
27
28
29
22.1.2 Introduction to Iterators (Cont.)
Figure 22.10 shows some operations that can be performed on each iterator type.
The operations for each iterator type include all operations preceding that type in the figure.
30
31
32
33
34
35
36
22.1.2 Introduction to Iterators (Cont.)
Figure 22.6 shows the categories of STL iterators.
Each category provides a specific set of functionality.
Figure 22.7 illustrates the hierarchy of iterator categories.
As you follow the hierarchy from top to bottom, each iterator category supports all the functionality of the categories above it in the figure.
Thus the “weakest” iterator types are at the top and the most powerful one is at the bottom.
Note that this is not an inheritance hierarchy.
37
38
39
40
Containers
Container classes in STL
Different kinds of data structures
Like lists, queues, stacks
Each is template class with parameter for particular data type to be stored
e.g., Lists of ints, doubles or myClass types
Each has own iterators
One might have bidirectional, another might just have forward iterators
But all operators and members have same meaning
19-41
41
22.1.1 Introduction to Containers
The STL container types are shown in Fig. 22.1.
The containers are divided into three major categories—sequence containers, associative containers and container adapters.
42
43
44
22.1.1 Introduction to Containers (Cont.)
The sequence containers represent linear data structures, such as vectors and linked lists.
Associative containers are nonlinear containers that typically can locate elements stored in the containers quickly.
Such containers can store sets of values or key/value pairs.
The sequence containers and associative containers are collectively referred to as the first-class containers.
As we saw in Chapter 20, stacks and queues actually are constrained versions of sequential containers.
For this reason, STL implements stacks and queues as container adapters that enable a program to view a sequential container in a constrained manner.
45
22.1.1 Introduction to Containers (Cont.)
There are other container types that are considered “near containers”—C-like pointer-based arrays (discussed in Chapter 7), bitsets for maintaining sets of flag values and val-arrays for performing high-speed mathematical vector operations (this last class is optimized for computation performance and is not as flexible as the first-class containers).
These types are considered “near containers” because they exhibit capabilities similar to those of the first-class containers, but do not support all the first-class-container capabilities.
Type string (discussed in Chapter 18) supports the same functionality as a sequence container, but stores only character data.
46
22.1.2 Introduction to Iterators (Cont.)
The iterator category that each container supports determines whether that container can be used with specific algorithms in the STL.
Containers that support random-access iterators can be used with all algorithms in the STL.
As we’ll see, pointers into arrays can be used in place of iterators in most STL algorithms, including those that require random-access iterators.
Figure 22.8 shows the iterator category of each of the STL containers.
The first-class containers (vectors, deques, lists, sets, multisets, maps and multimaps), strings and arrays are all traversable with iterators.
47
48
22.1.1 Introduction to Containers (Cont.)
Most STL containers provide similar functionality.
Many generic operations, such as member function size, apply to all containers, and other operations apply to subsets of similar containers.
This encourages extensibility of the STL with new classes.
Figure 22.2 describes the functions common to all Standard Library containers.
[Note: Overloaded operators operator<, operator<=, operator>, operator>=, operator== and operator!= are not provided for priority_queues.]
49
50
51
52
22.1.1 Introduction to Containers (Cont.)
The header files for each of the Standard Library containers are shown in Fig. 22.3.
The contents of these header files are all in namespace std.
53
54
22.1.1 Introduction to Containers (Cont.)
Figure 22.4 shows the common typedefs (to create synonyms or aliases for lengthy type names) found in first-class containers.
These typedefs are used in generic declarations of variables, parameters to functions and return values from functions.
For example, value_type in each container is always a typedef that represents the type of value stored in the container.
55
56
57
58
59
22.1.1 Introduction to Containers (Cont.)
When preparing to use an STL container, it’s important to ensure that the type of element being stored in the container supports a minimum set of functionality.
When an element is inserted into a container, a copy of that element is made.
For this reason, the element type should provide its own copy constructor and assignment operator.
[Note: This is required only if default memberwise copy and default memberwise assignment do not perform proper copy and assignment operations for the element type.]
Also, the associative containers and many algorithms require elements to be compared.
For this reason, the element type should provide an equality operator (==) and a less-than operator (<).
60
61
Sequential Containers
Arranges list data
1st element, next element, … to last element
Linked list is sequential container
Earlier linked lists were "singly linked lists"
One link per node
STL has no "singly linked list"
Only "doubly linked list": template class list
19-62
62
Display 19.4 Two Kinds of Lists
19-63
63
Display 19.5 Using the list Template Class(1 of 2)
19-64
1 //Program to demonstrate the STL template class list.
2 #include <iostream>
3 #include <list>
4 using std::cout;
5 using std::endl;
6 using std::list;
7 int main( )
8 {
9 list<int> listObject;
10 for (int i = 1; i <= 3; i++)
11 listObject.push_back(i);
12 cout << "List contains:\n";
13 list<int>::iterator iter;
14 for (iter = listObject.begin( ); iter != listObject.end( );
iter++)
15 cout << *iter << " ";
16 cout << endl;
64
Display 19.5 Using the list Template Class(2 of 2)
19-65
17 cout << "Setting all entries to 0:\n";
18 for (iter = listObject.begin( ); iter != listObject.end( );
iter++)
19 *iter = 0;
20 cout << "List now contains:\n";
21 for (iter = listObject.begin( ); iter != listObject.end( );
iter++)
22 cout << *iter << " ";
23 cout << endl;
24 return 0;
25 }
SAMPLE DIALOGUE
List contains:
1 2 3
Setting all entries to 0:
List now contains:
0 0 0
65
Associative Containers
Associative container: simple database
Store data
Each data item has key
Example: data: employee’s record as struct key: employee’s SSN
Items retrieved based on key
19-66
66
22.3 Associative Containers
The STL’s associative containers provide direct access to store and retrieve elements via keys (often called search keys).
The four associative containers are multiset, set, multimap and map.
Each associative container maintains its keys in sorted order.
Iterating through an associative container traverses it in the sort order for that container.
Classes multiset and set provide operations for manipulating sets of values where the values are the keys—there is not a separate value associated with each key.
The primary difference between a multiset and a set is that a multiset allows duplicate keys and a set does not.
67
22.3 Associative Containers (Cont.)
Classes multimap and map provide operations for manipulating values associated with keys (these values are sometimes referred to as mapped values).
The primary difference between a multimap and a map is that a multimap allows duplicate keys with associated values to be stored and a map allows only unique keys with associated values.
In addition to the common member functions of all containers presented in Fig. 22.2, all associative containers also support several other member functions, including find, lower_bound, upper_bound and count.
Examples of each of the associative containers and the common associative container member functions are presented in the next several subsections.
68
set Template Class
Simplest container possible
Stores elements without repetition
1st insertion places element in set
Each element is own key
Capabilities:
Add elements
Delete elements
Ask if element is in set
19-69
69
22.3.2 set Associative Container
The set associative container is used for fast storage and retrieval of unique keys.
The implementation of a set is identical to that of a multiset, except that a set must have unique keys.
Therefore, if an attempt is made to insert a duplicate key into a set, the duplicate is ignored; because this is the intended mathematical behavior of a set, we do not identify it as a common programming error.
A set supports bidirectional iterators (but not random-access iterators).
Figure 22.20 demonstrates a set of doubles.
Header file <set> must be included to use class set.
70
Program Using the set Template Class (1 of 2)
19-71
1 //Program to demonstrate use of the set template class.
2 #include <iostream>
3 #include <set>
4 using std::cout;
5 using std::endl;
6 using std::set;
7 int main( )
8 {
9 set<char> s;
10 s.insert(’A’);
11 s.insert(’D’);
12 s.insert(’D’);
13 s.insert(’C’);
14 s.insert(’C’);
15 s.insert(’B’);
16 cout << "The set contains:\n";
17 set<char>::const_iterator p;
18 for (p = s.begin( ); p != s.end( ); p++)
19 cout << *p << " ";
20 cout << endl;
71
Program Using the set Template Class (2 of 2)
19-72
21 cout << "Set contains 'C': ";
22 if (s.find('C')==s.end( ))
23 cout << " no " << endl;
24 else
26 cout << " yes " << endl;
27 cout << "Removing C.\n";
28 s.erase(’C’);
29 for (p = s.begin( ); p != s.end( ); p++)
30 cout << *p << " ";
31 cout << endl;
32 cout << "Set contains 'C': ";
33 if (s.find('C')==s.end( ))
34 cout << " no " << endl;
35 else
36 cout << " yes " << endl;
37 return 0;
38 }
SAMPLE DIALOGUE
The set contains:
A B C D
Set contains 'C': yes
Removing C.
A B D
Set contains 'C': no
72
Map Template Class
A function given as set of ordered pairs
For each value first, at most one value second in map
Example map declaration: map<string, int> numberMap;
Can use [ ] notation to access the map
For both storage and retrieval
Stores in sorted order, like set
Second value can have no ordering impact
19-73
73
22.3.4 map Associative Container
The map associative container performs fast storage and retrieval of unique keys and associated values.
Duplicate keys are not allowed—a single value can be associated with each key.
This is called a one-to-one mapping.
For example, a company that uses unique employee numbers, such as 100, 200 and 300, might have a map that associates employee numbers with their telephone extensions—4321, 4115 and 5217, respectively.
With a map you specify the key and get back the associated data quickly.
A map is also known as an associative array.
Providing the key in a map’s subscript operator [] locates the value associated with that key in the map.
74
Program Using the map Template Class (1 of 3)
19-75
1 //Program to demonstrate use of the map template class.
2 #include <iostream>
3 #include <map>
4 #include <string>
5 using std::cout;
6 using std::endl;
7 using std::map;
8 using std::string;
9 int main( )
10 {
11 map<string, string> planets;
12 planets["Mercury"] = "Hot planet";
13 planets["Venus"] = "Atmosphere of sulfuric acid";
14 planets["Earth"] = "Home";
15 planets["Mars"] = "The Red Planet";
16 planets["Jupiter"] = "Largest planet in our solar system";
17 planets["Saturn"] = "Has rings";
18 planets["Uranus"] = "Tilts on its side";
19 planets["Neptune"] = "1500 mile per hour winds";
20 planets["Pluto"] = "Dwarf planet";
75
Program Using the map Template Class (2 of 3)
19-76
21 cout << "Entry for Mercury - " << planets["Mercury"]
22 << endl << endl;
23 if (planets.find("Mercury") != planets.end())
24 cout << "Mercury is in the map." << endl;
25 if (planets.find("Ceres") == planets.end())
26 cout << "Ceres is not in the map." << endl << endl;
27 cout << "Iterating through all planets: " << endl;
28 map<string, string>::const_iterator iter;
29 for (iter = planets.begin(); iter != planets.end(); iter++)
30 {
31 cout << iter->first << " - " << iter->second << endl;
32 }
The iterator will output the map in order sorted by the key. In this case the output will be listed alphabetically by planet.
33 return 0;
34 }
76
Program Using the map Template Class (3 of 3)
19-77
SAMPLE DIALOGUE
Entry for Mercury - Hot planet
Mercury is in the map.
Ceres is not in the map.
Iterating through all planets:
Earth - Home
Jupiter - Largest planet in our solar system
Mars - The Red Planet
Mercury - Hot planet
Neptune - 1500 mile per hour winds
Pluto - Dwarf planet
Saturn - Has rings
Uranus - Tilts on its side
Venus - Atmosphere of sulfuric acid
77
Container Adapters stack and queue
Container adapters are template classes
Implemented "on top of" other classes
Example: stack template class by default implemented on top of deque template class
Buried in stack’s implementation is deque where all data resides
Others: queue, priority_queue
19-78
78
Specifying Container Adapters
Adapter template classes have "default" containers underneath
But can specify different underlying container
Examples: stack template class any sequence container priority_queue default is vector, could be others
Implementing Example: stack<int, vector<int>>
Makes vector underlying container for stack
19-79
79
22.4 Container Adapters
The STL provides three container adapters—stack, queue and priority_queue.
Adapters are not first-class containers, because they do not provide the actual data-structure implementation in which elements can be stored and because adapters do not support iterators.
The benefit of an adapter class is that you can choose an appropriate underlying data structure.
All three adapter classes provide member functions push and pop that properly insert an element into each adapter data structure and properly remove an element from each adapter data structure.
80
22.4.1 stack Adapter
Class stack enables insertions into and deletions from the underlying data structure at one end (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.
This example creates three integer stacks, using each of the sequence containers of the Standard Library as the underlying data structure to represent the stack.
By default, a stack is implemented with a deque.
81
22.4.1 stack Adapter (Cont.)
The stack operations are push to insert an element at the top of the stack (implemented by calling function push_back of the underlying container), pop to remove the top element of the stack (implemented by calling function pop_back of the underlying container), top to get a reference to the top element of the stack (implemented by calling function back of the underlying container), empty to determine whether the stack is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the stack (implemented by calling function size of the underlying container).
82
83
84
22.4.2 queue Adapter
Class queue enables insertions at the back of the underlying data structure and deletions from the front (commonly referred to as a first-in, first-out data structure).
A queue can be implemented with STL data structure list or deque.
By default, a queue is implemented with a deque.
85
22.4.2 queue Adapter (Cont.)
The common queue operations are push to insert an element at the back of the queue (implemented by calling function push_back of the underlying container), pop to remove the element at the front of the queue (implemented by calling function pop_front of the underlying container), front to get a reference to the first element in the queue (implemented by calling function front of the underlying container), back to get a reference to the last element in the queue (implemented by calling function back of the underlying container), empty to determine whether the queue is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the queue (implemented by calling function size of the underlying container).
86
87
88
22.4.3 priority_queue Adapter (Cont.)
Class priority_queue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure.
A priority_queue can be implemented with STL sequence containers vector or deque.
By default, a priority_queue is implemented with a vector as the underlying container.
When elements are added to a priority_queue, they’re inserted in priority order, such that the highest-priority element (i.e., the largest value) will be the first element removed from the priority_queue.
89
22.4.3 priority_queue Adapter (Cont.)
This is usually accomplished by arranging the elements in a binary tree structure called a heap that always maintains the largest value (i.e., highest-priority element) at the front of the data structure.
We discuss the STL’s heap algorithms in Section 22.5.12.
The comparison of elements is performed with comparator function object less< T > by default, but you can supply a different comparator.
There are several common priority_queue operations.
push inserts an element at the appropriate location based on priority order of the priority_queue (implemented by calling function push_back of the underlying container, then reordering the elements using heapsort).
90
22.4.3 priority_queue Adapter (Cont.)
pop removes the highest-priority element of the priority_queue (implemented by calling function pop_back of the underlying container after removing the top element of the heap).
top gets a reference to the top element of the priority_queue (implemented by calling function front of the underlying container).
empty determines whether the priority_queue is empty (implemented by calling function empty of the underlying container).
size gets the number of elements in the priority_queue (implemented by calling function size of the underlying container).
91
92
93
22.5 Algorithms
Until the STL, class libraries of containers and algorithms were essentially incompatible among vendors.
Early container libraries generally used inheritance and polymorphism, with the associated overhead of virtual function calls.
Early libraries built the algorithms into the container classes as class behaviors.
The STL separates the algorithms from the containers.
This makes it much easier to add new algorithms.
With the STL, the elements of containers are accessed through iterators.
The next several subsections demonstrate many of the STL algorithms.
94
95
22.5.1 fill, fill_n, generate and generate_n
Figure 22.26 demonstrates algorithms fill, fill_n, generate and generate_n.
Functions fill and fill_n set every element in a range of container elements to a specific value.
Functions generate and generate_n use a generator function to create values for every element in a range of container elements.
The generator function takes no arguments and returns a value that can be placed in an element of the container.
96
22.5.3 remove, remove_if, remove_copy and remove_copy_if
Figure 22.28 demonstrates removing values from a sequence with algorithms remove, remove_if, remove_copy and remove_copy_if.
97
22.5.4 replace, replace_if, replace_copy and replace_copy_if
Figure 22.29 demonstrates replacing values from a sequence using algorithms replace, replace_if, replace_copy and replace_copy_if.
98
22.5.5 Mathematical Algorithms
Figure 22.30 demonstrates several common mathematical algorithms from the STL, including random_shuffle, count, count_if, min_element, max_element, accumulate, for_each and transform.
99
22.5.6 Basic Searching and Sorting Algorithms
Figure 22.31 demonstrates some basic searching and sorting capabilities of the Standard Library, including find, find_if, sort and binary_search.
100
22.5.7 swap, iter_swap and swap_ranges
Figure 22.32 demonstrates algorithms swap, iter_swap and swap_ranges for swapping elements.
Line 18 uses function swap to exchange two values.
In this example, the first and second elements of array a are exchanged.
The function takes as arguments references to the two values being exchanged.
101
22.5.8 copy_backward, merge, unique and reverse
Figure 22.33 demonstrates STL algorithms copy_backward, merge, unique and reverse.
Line 26 uses function copy_backward to copy elements in the range from v1.begin() up to, but not including, v1.end(), placing the elements in results by starting from the element before results.end() and working toward the beginning of the vector.
The function returns an iterator positioned at the last element copied into the results (i.e., the beginning of results, because of the backward copy).
The elements are placed in results in the same order as v1.
102
22.5.8 copy_backward, merge, unique and reverse (Cont.)
This function requires three bidirectional iterator arguments (iterators that can be incremented and decremented to iterate forward and backward through a sequence, respectively).
One difference between copy_backward and copy is that the iterator returned from copy is positioned after the last element copied and the one returned from copy_backward is positioned at the last element copied (i.e., the first element in the sequence).
Also, copy_backward can manipulate overlapping ranges of elements in a container as long as the first element to copy is not in the destination range of elements.
103
Efficiency
STL designed with efficiency as important consideration
Strives to be optimally efficient
Example: set, map elements stored in sorted order for fast searches
Template class member functions:
Guaranteed maximum running time
Called "Big-O" notation, an "efficiency"-rating
19-104
104
