C++ STL

Table of content

• 1. Using STL in a source
• 2. STL: Structures and Algorithms
  • Vector
  • accumulate()
  • fill() and copy()
  • for_each(): traverse a container applying a function to every element
  • Transform: apply a function to every member and store the result into a sequence
  • auto_ptr<typename T> x smart_ptr
• 3. Input/Output: streams, string stream for easy conversions string <> whatever
• 4. Boost Libraries
  • smart_ptr - smart pointers to automaticaly destroy dynamic objects
  • The Lambda Library - create an unnamed function ad-hoc

1. Using STL in a source

1. "using namespace std;" must be somewhere at the beginning of your source file
2. #include all the headers you will need, e.g. "#include <vector>. Without the previous namespace it will not work.

2. STL: Structures and Algorithms

using namespace std;
#include <vector>                 // vector
#include <algorithm>        // sort, max_element 
#include <queue>                 // priority queue
#include <iostream>        // cout, cin - input/output streams

class HeurItem: public Item {
public:
  double ratio;
  int id;
  HeurItem(int id, Item&);
};//HeurItem

/** Needed for sorting
 *  Criterium: the biggest rate cost/weight the better
 */
struct OptimalityCriterium {  
  // return true, if the 1st param shall be placed before the 2nd one
  bool operator()(const HeurItem& a, const HeurItem& b) {
    return a.ratio > b.ratio;
  }
};//OptimalityCriterium

// ------------------------------------------------------------------- STL "vector" of 'Item'
typedef vector<HeurItem> TItem_vect;

KnapsackProblem::KnapsackProblem(int task_id, int nr_items, int max_load, Item **items){
   ...
  // The Vector
  TItem_vect item_vect;
  //  1. Init the vector: insert items
  for(int i=0; i < nr_items; i++){
    item_vect.push_back( *(new HeurItem(i, *(items[i]))));
  }// items -> item_vect

  //  2. Sort the items --------------------------------------------- STL "sort" algorithm
  sort(item_vect.begin(), item_vect.end(), OptimalityCriterium() );
} // constructor

class QueueElement{
public:
  unsigned penalty;

 // Needed for the priority queue; the higher penalty the worse it is
 // the prority queue uses this operator to order its elements
bool operator<( const QueueElement &e) const { return this->penalty > e.penalty; };

// Print QueueElement to a stream. Now we can type: cout << myQueueElement;
friend ostream& operator<<(ostream& out, const QueueElement &e){
  out<< "{p:"<< e.penalty << "}";
  return out;
}//print

};//QueueElement


// A priority queue ----------------------------------------------------- STL "priority_queue" data structure
priority_queue< QueueElement > p_queue;
...
p_queue.push( *(new QueueElement( 0 )));// Penalty == 0
QueueElement *best_state = new QueueElement( p_queue.top() );        // READ the 1st element of the queue
p_queue.pop();                                                        // REMOVE the 1st element
while ( !(p_queue.empty()) ) { ... }

// ----------------------------------------------------------------------- STL "max_element" algorithm
unsigned myarray[10];
unsigned *max_el = max_element(myarray, myarray + 10);
assert(maxp != full_buckets + 10);        // this is true when no such element is found

Vector

Array to vector and vice versa: 

#include <vector>        // needed for accumulate
using namespace std;

int array[]= {1,2,3,4};
//Parameters: ptr.to 1st and after last elm.
vector<int> vect (array+0, array+4);

//Vector to an array:
arr = new int [vect.size()];
copy( vect.begin(), vect.end(), arr);

Print a vector: see fill() and copy() below, replace "bestcosts" by vect.begin() and "bestcosts + SIZE" by vect.end(), "ostream_iterator<int>" by ostream_iterator<vector::value_type>.

accumulate()

This function is applied to a sequence of elements, e.g. an array or a vector, and "accumulates" the elements.

