Essential C++ # 03. Generic Programming

C++

Mar 26

Chapter 3. Generic Programming

In this chapter, the word "generic" refers to be independent of both the type of element they are operating on and the type of container within which the elements are held.

3.1. The Arithmetic of Pointers

📌Find specific value in a vector


int* find(const vector<int> &vec, int value)
{
    for (int ix = 0; ix < vec.size(); ++ix)
    {
        if(vec[ix]==value)
        {
            return &vec[ix];
        }
    }
    return 0;
}

📌(Generic Version)Find specific value in a vector


xxxxxxxxxx
template <typename T>
T* find(const vector<T> &vec, const T &value)
{
    for (int ix = 0; ix < vec.size(); ++ix)
    {
        if(vec[ix] == value)
        {
            return &vec[ix];
        }
    }
    return 0;
}

📌The magic and fun fact of pointer

Do you know in C++, an array is also a pointer? This is so much fun. The followings are the same!


xxxxxxxxxx
array[2]
*(array + 2)

If you are a C# programmer, you would say what the heck?? 😨😨

That's because an array is a pointer which records the 1st address of that array. Therefore, they are the same.

📌Find specific value in an array(Normal Version)


xxxxxxxxxx
template <typename T>
T* find(const T *array, int size, const T &value)
{
    // the difference between vector and array is that
    // array(pointer) could not be empty
    // therefore you should check it first
    if(!array || size < 1)
    {
        return 0;
    }
    for (int ix = 0; ix < size; ix++)
    {
        if(array[ix]==value)
        {
            return &array[ix];
        }
    }
    return 0;
}

📌Find specific value in an array(Pointer Version)


xxxxxxxxxx
template <typename T>
T* find(const T *array, int size, const T &value)
{
    if(!array || size < 1)
    {
        return 0;
    }
    // Please take a look here!! The pointer arithmetic!
    // rather shifting the index, here increment the address
    for(int ix = 0; ix < size; ix++, array++)
    {
        // dereference the pointer, so can be compared with value
        if(*array == value)
        {
            return array;
        }
    }
    return 0;
}

//TODO , here 🤔, in Qt, the function declaration should remove const from const T *array. Is it because the new standard of C++?

📌Find specific value in an array(Pointer Version with sentinel)

In this version, we use the address of last element of the array as sentinel¹ address.


xxxxxxxxxx
template <typename T>
T* find( T *first, const T *last, const T &value)
{
    if(!first || !last)
    {
        return 0;
    }
    // here the last address served as sentinel address
    for(; first!=last; first++)
    {
        if(*first == value)
        {
            return first;
        }
    }
    return 0;
}

You can use it as the following:


xxxxxxxxxx
int main()
{
    int arr_int[5] = {1,2,3,4,5};
    int* ptr = find(arr_int,arr_int+5, 3);
    cout << "Integer value: " << endl;
    cout << "ptr: " << ptr 
         << "*ptr: "<< *ptr<< endl;
    
    double arr_double[] = {1.1,2.3,1.6};
    double* ptr_double = find(arr_double, arr_double+3, 1.1);
    cout << "ptr_double: " << ptr_double 
         << "*ptr_double: "<< *ptr_double<< endl;
    
    return 0;
}

📌Behind the vec.begin()

Since a vector could be empty, therefore, it may cause error if we directly query like vec[0]. A safer way would be like this:


xxxxxxxxxx
template <typename T>
inline T* begin(vector<T> &vec)
{
    // check if it is empty
    return vec.empty()? 0 : &vec[0];
}

3.2. Iterators

The iterators here are very similar to the IEnumerable in C#. In short, iterator is a set of classes that are programmed using the same syntax as that of a pointer to collection in STL. For example, the ++ for vector is to query the next element, so as ++ for linked list. But the next address of a linked list cannot be just incremented. Therefore, we can override their operator.


xxxxxxxxxx
// a pseudo code could be like this
for(iter = numbers.begin(); iter!=numbers.end(); iter++)
{

}

📌What is an iterator?

iter is defined to be an iterator for vectors of T elements. It is initialized to address the first element of a vector.


