Introduction to C++: Part Twelve

Pair

• A pair combines two values into a single value, which can have different data types, represented by the two public attributes of the pair: first and second.

// Creating a pair - Method 1
pair<int, string> p1(100, "aaa");
pair<int, string> p2(101, "bbb");
// Creating a pair - Method 2 (Recommended)
pair<int, string> p3 = make_pair(102, "ccc");
cout << p3.first << p3.second << endl;

Map/Multimap Containers

• #include<map>
• The characteristic of a map is that all elements are automatically sorted based on their key values. All elements are pairs, with the first element considered the key and the second element the value. A map does not allow two elements to have the same key.
• A map provides read-only iterators; the key values cannot be changed through the map’s iterators, but the values can be modified.
• Like lists, maps are stored in a segmented continuous manner.
• A multimap has the same functionality as a map, with the only difference being that a multimap can have duplicate key values.
• Map Constructors
• map<T1, T2> mapTT;
• map<T1, T2, specified key sorting rule> mapTT;
• map(const map &mp);
• Map Assignment Operations
• map& operator=(const map &mp)
• swap(mp)
• Map Insertion Operations
• insert(…)
• Map Deletion Operations
• clear()
• erase(pos)
• erase(beg, end)
• erase(keyelen)
• Map Lookup Operations
• find(key)
• count(keyelen)
• lower_bound(keyelen)
• upper_bound(keyelen)
• equal_range(keyelen)

map<int, string> m;
m.insert(pair<int, string>(1, "aa"));
m.insert(make_pair(2, "bb"));
m.insert(map<int, string>::value_type(3, "cc"));
m[2] = "dd";
// cout << m[5] << endl;// Note to prevent index out of bounds; accessing a non-existent key in a map will automatically add a corresponding element pair(int, string)(5, 0)

Algorithms

• Header file #include<algorithm>

Function Objects – Functors

• An object combined with () will trigger the call of the overloaded () operator.
• If a class overloads the () operator function, instances of that class are called function objects or functors.
• Unary Function Objects
• One parameter
• Binary Function Objects
• Two parameters
• Multivariate Function Objects
• Multiple parameters

class CA {
int n; // Function objects can have other members
    public:
void operator()(char * str) { // Overload the () operator function
cout << str << endl;
}
}
CA()("aa");

Predicates

• A function or functor that returns a bool type is called a predicate.
• Unary predicates, binary predicates, multivariate predicates

C++ Built-in Function Objects

• Arithmetic Function Objects
• template<class T> T plus<T> Addition
• template<class T> T minus<T> Subtraction
• template<class T> T multiplies<T> Multiplication
• template<class T> T divides<T> Division
• template<class T> T modulus<T> Modulus
• template<class T> T negate<T> Negation
• Relational Function Objects
• template<class T> bool equal_to<T> Equal
• template<class T> bool not_equal_to<T> Not equal
• template<class T> bool greater<T> Greater than
• template<class T> bool greater_equal<T> Greater than or equal
• template<class T> bool less<T> Less than
• template<class T> bool less_equal<T> Less than or equal
• Logical Function Objects
• template<class T> bool logical_and<T> Logical AND
• template<class T> bool logical_or<T> Logical OR
• template<class T> bool logical_not<T> Logical NOT

Adapters

• Provide interfaces for algorithms

Function Object Adapters

• bind2nd
• bind1st

// Step 2: Publicly inherit from binary_function class <Parameter Parameter Return Value>
class Myprint: public binary_function<int, int, void> {
    public:
// Step 3: const modifier for operator() overload function
void operator()(int val, int param) const {
cout << val * tmp << endl;
}
}
vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);
// Step 1: Use bind2nd or bind1st to bind function parameters
for_each(vv.begin(), vv.end(), bind2nd(Myprint(), 100)); // Bind 100 to the second parameter of the overloaded function
// for_each(vv.begin(), vv.end(), bind1st(Myprint(), 100)); // Bind 100 to the first parameter of the overloaded function

Function Pointer Adapters

• Regular functions as adapters
• ptr_fun
• In C++, function names do not represent function addresses (the address is determined by the function name and parameters). You can use ptr_fun to obtain the function address.