• Parameters:
  1. iterator.begin is an iterator pointing to the beginning of the sequence
  2. iterator.end is an iterator pointing just behind the last element of the sequence
  3. init_value of the type result_type is the initial value of the result
  4. bin_op() is a functional object that may be applied to ( init_value, iterator.begin), i.e. it takes ( result_type, element's type) and returns result_type value 
• Return: bin_op(  bin_op( ... bin_op( init_value, iterator.begin ),  ...), iterator.end - 1) 

result_type accumulate ( iterator.begin, iterator.end, init_value, bin_op() )

#include <numeric>        // needed for accumulate
using namespace std;

class Item{
public:
  int weight;
  Item(int w){weight = w;};
};

//result must be of the same type as the 2nd argument- for accumulate
struct add {
  int operator() ( const int old_sum, const Item *item) const
    { return item->weight + old_sum; }
};

int main(int argc, char* argv[])
{
  Item **items = new Item*[3];
  for (int i=0;i<3;++i) items[i] = new Item(i);
  int sum = accumulate (items, items + 3, 0, add() );
  return sum;
}

fill() and copy()

#include <algorithm> // fill, copy
#include <iterator>  // ostream_iterator
#include <iostream>  // cout

// COPY to cout ----------------------------
int SIZE        = 100;
int bestcosts[SIZE];
...        /* fill the aray */

// Print array to stdout (cout), separate elements by a space
// Equals to for(int i=0;i<SIZE;i++) cout << bestcosts[i]<<" ";
copy (bestcosts, bestcosts + SIZE,
        ostream_iterator<int> (cout, " ")); 

// FILL array by 0s
fill( bestcosts, bestcosts + SIZE, 0 );

for_each() - non-modifying sequence operation

for_each() traverses a sequence, applying a function to every of its elements. The function may not modify them and its return value is ignored.

Suppose you have a list of Widgets and you want to call it's member function redraw() for each of them. You could do it in a loop:

list<Widget> wlist;
...
for (list<Widget>::iterator i = 
wlist.begin();
i != wlist.end(); ++i) {
i->redraw();
}

But you could also do it with the for_each algorithm:

list<Widget> wlist;
...

for_each( wlist.begin(), wlist.end(),
   mem_fun_ref(&Widget::redraw) );

Or you could define a functor to do this:

list<Widget> wlist;
struct doRedraw {
  void operator()(const Widget &w) { w.redraw(); } 
};
...

for_each( wlist.begin(), wlist.end(),
   doRedraw() );

list<Widget> wlist;
void doRedraw (Widget &w) { w.redraw(); }
...

for_each( wlist.begin(), wlist.end(),
   doRedraw );

/** Call for_each with first = begin, last = end. */

template <class Sequence, class UnaryFunction>
UnaryFunction forAll( Sequence &sequence, 
                      UnaryFunction function )
{
   for_each(sequence.begin(), sequence.end(), function);
   return function;
} // forAll
        ...
forAll( wlist, doRedraw );

transform() - modifying sequence operation

Transform iterates through a sequence <first,last), applies unary_op (binary_op) to each member and the results stores to the output sequence's iterator result, which may be equal to first.. There're two versions:

OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction unary_op);

OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op);

transform(a.begin(), a.end(), ostream_iterator<int>(cout),
          bind1st(plus<int>(), 1));

Explanation: bind1st sets a first argument of a binary function, plus computes addition, 1 is added to every member and it's printed. Se below how to simplify this with the lambda library.

auto_ptr<typename T>

IMPORTANT: it's recommended not to use auto_ptr because it's quality isn't very high. smart_ptr from <boost> shall be prefered. By: a Renault C++ developer.

Auto_ptr is a smart pointer; it means that you never have to free it manually (you never apply delete on it) - the object pointed by it is deleted automatically in the end of the pointer's lifetime. Example: const auto_ptr<myClass> ptr = new String; Summary:

• only one auto_ptr is allowed to point to an object; if you copy it (new_ptr = old_ptr), the old pointer is set to NULL
• object pointed by auto_ptr is deleted automatically and the pointer is set to NULL
• declared in <memory>
• WARNING: be aware auto_ptr behaves differently from a normal pointer (for if you copy it, you change it) and there are cases when you can't use it. For example never use a vector<> of auto_ptr and be careful with passing it as a function parameter ( myfunc(my_auto_ptr) makes a copy of the pointer thus invalidating the original one!) See this article (search for "Beware"; 2002AD). It's a good idea to declare it constsnt whenever you can.

Some methods (not checked)

• get() returns ? the address of the pointed object (which != auto_ptr because auto_ptr is a class?)
• reset(T*) sets auto_ptr to a new object, deleting the old one
• T* release() returns a normal pointer to the pointed object and sets auto_ptr to NULL

3. Input/Output: streams

File i/o

using namespace std;
#include <iomanip>        // setw() and setiosflags(ios::left)
#include <iostream>        // cout
#include <fstream>        // file stuff
// PRINT to the standard output (screen). Four characters of variable2 will
//  be printed aligned to the left.
cout << variable1 << " "<< setw(4) << setiosflags(ios::left)<< variable2;

//  ---------------------------------- FILE

 ifstream file;        // input file
file.open( "myfile.txt" );
if (! file.is_open() ) exit(1);
  // --- TRY to read the file ---
  // Read the 1st line: task_id nr_items max_load 
  file >> task_id >> nr_items >> max_load;
  // Test for .eof must be here after we tried to read, because
  // it returns true after the last read has failed.
  if( file.eof() ) return false;
file.close();

Standard i/o

Define how to print a class: operator<<

class Item { 
public: 
  int myID;
  friend ostream& operator<<(ostream& out, const Item &item)
  {
    out << "Item "<< item.myID;
    return out;
  }//print
};