xxxxxxxxxx
vector<int> ivec;
// normal iterator
vector<int>::iterator iter = ivec.begin();
// const iterator(you can loop them but not modify them)
vector<int>::const_iterator cst_iter = ivec.begin();

The double colon :: indicates that iterator is a type nested within the T vector definition.

📌Example Function using iterator

//TODO currently this is compiled with error

The display function can be implemented like so:

T could be saw as the element type of that container.


xxxxxxxxxx
template <typename T>
void display(const vector<T> &vec, ostream &os)
{
    vector<T>::const_iterator iter = vec.begin();
    vector<T>::const_iterator end_it = vec.end();

    for(; iter!=end_it; iter++)
    {
        os << *iter << ' ';
    }
    os << endl;
}

//TODO why in the end return last but not 0?

The find function can be implemented like so:

T could be saw as the iterator type, while S could be saw as the element type.


xxxxxxxxxx
template <typename T, typename S>
S find(T first, T last, const S &value)
{
    for(; first!=last; first++)
    {
        if(*first==value)
        {
            return first;
        }
    }
    return last;
}

You can use 1


xxxxxxxxxx
// arrange data
const int asize = 8;

// array, vector, and linked list
int ia[asize] {1,1,2,3,5,8,13,21};
vector<int> i_vec (ia, ia+asize);
list<int> i_list(ia, ia+asize);

// find in array
int* pia = find(ia, ia+asize, 1024);
if(pia != ia+asize)
{
    cout << "1024 found in ia..." << endl;
}

// find in vector
vector<int>::iterator it;
it = find(i_vec.begin(), ivec.end(), 1024);
if(it != ivec.end())
{
    cout << "1024 found in ivec..." << endl;
}

// find in linked list
list<int>::iterator it_list;
it_list = find(i_list.begin(), i_list.end(), 1024);
if(it_list!=i_list.end())
{
    cout << "1024 found in ilist..." << endl;
}

📌Frequently Used Method

search algorithms: find(), count(), adjacent_find(), find_if(), count_if(), binary_search(), and find_first_of()
sorting and general ordering algorithms: merge(), partial_sort(), partition(), random_shuffle(), reverse(), rotate(), and sort()
copy, deletion, and substitution and algorithms: copy(), remove(), remove_if(), replace(), replace_if(), swap(), and unique()
relational algorithms: equal(), includes(), and mismatch()
generation and mutation algorithms: fill(), for_each(), generate(), and transform()
numeric algorithms: accumulate(), adjacent_difference(), partial_sum(), and inner_product()
set algorithms: set_union() and set_difference()

3.3. Operations Common to All Containers

📌A Function Definition Cover All Common Functions of Containers


xxxxxxxxxx
void compare(vector<int> &vec1, vector<int> &vec2)
{
    // equality
    if(vec1 == vec2) return;

    // isEmpty?
    if(vec1.empty() || vec2.empty()) return;

    // the size
    if(vec1.size() != vec2.size()) return;

    // clear all the data
    vec1.clear();

    // begin and end
    for(auto iter = vec1.begin(); iter!= vec2.end(); iter++)
    {
        cout << "+";
    }

    // insert and erase
    vec1.insert(vec1.begin()+1, 2);
    vec2.erase(vec2.end()-3);
}

3.4. Using the Sequential Containers

📌Initialization of Container

The following are the common ways of initialized the containers.


xxxxxxxxxx
// 1.Create an empty container
list<string> slist;
deque<int> ideque;

// 2.Create a container of some size
list<int> ilist(1024);
vector<double> dvec(32);

// 3.Create a container of a given size specified with initial value
vector<char> chvec(10, 'X');
list<string> slist1(16, "unassigned");
deque<double> dd(10, 3.2);

// 4.Create a container with iterator
bool barr[3] = {true, false, true};
vector<bool> bvec(barr, barr+3);

// 5.Create a container by full copy another
list<string> slist2(slist);

📌Operations supported per container

	`vector`	`list`	`deque`
`front()`	✔	✔	✔
`push_front()`➕	❌	✔	✔
`pop_front()`➖	❌	✔	✔
`[0]` `[1]` `...` `[n-2]` `[n-1]`
`pop_back()`➖	✔	✔	✔
`push_back()`➕	✔	✔	✔
`back()`	✔	✔	✔

