C++: Set Array Using STL

A common initialization or cleanup operation when using arrays is set all its elements to a common value. It is typically done as:

for (int i = 0; i < SIZE; ++i)
    arr[i] = VAL;

The STL algorithm std::fill can be used to achieve the same with a single statement:

#include <algorithm>
std::fill( arr, arr + SIZE, VAL );

Notes from Effective STL

I recently read Effective STL by Scott Meyers. My review of the book can be found here. Below are my notes from the book.

  • One guideline that is missing in the book: Do not extend the STL containers. It is possible, but brings about nothing but misery.
  • Item 1: Choose your containers with care

    The standard sequence containers are: vector, list, deque, string
    The standard associative containers are: set, multiset, map, multimap

    string is typedef of basic_string<char>
    wstring is typedef of basic_string<wchar_t>

    Scott does not mention this, but I find this useful because when you get compilation errors on string, they will mention basic_string<> and not string.

  • Item 2: Beware of the illusion of container-independent code

    This item mentions the most important trick to cut the verbosity of STL: Typedef everything possible.

    For example:

    class Foo;
    typedef std::vector<Foo> FooVec;
    typedef FooVec::iterator FooVecIter;
    
  • Item 4: Call empty() instead of checking size() against zero

    empty() is a constant time operation on all containers. size() can sometimes be a linear time operation on certain containers, like std::list.
  • Item 5: Prefer range member functions to their single element counterparts

    Instead of doing:

    for (int i = 0; i < MAX; ++i)
        vec.push_back(arr[i]);
    

    Try this:

    std::copy( arr, arr, std::back_inserter(vec) );
    

    For an example usage of std::back_inserter see this post.

  • Item 9: Choose carefully among erasing options

    To me, this is STL’s biggest gotcha! std::remove() does not remove elements from the container.

    Use the erase-remove idiom to achieve actual removal:

    fooVec.erase( std::remove(), fooVec.end() );
    
  • Item 14: Use reserve to avoid unnecessary reallocations
  • Item 16: Know how to pass vector and string data to legacy APIs

    if ( !fooVec.empty() )  // This is important!
        someCFunctionCall( &v[0], v.size() );
    
  • Item 18: Avoid using vector<bool>

    It is a pseudo-container with a compressed representation of bools. Avoid using std::vector<bool>, use std::deque<bool> instead. It offers everything that the former does.
  • Item 21: Always have comparison functions return false for equal values
  • Item 23: Consider replacing associative containers with sorted vectors

    If the container is used in a phased manner, first phase only for insertions and the second phase only for lookups, then a sequence container might offer better performance than an associative container.
  • Item 27: Use distance and advance to convert a container’s const_iterator to iterator

    STLContainer v;
    STLContainer::const_iterator ci = SomeFunction();
    STLContainer::iterator i( v.begin() );
    std::advance( i, std::distance<STLContainer::const_iterator>( i, ci ));
    
  • Item 28: Understand how to use a reverse_iterator’s base iterator

    The base() iterator of a reverse_iterator points 1 element in front of the reverse_iterator position. Use with care.
  • Item 29: Consider istreambuf_iterator for character-by-character input

    Useful for unformatted input from files:

    // Read file to string
    std::ifstream iFile("haha.txt");
    std::string fileData( std::istreambuf_iterator<char>( iFile ) ), std::istreambuf_iterator<char>() );
    
  • Item 30: Make sure destination ranges are big enough

    This usually leads to bugs. Instead, whenever possible use one of the inserters: std::inserter, std::back_inserter or std::front_inserter.

    For an example usage of std::back_inserter see this post.
  • Item 31: Know your sorting options

    Ordered by performance, best to worst:
    partition
    stable_partition
    nth_element
    partial_sort
    sort
    stable_sort
  • Item 34: Note which algorithms expect sorted ranges

    These are:
    binary_search
    lower_bound
    upper_bound
    equal_range
    set_union
    set_intersection
    set_difference
    set_symmetric_difference
    merge
    inplace_merge
    includes
  • Item 37: Use accumulate or for_each to summarize ranges
  • Item 39: Make predicates pure functions

    Predicate is a function that returns bool.
    Pure function is a function whose return value depends only on its input parameters. It does not have any side effects.
  • Item 40: Make functor classes adaptable

    Inherit functors from std::unary_function or std::binary_function so that the necessary types are defined nicely for you.

    Defining functors as classes or structs is purely a matter of style. STL uses structs. Some may find it better since there is no need to declare it as public.
  • Item 43: Prefer algorithm calls to hand written loops
  • Item 44: Prefer member functions to algorithms with the same names
  • Item 45: Distinguish among count, find, binary_search, lower_bound, upper_bound and equal_range
  • Item 46: Consider function objects instead of functions as algorithm parameters

    Passing functors is actually faster than passing pointer to a function! 🙂