String stream - conversions from/to string made easy

The class stringstream from the library sstream can be used as any other stream, only it operates on strings instead of files.

#include <sstream>
stringstream s;
s << "whatever" << 12.5 << myInetAddress;
string result = s.str(); // char* result = s.str().c_str();

4. Boost Libraries

Boost is a great C++ library.

The Smart Pointer (smart_ptr)

To use Boost::smart_ptr you don't need to install the library, it suffices to get boost/include/*.hpp including smart_ptr.hpp and more, put them into a directory (e.g. /example/boost/) and compile your program: g++ -I/example ... .

There are actually more versions of the smart_ptr one of whose is shared_ptr:

#include <boost/shared_ptr.hpp>
using namespace boost;

/** Do-nothing deleter for shared_ptr to a static object*/
struct null_deleter
{
    void operator()(void const *) const {}
};

...
const Job aStaticInstanceOfJob;
/** Pointer to an object that shall not be deleted (e.g. because it's static) and is const. */
shared_ptr<const Job> aJobPtr( &(aStaticInstanceOfJob) ),
   null_deleter());            // The pointed object 1)cannot be changed
                               // 2)won't be deleted when aJobPtr is destroyed
shared_ptr<State> statePtr;
statePtr.reset( new State() ); // set it to point to an object [and perhaps get rid of the 1 pointed before]

The Boost Lambda Library (BLL, see www)

This library let you create an unnamed function ad-hoc. Three formal parameters are predefined: _1, _2, _3.

Important notes on usage

• Use the namespace boost::lambda.
• g++ >= 3.0 is required to compile programs using lambda.
• All of this library is in the header files, you don't need to compile libboost.

Examples and info

for_each(a.begin(), a.end(), cout << (1 + _1));

Explanation: we've defined here an unnamed function whose body is cout << (1 + _1) where _1 refers to the first argument - the iterator. The value of every object in a +1 is printed.

BLL manuals reads (section 4.1):

Note that a normal (non-lambda) expression as subexpression of a lambda expression is evaluated immediately. This may cause surprises. For instance, if the previous example is rewritten as
for_each(vp.begin(), vp.end(), cout << '\n' << *_1);
the subexpression cout << '\n' is evaluated immediately and the effect is to output a single line break, followed by the elements of vp.

The BLL provides functions constant and var to turn constants and, respectively, variables into lambda expressions, and can be used to prevent the immediate evaluation of subexpressions: for_each(vp.begin(), vp.end(), cout << constant('\n') << *_1); See sec. 5.5.

int index = 0;
for_each(a.begin(), a.end(), (cout << ++var(index) << ':' << _1 << '\n', cout << ' '));

Explanation: prints "1:first member\n, 2:second member, ...". var() is needed so that ++index won't be evaluated only once. Notice the syntax of a more complex lambda function (a bit artificial in this case): the statements are enclosed by () and separated by commas.

Control structure

if_then(condition, then_part) 
if_then_else(condition, then_part, else_part)   // equals to: condition ? then_part : else_part
if_then_else_return(condition, then_part, else_part) 
while_loop(condition, body) 
while_loop(condition) // no body case 
do_while_loop(condition, body) 
do_while_loop(condition) // no body case 
for_loop(init, condition, increment, body) for_loop(init, condition, increment) // no body case 
switch_statement(...)

An alternative syntax:

if_(condition)[then_part]
if_(condition)[then_part].else_[else_part]
while_(condition)[body]
do_[body].while_(condition)
for_(init, condition, increment)[body]

More stuff

switch statement, exceptions, new & delete, ...

Header files

lambda/lambda.hpp, lambda/bind.hpp, lambda/if.hpp, lambda/loops.hpp, lambda/switch.hpp, lambda/construct.hpp, lambda/casts.hpp, lambda/exceptions.hpp, lambda/algorithm.hpp and lambda/numeric.hpp

Additionally, the library depends on two other Boost Libraries, the Tuple [tuple] and the type_traits [type_traits] libraries, and on the boost/ref.hpp header.

Lambda vs. shared_ptr

Nowadays (Nov 2004) there're problems using shared_ptr in a lambda expression see a description.

find_if( vector.begin(), vector.end(), ( _1->aMethodOfMyObj() ) ) where the vector contains shared_ptr<MyObj> =>

> The compiler throws the error:
> --> error: base operand of `->' has non-pointer type `const
> boost::lambda::lambda_functor<boost::lambda::placeholder<1> >'

You cannot use boost::bind (boost/bind.hpp) for lambda to bind _1 (*_1) to aMethodOfMyObj, you need boost::lambda::bind (boost/lambda/bind.hpp), but this one is a bit different from the boost::bind and doesn't support shared_ptr yet, you need to patch the library (see the description).