void myprintFn(int val, int param) {
cout << val * tmp << endl;
}
vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);
for_each(vv.begin(), vv.end(), bind2nd(ptr_fun(myprintFn), 100));

Member Function as Adapters

• mem_fun_ref

class CA {
    public:
int num;
        CA(){}
        CA(int num) {
            this->num = num;
        }
void fn(int param) {
cout << num * param << endl;
        }
}
vector<CA> vv;
vv.push_back(CA(10));
vv.push_back(CA(20));
vv.push_back(CA(30));

for_each(vv.begin(), vv.end(), bind2nd(mem_fun_ref(&CA::fn), 100));

Negation Adapters

• not1 Unary Negation
• not2 Binary Negation
• C++11 supports lambda expression syntax

vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);

find_if(vv.begin(), vv.end(), bind2nd(greater<int>(), 30)); // Find elements greater than or equal to 30
find_if(vv.begin(), vv.end(), not1(bind2nd(greater<int>(), 30))); // Negation

sort(vv.begin(), vv.end(), greater<int>()); // Sort from largest to smallest
sort(vv.begin(), vv.end(), not2(greater<int>())); // Negation, i.e., sort from smallest to largest; requires two parameters for comparison, hence use binary negation not2
// greater: Greater than predicate function

Lambda Expressions

• C++11 supports lambda expression syntax

vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);

// [] does not write anything, lambda cannot recognize external data
// [=] lambda can read external data
// [&] lambda can write external data
for_each(vv.begin(), vv.end(), [&](int val) {
cout << val << endl;
});

Common Algorithms

• for_each(iterator beg, iterator end, _callback)
• Traversal
• transform(iterator beg1, iterator end1, iterator beg2, _callback)
• Transfer, moving the contents of a container range to another container
• During the transfer, memory for the target container will not be allocated; it must be pre-allocated.

vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);

vector<int> vv2;
vv2.resize(vv.size());

transform(vv.begin(), vv.end(), [=](int val) {
return val + 10;
})

• find(iterator beg, iterator end, value)
• Search, returns the iterator position of the found element
• find_if(iterator beg, iterator end, _callback)
• Search by condition
• adjacent_find(iterator beg, iterator end, _callback)
• Find adjacent duplicate elements
• bool binary_search(iterator beg, iterator end, value)
• Binary search, the container being searched must be sorted
• Returns a bool value, can be used to check if a container contains a certain value
• count(iterator beg, iterator end, value)
• Count occurrences of an element
• count_if(iterator beg, iterator end, _callback)
• Count by condition
• min(int n1, int n2)
• The min function compares two parameters and returns the smaller value

Common Sorting Algorithms

• merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
• Merge algorithm, merges the contents of two containers into a third container
• The merging process will sort; by default, the smaller value moves to the third container first, i.e., ascending order
• sort(iterator beg, iterator end, _callback)
• Sort by condition
• random_shuffle(iterator beg, iterator end)
• Shuffle container order
• Internally shuffled based on random numbers, random numbers must be set in advance
• reverse(iterator beg, iterator end)
• Reverse container order

Common Copy and Replace Algorithms

• copy(iterator beg, iterator end, iterator dest)
• Copy

// Output copied content to terminal iterator
#include<iterator>

vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);
// ostream_iterator terminal output stream iterator ostream_iterator<type>(mode, separator)
copy(vv.begin(), vv.end(), ostream_iterator<int>(cout, " "))

• replace(iterator beg, iterator end, oldvalue, newvalue)
• Replace
• replace_if(iterator beg, iterator end, _callback, newvalue)
• Replace by condition
• swap(container c1, container c2)
• Swap two container elements

Arithmetic Generation Algorithms

• accumulate(iterator beg, iterator end, value)
• Summation algorithm
• fill(iterator beg, iterator end, value)
• Fill

Common Set Algorithms

• set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
• Find intersection, returns the actual content size
• set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
• Find union, returns the actual content size
• set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
• Find difference, returns the actual content size

Common Error Messages

• no match for operator
• No matching overloaded operator found; you may need to define the relevant overloaded operator.