📌Different Ways Using insert()

1️⃣the insert() is like: iterator insert(iterator position, elemType value)


xxxxxxxxxx
// arrange
int ival = 6;
int ia[3] = {1, 2, 9};  // make a linked list with contiguous order
list<int> ilist(ia, ia+3);
list<int>::iterator it = ilist.begin();

// loop over the linked list
while(it != ilist.end())
{
    // if a specific value is > such value
    if(*it >= ival)
    {
        // insert
        ilist.insert(it, ival);
        break;
    }
    it++;
}
// if iterator is at the end(a.k.a. no value in the linked list > such value)
// the value should be at the end of linked list
if(it == ilist.end())
{
    ilist.push_back(ival);
}
// display it
for(int ix:ilist )
{
    cout << ix;
}

2️⃣void insert(iterator position, int count, elemType value) inserts "count" elements of value before position.

The following


xxxxxxxxxx
// arrage
list<string> slist(3, string("Hello"));
list<string>::iterator it = slist.begin();

// iterator as the 2nd position
it++;

// insert after that position
slist.insert(it, 5, string("dummy"));

// display
for(auto val : slist)
{
    cout << val << "  ";
}

There are many other overloaded version. Please refer to docs.

📌erase in STL


xxxxxxxxxx
// arrage
list<string> slist(6, string("Hello"));
list<string>::iterator it = slist.begin();
// iterator as the 2nd position
it++;
list<string>::iterator first = slist.begin();
list<string>::iterator last = slist.end();
last--;

// before erase
for(auto v : slist)
{
    cout << v << "  ";
}
cout << endl;

// since I decrement last once
// then erase will be 0 to n-2
slist.erase(first, last);
// after erase
for(auto v : slist)
{
    cout << v << "  ";
}

📌Linked list does not support offset arithmetic


xxxxxxxxxx
list<string> slist(6, string("Hello"));
list<string>::iterator it = slist.begin();

// ERROR
it = it + 2; //failed to offset 2 position
// OK
it++;        //succeed because the ++ has overloaded version

Because the addresses of Linked List are not contiguous! Please refer to my Algorithm Repo.

3.5. Using the Generic Algorithm

📌Prerequisite


xxxxxxxxxx
#include <algorithm>

📌Generic Search Algorithm

Function	Description	Return
`find()`	searches unordered collection	`true` found, `false` not found
`binary_search()`	searches ordered collection, more efficient than `find()`	`true` found, `false` not found
`count()`	count the number of that container	`int` represents the number
`search()`	matches a subsequence, e.g. find `{5,7}` in `{1,3,5,7,2,9}`	the iterator of at the beginning of subsequence if found, the end if not found

📌Implement search element in Fibonacci sequence using generic algorithm


xxxxxxxxxx
#include <algorithm>
// function to grow the vector if element is bigger than current array
extern bool grow_vec(vector<int> &vec, int elem);

// query if an element inside the vector
bool is_elem(vector<int> &vec, int elem)
{
    // find the max value first
    int max_value = max_element(vec.begin(), vec.end());
    // if the query element is outside of max
    if(max_value < elem)
    {
        //grow it
        return grow_vec(vec, elem);
    }
    if(max_value == elem)
    {
        return true;
    }

    // search it 
    return binary_search(vec.begin(), vec.end(), elem);
}

📌binary_seach() only works for sorted container

It is left to the programmer to guarantee the preceding requirement! What if we are not sure?


xxxxxxxxxx
// unsure vector
vector<int> vec;
// duplicate vector with same size
vector<int> vec_copy(vec.size());
// copy from start to end
copy(vec.begin(), vec.end(), vec_copy.begin());
// sort that copy vector
sort(vec_copy.begin(), vec_copy.end());

// query...
int query_num = 13;
bool is_found = binary_search(
    vec_copy.begin(),
    vec_copy.end(),
    query_num);

3.6. Design a Generic Algorithm

📌A filer function

Suppose we have a function to filter out numbers less than 10:


