程序代写代做代考 C data structure algorithm c++ COMP2012 Object-Oriented Programming and Data Structures

Operator≪ as a Friend Function Template ..
The friend operator≪ function definition may be defined outside the
Array class template like other class member functions.
Now the friend operator≪ function may access the private members of the Array class.
template /* File: array-op-os-friend.h */
ostream& operator<<(ostream& os, const Array& a)
{
os << "#elements stored = " << a._size << endl; for (int i = 0; i < a._size; ++i) os << a._value[i] << endl; return os; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 12 / 43 Containers in STL 1. Sequence containers 􏰢 Represent linear data structures 􏰢 Start from index/location 0 2. Associative containers 􏰢 Non-sequential containers 􏰢 Store key/value pairs 3. Container adapters 􏰢 Adopted containers that support a limited set of container operations 4. “Near-containers” C-like pointer-based arrays 􏰢 Exhibit capabilities similar to those of the sequence containers, but do not support all their capabilities 􏰢 strings, bitsets and valarrays Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 13 / 43 Containers in STL .. Type of Container Sequence Associative Adapters Near-containers STL Containers vector, list, deque map, multimap, multiset, set priority queue, queue, stack bitset, valarray, string Containers in the same category share a set of same or similar public member functions (i.e., public interface or algorithms). Deque (double-ended queue) 􏰢 Unlike STL vector, the elements of a deque are not stored contiguously;, it uses a sequence of chunks of fixed-size arrays. 􏰢 Like STL vector, the storage of a deque is automatically expanded/contracted as needed, but deque does not require copying of all the existing elements. 􏰢 Allows fast insertion and deletion at both ends. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 14 / 43 Deque (Double-Ended QUEue) Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 15 / 43 Sequence Containers: Access, Add, Remove Element access for all: front(): First element back(): Last element Element access for vector and deque: [ ]: Subscript operator, index not checked. Add/remove elements for all: push back(): Append element. pop back(): Remove last element. Add/remove elements for list and deque: push front(): Insert element at the front. pop front(): Remove first element. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 16 / 43 Sequence Containers: Other Operations List operations are fast for list, but also available for vector and deque: insert(p, x): Insert an element x at position p. erase(p): Remove an element at position p. clear(): Erase all elements. Miscellaneous Operations: size(): Returns the number of elements. empty(): Returns true if the sequence is empty. resize(int new size): Change size of the sequence. Comparison operators ==, !=, < etc. are also defined. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 17 / 43 Part II STL Iterators: Generalized Pointers Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 18 / 43 Iterators to Traverse a Sequence Container Iterators are generalized pointers. To traverse the elements of a sequence container sequentially, one may use an iterator of the container type. E.g, list::iterator is an iterator for a list of int.
const iterator is the const version of an iterator: the object it ‘points’ to can’t be modified.
STL sequence containers provide the begin() and end() to set an iterator to the beginning and end of a container.
For each kind of STL sequence container, there is an iterator type. E.g.,
􏰢 list::iterator, list::const iterator
􏰢 vector::iterator, vector::const iterator
􏰢 deque::iterator, deque::const iterator
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 19 / 43

Iterators to Traverse a Sequence Container ..
#include
using namespace std;
#include int main() {
/* File: print-list.cpp */
// STL list
// An int STL list
x.push_back(j); // Append items to an STL list
list::const_iterator p; // STL list iterator
for (p = x.begin(); p != x.end(); ++p)
cout << *p << endl; return 0; } list x;
for (int j = 0; j < 5; ++j) Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 20 / 43 Why Are Iterators So Great? template /* File: find-template.h */
Iterator find(Iterator begin, Iterator end, const T& value)
{
while (begin != end && *begin != value)
++begin;
return begin;
}
Iterators allow us to separate algorithms from containers when they are used with templates.
The new find() function template contains no information about the implementation of the container, or how to move the iterator from one element to the next.
The same find() function can be used for any container that provides a suitable iterator.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 21 / 43

