Screenplay: C++: STL Containers (Intro)¶

Pointer Arithmetics Recap ¶

code/10-pointer-arith-basics.cc¶

#include <gtest/gtest.h>


TEST(PointerArithmetics, Basics)
{
    int array[] = {0,1,2,3,4,5,6,7,8,9};
    int* ip = array; // &array[0]

    ASSERT_EQ(*ip, 0);
    ASSERT_EQ(ip[0], 0);

    ASSERT_EQ(*(ip+9), 9);
    ASSERT_EQ(ip[9], 9);

    int* bugp = ip + 10; // one off

    // ASSERT_EQ(*bugp, 10);
    (void)bugp;
}

Discussion

Step width, pointer increment
No range checks: performance
Note how valgrind does not say invalid write, but conditional jump depends on uninitialized …
C++03 slides, 105ff.

Next: “copy” algorithm

start without const
const on begin, end; fix copy() prototype

code/11-pointer-arith-ranges.cc¶

#include <gtest/gtest.h>


static void copy(const int* begin, const int* end, int* destination)
{
    while (begin != end) {
        *destination = *begin;
        ++begin;
        ++destination;
    }
}

TEST(PointerArithmetics, Ranges)
{
    int array[] = {0,1,2,3,4,5,6,7,8,9};
    size_t num_elements = sizeof(array)/sizeof(int);

    const int* begin = array;
    const int* end = array + num_elements;

    int another_array[10];
    copy(begin, end, another_array);
    ASSERT_EQ(another_array[0], array[0]);
    ASSERT_EQ(another_array[9], array[9]);

    int yet_another_array[3];
    copy(begin, begin+3, yet_another_array);
    ASSERT_EQ(yet_another_array[0], array[0]);
    ASSERT_EQ(yet_another_array[2], array[2]);
}

Discussion