xxxxxxxxxx
vector<int> less_than_10(const vector<int> &vec)
{
    vector<int> nvec;
    for(int ix = 0; ix < vec.size(); ix++)
    {
        if(vec[ix] < 10)
        {
            nvec.push_back(vec[ix]);
        }
    }
    return nvec;
}

It is just a very simple for loop to filter out the vector. But the constraints❌ are:

cannot specify the value for filtering
cannot specify $>$ or $<$

Therefore, we could implement something like this:


xxxxxxxxxx
//  a function compared is bigger
bool is_bigger(int lhs, int rhs)
{
    return lhs > rhs? true : false;
}
//  a function compared is smaller
bool is_smaller(int lhs, int rhs)
{
    return lhs < rhs? true : false;
}

//  filter with some value
//  the last argument is a pointer to function
vector<int> filter_with_value(vector<int> &vec, int value, bool (*flag)(int, int))
{
    vector<int> nvec;
    for(int ix = 0; ix < vec.size(); ix++)
    {
        if(flag(vec[ix], value))
        {
            nvec.push_back(vec[ix]);
        }
    }
    return nvec;
}

// how to use it
void prog_6()
{
    int arr[5] = {12,13,20,100, 5};
    vector<int> ivec(arr, arr+5);
    vector<int> vec_bigger_10 = filter_with_value(ivec, 13, is_bigger);

    for(auto v : vec_bigger_10)
    {
        cout << v << "  ";
    }
}

📌Function Objects

Definition: A function object is an instance of a class that provides an overloaded instance of the function call operator.

Analogy: Delegate in C#, Pointer to Function in C++

Example:

Suppose we have a sequence of numbers:

S_{1} = {s_{1}, s_{2}, \dots, s_{n}}

Do the element wise addition:

S_{1} = {s_{1} + s_{1}, s_{2} + s_{2}, \dots, s_{n} + s_{n}}

Do the element wise multiplication:

S_{1} = {s_{1} * s_{1}, s_{2} * s_{2}, \dots, s_{n} * s_{n}}

Then add to another sequence:

\begin{matrix} S_{1} = {s_{1}, s_{2}, \dots, s_{n}} \\ S_{2} = {s^{1}, s^{2}, \dots, s^{n}} \\ S_{F} = {s^{1} + s_{1}, s^{2} + s_{2}, \dots, s^{n} + s_{n}} \end{matrix}

We can use transform() function to do element-wise operation. It takes 5 arguments:

1️⃣ start of elements range to transform

2️⃣ end of elements range to transform

3️⃣ start position fetching data (iterator points to the beginning of container which fetch data)

4️⃣ start position apply those data (iterator points to the beginning of the container where apply those transformation)

5️⃣ function object (delegate / pointer to function) to apply those changes


xxxxxxxxxx
#include <functional>
void func_obj_example()
{
    int s1[5] = {1, 2, 3, 6, 9};
    int s2[5] = {2, 3, 5, 6, 9};
    vector<int> vec_s1(s1, s1+5);
    vector<int> vec_s2(s2, s2+5);
    vector<int> vec_sf(5);

    transform(vec_s1.begin(),       // 1.
              vec_s1.end(),         // 2.
              vec_s1.begin(),       // 3.
              vec_s1.begin(),       // 4.
              plus<int>());         // 5.

    transform(vec_s1.begin(),       // 1.
              vec_s1.end(),         // 2.
              vec_s1.begin(),       // 3.
              vec_s1.begin(),       // 4.
              multiplies<int>());   // 5.

    transform(vec_s1.begin(),       // 1.
              vec_s1.end(),         // 2.
              vec_s2.begin(),       // 3.
              vec_s1.begin(),       // 4.
              plus<int>());         // 5.
}

📌Function Object Adapter

In short, the function object adapter modifies a function object by specifying lhs/rhs as input. For example,

bind1st binds the 1st operand. bind2nd binds the 2nd operand.


