Programming with the STL

STL concepts

Containers
Iterators
Algorithms

Containers

Manage collections of objects of a certain kind
Sequential containers (vector, list, deque...)
Associative containers (map, set, unordered_map...)

Iterators

Abstraction for stepping through containers
Provide decoupling between containers and algorithms

Algorithm

Act on containers through iterators
Non-modifying sequence operations (find, search, count...)
Modyfing sequence operations (copy, transform, generate...)

Documentation

www.cppreference.com

Update the repo

git push origin functional
git checkout master
git pull upstream master
git push origin master
git checkout -b stl

Sequential container

std::vector
std::array
std::string
std::list
std::forward_list
std::stack
std::deque
std::queue
std::priority_queue

std::vector - access


    #include <vector>
    #include <iostream>

    std::vector<double> v(10, 1.);
    v[2] = 4.5;
    std::cout << v.size() << std::endl;
    std::cout << v[4] << std::endl;

Write a function that prints the elements of a vector, separated by commas

Write a function "print" that prints the elements of a vector, separated by commas


    void print(const std::vector<double>& v)
    {
        for(size_t i = 0; i < v.size(); ++i)
        {
            std::cout << v[i] << ",";
        }
        std::cout << std::endl;
    }

reminder

mkdir build
cd build
cmake ..
make

std::vector - initialization


    std::vector<double> v1;
    std::vector<double> v2(10);
    std::vector<double> v3(10, 2);
    std::vector<double> v4 = { 1., 2., 4., 6., 7. };

std::vector - copy


    std::vector<double> v5(v4);
    std::vector<double> v6 = v4;

Write a function that computes the mean of a vector


    double mean(const std::vector<double>& v)
    {
        double res = 0.;
        for(size_t i = 0; i < v.size(); ++i)
        {
            res += v[i];
        }
        return res / v.size();
    }

std::vector - resizing


    v3.resize(10);
    v4.push_back(2.5);
    v5.clear();

Write a function "extend_vector" such that


    std::vector<double> v = { 1., 2., 3., 4. };
    extend_vector(v);
    print(v);

gives the following output


    1, 2, 3, 4, 2, 4, 6, 8,

Solution 1


    void extend_vector1(std::vector<double>& v)
    {
        size_t size = v.size();
        v.resize(2 * size);
        for(size_t i = 0; i < size; ++i)
        {
            v[i + size] = 2 * v[i];
        }
    }

Solution 2


    void extend_vector2(std::vector<double>& v)
    {
        size_t size = v.size();
        v.reserve(2 * size); // not required, for performance considerations only
        for(size_t i = 0; i < size; ++i)
        {
            v.push_back(2 * v[i]);
        }
    }

Write a function that appends a vector to another one

Solution 1


    void append1(const std::vector<double>& src, std::vector<double>& dst)
    {
        size_t src_size = src.size();
        size_t dst_size = dst.size();
        dst.resize(dst_size + src_size);
        for(size_t i = 0; i < src_size; ++i)
        {
            dst[i + dst_size] = src[i];
        }
    }

Solution 2


    void append2(const std::vector<double>& src, std::vector<double>& dst)
    {
        size_t src_size = src.size();
        dst.reserve(dst.size() + src_size); // For performance only
        for(size_t i = 0; i < src_size; ++i)
        {
            dst.push_back(src[i]);
        }
    }

std::vector - iterators


    std::vector<double> v = { 1., 2., 3., 4., 5. };
    auto iter = v.begin();
    auto iter_end = v.end();
    std::cout << *iter << std::endl;
    ++iter;
    std::cout << *iter << std::endl;
    iter += 2;
    std::cout << *iter << std::endl;
    *iter = 10;
    std::cout << *iter << std::endl;

Rewrite the print functions with iterators


    void print(const std::vector<double>& v)
    {
        for(auto iter = v.begin(); iter != v.end(); ++iter)
        {
            std::cout << *iter << ",";
        }
        std::cout << std::endl;
    }