[begin, end)
emphasize `const a lot
copy(): algorithm
C++03 slides, 108ff.

Container: `std::vector`¶

Steps

slowly morph C program from above
C++03: separate step
C++11: separate step

code/20-vector.cc¶

#include <gtest/gtest.h>

#include <vector>


TEST(Vector, Basics_CXX03)
{
    std::vector<int> array;
    for (int i=0; i<10; i++)
        array.push_back(i);

    // int* ip = &array[0]; // works
    // int* ip = array.begin(); // error
    // std::vector<int>::iterator ip = array.begin();
    std::vector<int>::const_iterator ip = array.begin();

    ASSERT_EQ(*ip, 0);
    ASSERT_EQ(ip[0], 0);

    ASSERT_EQ(*(ip+9), 9);
    ASSERT_EQ(ip[9], 9);
}

TEST(Vector, Basics_CXX11)
{
    std::vector<int> array{0,1,2,3,4,5,6,7,8,9};
    auto ip = array.cbegin();

    ASSERT_EQ(*ip, 0);
    ASSERT_EQ(ip[0], 0);

    ASSERT_EQ(*(ip+9), 9);
    ASSERT_EQ(ip[9], 9);
}

Discussion

brace initialization (see more in C++11 slides, "Brace Initialization".
note how iterator feels like a pointer
- index operator []
- increment

Algorithm: `std::vector` and Naive Copy ¶

Steps

start out with function copy() from C pointer arith above
WTF does the compiler not choose my copy, but rather complains about something from std? do they have a namespace leak somewhere?
rename to my_copy()
see how we end up with two versions of my_copy()
- different prototypes, but identical body

code/25-vector-naive-copy.cc¶

#include <gtest/gtest.h>

#include <vector>


static void my_copy(
    std::vector<int>::const_iterator begin,
    std::vector<int>::const_iterator end,
    std::vector<int>::iterator destination)
{
    while (begin != end) {
        *destination = *begin;
        ++begin;
        ++destination;
    }
}

static void my_copy(
    std::vector<int>::const_iterator begin,
    std::vector<int>::const_iterator end,
    int* destination)
{
    while (begin != end) {
        *destination = *begin;
        ++begin;
        ++destination;
    }
}

TEST(Vector, NaiveCopy)
{
    std::vector<int> array{0,1,2,3,4,5,6,7,8,9};
    auto begin = array.cbegin();
    auto end = array.cend();

    int another_array[10];
    my_copy(begin, end, another_array);
    ASSERT_EQ(another_array[0], array[0]);
    ASSERT_EQ(another_array[9], array[9]);

    std::vector<int> yet_another_array(3);
    my_copy(begin, begin+3, yet_another_array.begin());
    ASSERT_EQ(yet_another_array[0], array[0]);
    ASSERT_EQ(yet_another_array[2], array[2]);
}

Discussion

this cannot be the positive side
enter std::copy<>

Algorithm: `std::vector` and `std::copy<>`¶

Steps

again, morph from previous my_copy

code/26-vector-algo-copy.cc¶

#include <gtest/gtest.h>

#include <vector>
#include <algorithm>


TEST(Vector, AlgoCopy)
{
    std::vector<int> array{0,1,2,3,4,5,6,7,8,9};

    int another_array[10];
    std::copy(array.cbegin(), array.cend(), another_array);
    ASSERT_EQ(another_array[0], array[0]);
    ASSERT_EQ(another_array[9], array[9]);

    int yet_another_array[3];
    std::copy(array.cbegin(), array.cbegin()+3, yet_another_array);
    ASSERT_EQ(yet_another_array[0], array[0]);
    ASSERT_EQ(yet_another_array[2], array[2]);
}

TEST(Vector, BackInsert)
{
    std::vector<int> array{0,1,2,3,4,5,6,7,8,9};
    std::vector<int> another_array; // empty
    // std::copy(array.cbegin(), array.cbegin()+3, another_array); // bug
    std::copy(array.cbegin(), array.cend(),
              std::back_insert_iterator<std::vector<int>>(another_array));
    ASSERT_EQ(another_array[0], array[0]);
    ASSERT_EQ(another_array[9], array[9]);
}

Discussion

std::copy works like my_copy: no range checks, nothing special

Container: `std::list`¶

Steps

Nah, these are trivial. Show vector pendants
erase is difficult.
- show naive variant first; valgrind will complain.
- check doc of erase. return value is what we need.

code/25-list.cc¶

#include <gtest/gtest.h>

#include <list>
#include <algorithm>


TEST(List, Append)
{
    std::list<int> l;
    l.push_back(42);
    l.push_back(7);
    l.push_back(666);

    ASSERT_EQ(l.size(), 3);
}

TEST(List, Insert)
{
    std::list<int> l{42, 7, 666}; // C++11

    // insert 667 before 666 ...

    // find position where to insert
    auto position = std::find(l.begin(), l.end(), 666);
    ASSERT_NE(position, l.end());

    // insert at (i.e. before) position
    auto inserted = l.insert(position, 667);
    ASSERT_NE(inserted, l.end());
    ASSERT_EQ(l.size(), 4);
}

TEST(List, Erase)
{
    std::list<int> l;
    l.push_back(42);
    l.push_back(7);
    l.push_back(666);
    l.push_back(7);

    // erase elements with value 7

#if 0 // naive variant; ask valgrind
    for (auto it=l.begin(); it!=l.end(); it++) {
        if (*it == 7)
            l.erase(it);
    }
#endif

    auto it = l.begin();
    while (it != l.end()) {
        if (*it == 7)
            it = l.erase(it);
        else
            it++;
    }

    ASSERT_EQ(l.size(), 2);
}

Container: `std::map`¶

code/30-map.cc¶

#include <gtest/gtest.h>

#include <map>
#include <string>


TEST(Map, InsertFind)
{
    std::map<int, std::string> m;
    m.insert(std::make_pair(666, "666"));
    m.insert(std::make_pair(42, "42"));

    auto found = m.find(666);
    ASSERT_NE(found, m.end());
    ASSERT_EQ(found->first, 666);
    ASSERT_EQ(found->second, "666");
}

TEST(Map, EraseByPosition)
{
    std::map<int, std::string> m{{666, "666"}, {42, "42"}}; // C++11

    // find element
    auto found = m.find(666);
    ASSERT_NE(found, m.end());

    // remove by position
    m.erase(found);

    ASSERT_EQ(m.find(666), m.end()); // verify not in map
}

TEST(Map, EraseByKey)
{
    std::map<int, std::string> m{{666, "666"}, {42, "42"}}; // C++11

    // find element
    auto found = m.find(666);
    ASSERT_NE(found, m.end());

    // remove by position
    m.erase(found);

    ASSERT_EQ(m.find(666), m.end()); // verify not in map
}

Screenplay: C++: STL Containers (Intro)¶

Pointer Arithmetics Recap¶

Container: std::vector¶

Algorithm: std::vector and Naive Copy¶

Algorithm: std::vector and std::copy<>¶

Container: std::list¶

Container: std::map¶

Pointer Arithmetics Recap ¶

Container: `std::vector`¶

Algorithm: `std::vector` and Naive Copy ¶

Algorithm: `std::vector` and `std::copy<>`¶

Container: `std::list`¶

Container: `std::map`¶