xxxxxxxxxx
vector<int> filter(const vector<int> &vec, int val, less<int> &lt)
{
    vector<int> nvec;
    vector<int>::const_iterator iter = vec.begin();

    // bind2nd(less<int>, val) binds val to the second value of less<int>
    // less<int> now compares each value against val
    while( (iter =
            find_if(iter,
                    vec.end(),
                    bind2nd(lt, val))
            ) != vec.end())
    {
        // each time iter != vec.end(),
        // iter addresses an element less than val
        nvec.push_back(*iter);
        iter++;
    }
    return nvec;
}

📌More General Version

The following is a really excellent example. Please digest!


xxxxxxxxxx
template <typename InputIterator,
          typename OutputIterator,
          typename ElemType,
          typename Comp>
OutputIterator filter (InputIterator first,
                       InputIterator last,
                       OutputIterator at,
                       const ElemType &val,
                       Comp pred)
{
    while( (first = find_if(first, last, bind2nd(pred, val)))
           != last)
    {
        // just to see what is going on ...
        cout << "found value: " << *first << endl;
        // assign value, then advance both iterators
        *at++ = *first++;
    }
    return at;
}

The *at++ = *first++; is just the following:


xxxxxxxxxx
*at = *first;
at++;
first++;

📌A Subdivision method on vector

The following function is kind of similar to C# (where x => x< ???)


xxxxxxxxxx
vector<int> sub_vec(vector<int> &vec, int val)
{
    // clone a vector
    vector<int> nvec(vec);
    // sort it first
    sort(nvec.begin(), nvec.end());

    vector<int>::iterator iter;
    // find the pos marked > val
    iter =  find_if(nvec.begin(), nvec.end(), bind2nd(greater<int>(), val));

    // delete the part
    nvec.erase(iter, nvec.end());

    return nvec;
}

3.7. Using a Map

📌Regular Operation with map

The analogy of map in C++ in C# is Dict< , >.


xxxxxxxxxx
#include <map>
#include <fstream>

// Declare a map with key:string, value:int
map<string, int> words;

// Add a key-value pair:
words["Torso"] = 1;

ifstream infile("./material/serenity_prayer.txt");
if(infile)
{
    // Suppose we want to analyze the word occurence:
    string tword;
    while(infile >> tword)
    {
        words[tword]++;
    }
}

// check the occurence
map<string, int>::iterator iter = words.begin();
for(; iter!=words.end(); iter++)
{
    cout << "key: " << iter->first
        << "value: " << iter->second << endl;
}

Taking into account that the syntax query a key-value pair, first refers to key, second refers to value.

📌Appropriate Way Finding a Value

Suppose you want to find out if a value is in that map, you may do something like this:


xxxxxxxxxx
// NOT APPROPRIATE

map<string, int> words;

if(words["vermeer"])
{
    cout << "Exist." << endl;
}
else
{
    cout << "Not exist." << endl;
}

It can work but it is not appropriate❌. First, words["vermeer"] return some value, if it is 0, then it is false as well. Therefore it could work. But the point is if there is no such key before, using statement like this will add the key-value pair to the map!


xxxxxxxxxx
// APPROPRIATE

map<string, int> words;
string query_word("vermeer");

if(words.count(query_word))
{
    cout << "Found. ";
    cout << "Value: " << words[query_word] << endl;
}
else
{
    cout << "Not found.";
}

The preceding method using map.count() will return the occurrence but it will not add an empty key.✔


xxxxxxxxxx
// APPROPRIATE

map<string, int> words;
map<string, int>::const_iterator iterator;
// Find such word,
// if found=> that iterator
// if not found => the end() iterator
iterator = words.find("vermeer");
if(iterator!=words.end())
{
    cout << "Found.";
    cout << "Value: " << iterator->second << endl;
}
else
{
    cout << "Not found." << endl;
}

The preceding method using map.find() will return the iterator at such position.✔

3.8. Using a Set

You know what set is...

📌Turn a vector to set


xxxxxxxxxx
// init words vector
string words_array[5] = {"Daniel", "Haley", "Daniel", "Bob", "Maria"};
vector<string> words(words_array, words_array+5);
// turn vector to set
set<string> words_set(words.begin(), words.end());

for(auto w : words)
{
    cout << w << " ";
}
cout << endl;
for(auto w: words_set)
{
    cout << w << " ";
}