C++ STL: Find common elements of 2 sorted vectors

Finding the elements common among two sorted vectors and storing the (common) result in a third vector can be done using the std::set_intersection algorithm as follows:

std::set_intersection(	vec0.begin(), vec0.end(),
						vec1.begin(), vec1.end(),
						vec2.begin()	);

Note that std::set_intersection expects the result vector to be of enough size, i.e. of size max( vec0.size(), vec1.size() ). I find this ugly since the result vector needs to be filled with junk elements and its space is wasted depending on the result of the intersection.

Thankfully, STL has std::back_inserter which can handle this situation:

std::set_intersection(	vec0.begin(), vec0.end(),
						vec1.begin(), vec1.end(),
						std::back_inserter( vec2 )	);

The std::back_inserter acts as an iterator to std::set_intersection while it uses std::vector.push_back() to insert each new element given by it. So, the resulting vector does not need to be initialized to an appropriate size and after std::set_intersection it has only the result elements and has exactly that size.

C++ STL: Copy vector to array

The array behaves like a vector and so can be used almost everywhere a vector is used. So, a vector can be copied into an array using std::copy algorithm. But, make sure that the array is big enough to hold the elements of the vector when you do this:

#include <vector>

std::vector<Foo> fooVec;
Foo fooArr[FOO_MAX];

std::copy( fooVec.begin(), fooVec.end(), fooArr );

C++ STL: Output Container to Stream

We can output the elements of any container to any ostream using std::copy like this. But, it would be really nice if we could output any vector like this:

std::vector<MyClass> myVec;
std::cout << myVec;

To achieve that, we just need one more wrapper around std::copy, a function template that accepts vectors of any type:

template <typename T>
std::ostream& operator << (std::ostream& os, const std::vector<T>& vec)
{
    std::copy( vec.begin(), vec.end(), std::ostream_iterator<T>( os ) );
    return os;
}

Similar functions can be written for other STL containers.

C++ STL: Output Container Elements to Stream

The std::copy function (defined in <algorithm>) can be used to easily output elements of any STL container to any ostream. To do this, we can use the std::ostream_iterator (defined in <iterator>). std::ostream_iterator can be passed a ostream object and an optional delimiter string.

For example to output a vector of integers to std::cout:

#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>

std::vector<int> iVec;
// ...
std::copy(iVec.begin(), iVec.end(), std::ostream_iterator<int>( std::cout ));
// ...
std::copy(iVec.begin(), iVec.end(), std::ostream_iterator<int>( std::cout, "\n" )); // One integer per line

C++ STL: Set

One can create and use a STL vector of objects of a class without any extra code. To do the same with a STL set of objects of a class one needs to add a comparison function to the class. This is required because a set keeps its elements sorted.

A bare bones example:

#include <set>

class MyObj
{
    public:
        int _item;
        MyObj::MyObj(int item) : _item(item) {}

        // Comparison
        bool MyObj::operator < (const MyObj& other) const
        {
            return _item < other._item;
        }
};

int main()
{
    std::set<MyObj> mySet;
    mySet.insert(10);
    mySet.insert(7);

    return 0;
}

C++: Initialize STL Vector with Array

A STL vector does not have any constructor that looks like it accepts an array. So, the straightforward way to initialize a vector with an array looks like:

#include <vector>

int arr[ARR_LEN] = { /* Array elements */ };
std::vector iVec;
for (int i = 0; i < ARR_LEN; ++i)
    iVec.push_back( arr[i] );

That is too much code for a simple initialization! Thankfully, there is another way do it with less code.

The constructor vector(InputIterator begin, InputIterator end) which initializes a vector with the elements of the range [begin, end) can be used with arrays too. This is because array pointers have all the properties required of an (input) iterator:

#include <vector>

int arr[ARR_LEN] = { /* Array elements */ };
std::vector<int> iVec(arr, arr + ARR_LEN);

Note that the second argument arr + ARR_LEN is beyond the last element of the array and thus behaves as the correct end().