Example: find() with a vector Iterator
#include /* File: find-iterator-test.cpp */
using namespace std;
#include
int main() {
const int SIZE = 10; vector x(SIZE);
for (int i = 0; i < x.size(); i++) x[i] = 2 * i; while (true) { cout << "Enter number: "; int num; cin >> num;
vector::iterator position = find(x.begin(), x.end(), num);
if (position == x.end())
cout << "Not found\n"; else if (++position != x.end()) cout << "Found before the item " << *position << '\n'; else cout << "Found as the last element\n"; } } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 22 / 43 Part III STL Algorithms Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 23 / 43 STL Algorithms The STL does not only have container classes and iterators, but also algorithms that work with different containers. STL algorithms are implemented as global functions. E.g., STL algorithm find() searches sequentially through a sequence, and stops when an item matches its 3rd argument. One limitation of find() is that it requires an exact match by value. template /* File: stl-find.cpp */
Iterator find(Iterator first, Iterator last, const T& value)
{
while (first != last && *first != value)
++first;
return first;
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 24 / 43

Example: Using STL find()
#include
using namespace std;
#include
#include #include
int main() {
/* File: find-composer.cpp */
}
list composers;
composers.push_back(“Mozart”);
composers.push_back(“Bach”);
composers.push_back(“Chopin”);
list::iterator p =
find(composers.begin(), composers.end(), “Bach”);
if (p == composers.end())
cout << "Not found." << endl; else if (++p != composers.end()) cout << "Found before: " << *p << endl; else cout << "Found at the end of the list." << endl; return 0; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 25 / 43 Algorithms, Iterators, and Sub-Sequences Sequences/Sub-sequences are specified using iterators that indicate the beginning and the end for an algorithm to work on. The following functions will be used in the following examples. /* File: init.h */ inline int quadratic(int x) { return -x*x + 40*x + 22; } template
void my_initialization(T& x, int num_items)
{
for (int j = 0; j < num_items; ++j) x.push_back( quadratic(j) ); // Can you rewrite using lambda? } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 26 / 43 Example: STL find() the 2nd Occurrence of a Value #include
using namespace std;
#include
#include
#include “init.h”
int main() {
/* File: find-2nd-occurrence.cpp */
} }
const int search_value = 341;
vector x;
my_initialization(x, 100);
vector::iterator p = find(x.begin(), x.end(), search_value);
if (p != x.end()) // Value found for the first time!
{
p = find(++p, x.end(), search_value); // Search again
if (p != x.end())
cout << search_value << "appears after " << *--p << endl; return 0; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 27 / 43 STL find if() template /* File: stl-find-if.cpp */
Iterator find_if(Iterator first, Iterator last, Predicate predicate)
{
while (first != last && !predicate(*first))
++first;
return first;
}
find if() is a more general algorithm than find() in that it stops when a condition is satisfied.
The condition is called a predicate and is implemented by a boolean function.
This allows partial match, or match by keys.
In general, you may pass a function to another function as its
argument!
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 28 / 43

STL find if() — Search by Condition
#include /* File: find-gt350.cpp */
using namespace std;
#include
#include
#include “init.h”
bool greater_than_350(int value) { return value > 350; }
int main() {
vector x;
my_initialization(x, 100);
vector::const_iterator p =
find_if( x.begin(), x.end(), greater_than_350 );
if (p != x.end())
cout << "Found element: " << *p << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 29 / 43 Function Pointer Inherited from C, C++ allows a function to be passed as argument to another function. Actually, we say that we pass the function pointer. E.g., the type of the function pointer of the template larger() we talked before is: inline const T (∗)(const T&, const T&); STL’s max() is the same as our larger(). Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 30 / 43 Function Pointer Example: smaller() and larger() #include /* File: fp-smaller-larger.cpp */
using namespace std;
int larger(int x, int y) { return (x > y) ? x : y; }
int smaller(int x, int y) { return (x > y) ? y : x; }
int main() {
int choice;
cout << "Choice: (1 for larger; others for smaller): "; cin >> choice;
int (*f)(int x, int y) = (choice == 1) ? larger : smaller;
cout << f(3, 5) << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 31 / 43 Function Pointer Example: Calculator #include /* File: fp-calculator.cpp */
using namespace std;
double add(double x, double y) { return x+y; }
double subtract(double x, double y) { return x-y; }
double multiply(double x, double y) { return x*y; }
double divide(double x, double y) { return x/y; } // No error checking
int main() {
double (*f[])(double x, double y) // Array of function pointers
= { add, subtract, multiply, divide };
int operation; double x, y;
cout << "Enter 0:+, 1:-, 2:*, 3:/, then 2 numbers: "; while (cin >> operation >> x >> y)
{
if (operation >= 0 && operation <= 3) cout << f[operation](x, y) << endl; // Call + - * / cout << "Enter 0:+, 1:-, 2:*, 3:/, then 2 numbers: "; } } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 32 / 43 Example: Function Pointer as Lambda #include /* File: fp-min-max-lambda.cpp */
using namespace std;
int main() {
int choice;
cout << "Choice: (1 for my_max; others for my_min): "; cin >> choice;
int (*f)(int, int);
if(choice == 1)
f = [] (int x, int y) { return (x > y) ? x : y; };
else
f = [] (int x, int y) { return (x > y) ? y : x; };
cout << f(3, 5) << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 33 / 43 Function Objects STL function objects are a generalization of function pointers. An object that can be called like a function is called a function object, functoid, or functor. Function pointer and lambdas are just two example of function objects. An object can be called if it supports the operator(). A function object must have at least the operator() overloaded; of course, they may have other member functions/data. Function objects are more powerful than function pointers, since they can have data members and therefore carry around information or internal states. A function object (or a function) that returns a boolean value (of type bool) is called a predicate. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 34 / 43 STL find if() with Function Object Greater Than #include /* File: fo-greater-than.cpp */
using namespace std;
#include
#include
#include “init.h”
#include “fo-greater-than.h”
int main() {
vector x; my_initialization(x, 100);
int limit = 0;
while (cin >> limit)
{
vector::const_iterator p =
find_if(x.begin(), x.end(), Greater_Than(limit)); // Call FO
if (p != x.end())
cout << "Element found: " << *p << endl; else cout << "Element not found!" << endl; } return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 35 / 43 STL find if() with Function Object Greater Than .. class Greater_Than /* File: fo-greater-than.h */ { private: int limit; public: Greater_Than(int a) : limit(a) { } bool operator()(int value) { return value > limit; }
};
The line with Call FO is the same as:
// Create a Greater_Than function object g
Greater_Than g(350);
p = find_if( x.begin(), x.end(), g );
When find if() examines each item, say x[j] in the container vector x, against the temporary Greater Than function object, it will call the FO’s operator() with x[j] as the argument. i.e., g(x[j]) // Or, in formal writing: g.operator()(x[j])
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 36 / 43

STL count if() with Function Object Greater Than
#include /* File: fo-count.cpp */
using namespace std;
#include
#include
#include “fo-greater-than.h”
int main() {
vector x;
for (int j = -5; j < 5; ++j) x.push_back(j*10); // Count how many items are greater than 10 cout << count_if(x.begin(), x.end(), Greater_Than(10)) << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 37 / 43 STL for each() to Sum using Function Object #include
using namespace std;
#include #include
class Sum {
private:
int sum;
/* File: fo-sum.cpp */
public:
Sum() : sum(0) { }
void operator()(int value) { sum += value; }
int result() const { return sum; }
};
int main() {
list x;
for (int j = 0; j < 5; ++j) x.push_back(j); // Initialize x Sum sum = for_each( x.begin(), x.end(), Sum() ); cout << "Sum = " << sum.result() << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 38 / 43 STL Algorithms: for each() and transform() /* File: stl-foreach.h */ template
Function for_each(Iterator first, Iterator last, Function g)
{
for ( ; first != last; ++first )
g(*first);
return g; // Returning the input function!
}
/* File: stl-transform.h */
template
Iterator2 transform(Iterator1 first, Iterator1 last,
Iterator2 result, Function g)
{
for ( ; first != last; ++first, ++result )
*result = g(*first);
return result;
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 39 / 43

STL for each() to Add using Function Object Add
#include #include
#include
class Add {
private:
int data;
/* File: fo-add.h */
public:
Add(int i) : data(i) { }
int operator()(int value) { return value + data; }
};
class Print {
private:
ostream& os;
public:
Print(ostream& s) : os(s) { }
void operator()(int value) { os << value << " "; } }; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 40 / 43 STL for each() to Add using Function Object Add .. #include
using namespace std;
#include “fo-add.h”
int main() {
list x;
for (int j = 0; j < 5; ++j) x.push_back(j); /* File: fo-add10.cpp */ vector y(x.size());
transform( x.begin(), x.end(), y.begin(), Add(10) );
for_each( y.begin(), y.end(), Print(cout) );
cout << endl; return 0; } // Initialize x Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 41 / 43 Other Algorithms in the STL min element and max element equal generate (Replace elements by applying a function object) remove, remove if Remove elements reverse, rotate Rearrange sequence random shuffle binary search sort (using a function object to compare two elements) merge, unique set union, set intersection, set difference Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 42 / 43 That’s all! Any questions? Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 43 / 43