// OUTPUT
// Daniel Haley Daniel Bob Maria 
// Bob Daniel Haley Maria

📌Insert value to set


xxxxxxxxxx
// arrange
string words_array[5] = {"Daniel", "Haley", "Daniel", "Bob", "Maria"};
vector<string> words(words_array, words_array+5);
string some_words[3] = {"Roma", "Milano", "Torino"};
// init set
set<string> words_set;

// insert range of array
words_set.insert(some_words, some_words+3);
// insert vector
words_set.insert(words.begin(), words.end());
// insert single element
words_set.insert("Fendi");

for(auto w : words_set)
{
    cout << w << " ";
}

// OUTPUT
// Bob Daniel Fendi Haley Maria Milano Roma Torino

📌Iteration over a set


xxxxxxxxxx
// arrange
string words_array[7] = {"Daniel", "Haley", "Daniel", "Bob", "Maria", "Fendi", "Armani"};
set<string> words_set(words_array, words_array+7);
// loop over a set
set<string>::const_iterator iter = words_set.begin();
for(; iter!=words_set.end(); iter++)
{
    cout << *iter << " ";
}

3.9. Iterator Inserters

📌Why should we use iterator inserter?

In short, for saving memory! Preceding methods are good but they must be required with sufficient size of such container(iterator pos). Therefore, here comes "inserter" which does not require specific size of container.

📌Common Iterator Inserters

Parallel to container operation, the inserter works as the following:

Container Operation	Iterator Operation
`push_back()`	`back_inserter()`
`insert()`	`inserter()`
`push_front()`	`front_inserter()`

📌add a range of elements into vector using inserter

I think this is the primary advantage of inserters.


xxxxxxxxxx
// ERROR, you can't push back a range❌
vector<int> ivec{1, 2, 3};
vector<int> ivec2{4, 5, 6};
ivec.push_back(ivec2);

Instead, you can insert range like this:


xxxxxxxxxx
vector<int> ivec{1, 2, 3};
vector<int> ivec2{4, 5, 6};

// OK✔
copy(ivec2.begin(), ivec2.end(), back_inserter(ivec));
for(auto v : ivec)
{
    cout << v << " ";
}

3.10. iostream Iterators

📌Fancy Read something and Output something

We are often required to

1️⃣read something in,

2️⃣sort it,

3️⃣output it.


xxxxxxxxxx
// OLD SCHOOL

string word;
vector<string> texts;

// 1. read in
while(cin >> word)
{
    texts.push_back(word);
}
// 2. sort it
sort(texts.begin(), texts.end());
// 3. output it
for(int ix = 0; ix < texts.size(); ++ix)
{
    cout << texts[ix] << " ";
}

The preceding codes are not quite elegant. Please refer to the following:


xxxxxxxxxx
// NEW SCHOOL cout👍

istream_iterator<string> start(cin);
istream_iterator<string> end;

vector<string> texts;

ostream_iterator<string> os(cout, " ");  // the 2nd argument is the seperator

// 1. read in
copy(start, end, back_inserter(texts));
// 2. sort
sort(texts.begin(), texts.end());
// 3. output it
copy(texts.begin(), texts.end(), os);

The following is to output to a file


x
// NEW SCHOOL ofstream👍
ifstream infile;
ofstream outfile;

infile.open("./moo_cat.txt");
outfile.open("./moo_cat_sorted.txt");

if(!infile || !outfile)
{
    cerr << "Cannot open moo_cat.txt OR moo_cat_sorted.txt" << endl;
    return;
}

istream_iterator<string> start(infile);
istream_iterator<string> end;

vector<string> texts;

ostream_iterator<string> os(outfile, " ");  // the 2nd argument is the seperator

// 1. read in
copy(start, end, back_inserter(texts));
// 2. sort
transform(texts.begin(), texts.end(), texts.begin(), ::tolower);
sort(texts.begin(), texts.end());
// 3. output it
copy(texts.begin(), texts.end(), os);

infile.close();
outfile.close();

1 A sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data)[1] is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in a loop or recursive algorithm. ↩

C++

Xingxin HE