std::copy


    #include <algorithm>

    std::vector<double> src = { .... };
    std::vector<double> dst(src.size();
    std::copy(src.begin(), src.end(), dst.begin());

Rewrite the append function with iterators

Solution 1


    void append1(const std::vector<double>& src, std::vector<double>& dst)
    {
        size_t dst_size = dst.size();
        dst.resize(dst_size + src.size());
        std::copy(src.begin(), src.end(), dst.begin() + dst_size);
    }

Solution 2


    #include <iterator>

    void append2(const std::vector<double>& src, std::vector<double>& dst)
    {
        dst.reserve(dst.size() + src.size()); // Not required, for performance consideration only
        std::copy(src.begin(), src.end(), std::back_inserter(dst));
    }

ostream_iterator


    void test()
    {
        std::ostream_iterator<double> out_it(std::cout, ", ");
        *out_it = 2;
        ++out_it;
        *out_it = 3;
    }

Rewrite the print function with iterators


    void print(const std::vector<double>& v)
    {
        std::ostream_iterator<double> out_it(std::cout, ", ");
        std::copy(v.begin(), v.end(), out_it); 
        std::cout << std::endl;
    }

std::accumulate


    std::vector<double> v = {1., 2., 3., 4. };
    double res = std::accumulate(v.begin(), v.end(), 4.);
    std::cout << res << std::endl;

Rewrite the mean function with iterators


    double mean(const std::vector<double> v)
    {
        double res = std::accumulate(v.begin(), v.end(), 0.);
        return res / v.size();
    }

Functors


    #include <functional>

    void test()
    {
        std::plus<double> f;
        std::cout << f(1.0, 2.0) << std::endl;
        std::multiplies<double> f2;
        std::cout << f2(1.0, 2.0) << std::endl;
    }


    double mean(const std::vector<double>& v)
    {
        double res = std::accumulate(v.begin(), v.end(), 0., std::plus<double>());
        return res / v.size();
    }

Write a geometric mean function


    #include <cmath>

    double geometric_mean(const std::vector<double>& v)
    {
        double res = std::accumulate(v.begin(), v.end(), 1., std::multiplies<double>());
        return std::pow(res, 1. / v.size());
    }

lambda

Anonymous functor


    auto lambda1 = [](double d1, double d2) { return d1 + d2; }
    auto lambda2 = [](double d1, double d2) -> { return d1 + d2; }

    double res1 = lambda1(1.2, 2.5);
    double res2 = lambda2(1.2, 2.5);

lambda


    double mean(const std::vector<double>& v)
    {
        double res = 0.;
        auto lambda = [](double d1, double d2) { return d1 + d2; };
        double res = std::accumulate(v.begin(), v.end(), 0., lambda);
        return res / v.size();
    }

std::transform


    std::vector<double> v1 = { 1., 2., 3., 4. };
    std::vector<double> v2 = { 1., 2., 3., 4. };
    std::vector<double> res1(v1.size());
    std::vector<double> res2(v1.size());
    
    std::transform(v1.begin(), v1.end(), res1.begin(), std::negate<double>());
    std::transform(v1.begin(), v1.end(), v2.begin(), res2.begin(), std::plus<double>());
    
    std::transform(v1.begin(), v1.end(), res1.begin(), [](double arg) { return -arg; });
    std::transform(v1.begin(), v1.end(), v2.begin(), res2.begin(),
                   [](double arg1, double arg2) { return arg1 + arg2; });

Rewrite the "extend_vector1" function with iterators


    void extend_vector1(std::vector<double>& v)
    {
        size_t size = v.size();
        v.resize(2 * size);
        std::transform(v.begin(), v.begin() + size, v.begin() + size, [](double arg) { return 2 * arg; });
    }

Replace the factor 2 with a function parameter


    void extend_vector1(std::vector<double>& v, double factor)
    {
        size_t size = v.size();
        v.resize(2 * size);
        std::transform(v.begin(), v.begin() + size, v.begin() + size,
                       [](double arg) { return factor * arg; });
    }


    void extend_vector1(std::vector<double>& v, double factor)
    {
        size_t size = v.size();
        v.resize(2 * size);
        std::transform(v.begin(), v.begin() + size, v.begin() + size,
                       [factor](double arg) { return factor * arg; });
    }

lambda capture

[] - captures nothing
[=] - captures all by value
[&] - captures all by reference
[var1] - captures var1 by value
[&var2] - captures var2 by reference
[=,&var2] - captures all by value, but var2 by reference
[var1, &var2]

Dangling reference


    auto get_functor(double factor)
    {
        double factor_twice = 2 * factor;
        auto lambda = [&factor_twice](double arg) { return factor_twice * arg; };
        return lambda;
    }


    void test()
    {
        auto lambda = get_functor(2.5);
        double res = lambda(1.5); // Boom!
    }

Associative containers

map
multi_map
set
multiset
unordered_map
unordered_multimap
unordered_set
unordered_multiset

std::map - access


    #include <map>
    #include <string>
    #include <iostream>

    std::map<std::string, int> m;
    m["a"] = 2;
    std::cout << m.size() << std::endl;
    std::cout << m["a"] << std::endl;
    std::cout << m["b"] << std::endl;
    std::cout << m.size() << std::endl;

std::map - access


    int get_item(const std::map<std::string, int>& m, const std::string& k)
    {
        return m[k];
    }

std::map - iterator


    void print(const std::map<std::string, int>& m)
    {
        for(auto iter = m.begin(); m != m.end(); ++iter)
        {
            std::cout << *iter << ", ";
        }
        std::cout << std::endl;
    }

Write a function that prints the elements of a map


    void print(const std::map<std::string, int>& m)
    {
        for(auto iter = m.begin(); m != m.end(); ++iter)
        {
            std::cout << "(" << (*iter).first << ","
                      << (*iter).second << "), ";
        }
        std::cout << std::endl;
    }


    void print(const std::map<std::string, int>& m)
    {
        for(auto iter = m.begin(); m != m.end(); ++iter)
        {
            std::cout << "(" << iter->first << ","
                      << iter->second << "), ";
        }
        std::cout << std::endl;
    }

std::map - access


    int get_item(const std::map<std::string, int>& m, const std::string& k)
    {
        auto iter = m.find(k);
        // Bad practice, only for illustrating, don't do this at home
        return (iter != m.end()) ? iter->second : -1;
    }