Boost is a large collection of C++ libraries that are
Boost is closely connected with the C++ standardisation process:
We take a brief tour of some of the more useful Boost libraries.
A smart pointer is a pointer that owns the object it points to and is responsible for deleting it.
A problematic issue with smart pointers is what happens to ownership in copy operation. There are at least the following alternatives:
In Boost there are no deep-copy smart pointers but the other options are available:
Boost also provides:
shared_ptr should be the default smart pointer.
Safe to use almost anywhere.
Can be created from:
Never create a smart pointer (of any type except intrusive_ptr) from a "used" raw pointer.
// preferred way to set up shared_ptr<int> sp (new int); sp.reset(new int); // DON'T DO THIS! // This creates two distinct reference counters // and the object will be deleted twice: int* q = new int; shared_ptr<int> sq1(q); shared_ptr<int> sq2(q);
Boost smart pointer documentation and TR1 smart pointer proposal provide more information.
Boost has a collection utilities for helping to write standard-conforming iterators:
// fill vector with 1 2 3 4 5 std::vector<int> numbers; typedef std::vector<int>::iterator n_iter; std::copy(boost::counting_iterator<int>(1), boost::counting_iterator<int>(6), std::back_inserter(numbers)); // fill another vector with iterators to the first std::vector<std::vector<int>::iterator> pointers; std::copy(boost::make_counting_iterator(numbers.begin()), boost::make_counting_iterator(numbers.end()), std::back_inserter(pointers));
indirect_iterator
- Iterator to a container of pointers or iterators that behaves as if an iterator to the pointed to objects.
// print indirect contents std::copy(boost::make_indirect_iterator(pointers.begin()), boost::make_indirect_iterator(pointers.end()), std::ostream_iterator<int>(std::cout, " ")); // outputs 1 2 3 4 5filter_iterator
function_output_iterator
permutation_iterator
transform_iterator
reverse_iterator (improved from standard)
shared_container_iterator
zip_iterator
See Boost Iterator Library documentation for more adaptors and further details.
TR1 contains a flexible functor adaptor bind. Boost has two independent implementations of it, boost::bind and boost::lambda.
Here is what bind does:
bind(functor, arg1, arg2, ...)
The result (return value) is a functor.
functor can be
arg1, arg2, ... can be
place holders _1, _2, etc. that represent the arguments of the resulting functor
// make greater<int> by swapping arguments of less<int> bind (less<int>(), _2, _1);
value
int x = 5; bind (less<int>(), _1, x); // is equivalent to bind (less<int>(), _1, 5);
reference
bind (less<size_t>(), _1, ref(x)); // now changing the value of x affects the functor
bind expression
// unary predicate that returns true if the argument is
// a person whose shoe size is smaller the age
bind (less<int>(),
bind(&person::shoe_size, _1)
bind(&person::age, _1)
);
The bind expressions can grow very complicated. boost::bind overloads some operators to simplify the definition of functors. For example, the above unary functor comparing shoe size and age can also be expressed as
bind(&person::shoe_size, _1) < bind(&person::age, _1);
boost::lambda takes this expression template technique to an extreme.
Almost all operators are overloaded.
bind is not needed at all when there are only operators.
vector<int*> v; // ... for_each (v.begin(), v.end(), cout << *_1 + 50 << '\n');
bind is still needed for named functors
Boost::regex is an implementation of the TR1 regular expressions.
string card_number;
// ...
regex card_number_format ("(\\d{4}[- ]){3}(\\d{4})");
bool is_valid = regex_match (card_number, card_number_format);
There are two basic algorithms:
The string can be given as
string
C-string
iterator range
regex_match (begin, end, expression);
There are two optional arguments:
regex_match (string, match_result, expression, flags);
There are also
regex_iterator ri (begin, end, expression);
regex_replace (result, begin, end, expression, format);
More information can be found in boost::regex documentation and TR1 regex proposal
TR1 and Boost define a tuple as a generalization of standard pair.
tuple<int, float, string> t(1, 3.5, string("Hello"));
Tuples can be created with make_tuple.
t = make_tuple(2, 0.78, string("there"));
Conversions between elements work.
t = make_tuple('a', 5, "world!");
tie is convenient for unpacking a tuple
int n; float x; string s; tie(n, x, s) = t; // is equivalent to make_tuple(ref(n), ref(x), ref(s)) = t;
This is useful for returning multiple values from an algorithm.
iterator result_begin, result_end; tie(result_begin, result_end) = equal_range (begin, end, value);
An element can be accessed with get.
int m = get<0>(t); float y = get<1>(t); string r = get<2>(t);
Tuples also support
More information in Boost tuple documentation and in TR1 tuple proposal.
Probably the largest library in Boost is the Boost Graph Library (BGL). It provides:
BGL algorithms take the graph type as a template argument. The graph type can be
The graph type Graph has to model graph concepts.
Basic features include:
Associated types are defined by graph traits
graph_traits<Graph>::vertex_descriptor graph_traits<Graph>::edge_descriptor graph_traits<Graph>::vertex_iterator graph_traits<Graph>::out_edge_iterator ...
Vertex and edge descriptors are unique identifiers of vertices and edges.
Functions for basic operations and access.
Graph g; edge_descriptor e; vertex_descriptor u, v; u = add_vertex(g); v = add_vertex(g); e = add_edge(u, v, g); assert(u == source(e, g) && v == target(e, g));
Vertex and edge iterators.
vertex_iterator vbegin, vend;
tie(vbegin, vend) = vertices(g);
for (vertex_iterator i = vbegin; i != vend; ++i) {
out_edge_iterator ebegin, eend;
tie(ebegin, eend) = out_edges(v, g);
for_each (ebegin, eend, do_something());
}
Vertex and edge properties are accessed with property maps.
name_map[u] = "u"; put(name_map, v, "v"); // ... float & we = weight_map[e]; we = 3.5; // ... edge_iterator i, eend; for (tie(i,eend) = edges(g); i != eend; ++i) { cout << "weight(" << name_map[source(*i,g)] << ',' << name_map[target(*i,g)] << ") = " << get(weight_map, *i) << '\n'; }
- Underlying implementation may vary. For example,
- vector (descriptor is an integer)
- member value (descriptor is a pointer)
- member of vector element
- boolean property could be a (sign) bit in another value
- Interior properties are properties of the graph.
property_map<Graph, edge_weight_t>::type weight_map = get(edge_weight, g); put(weight_map, e, 3.5); // is the same as put(edge_weight_t, g, e, 3.5);
- Exterior property maps can be created as needed.
- Property maps are common arguments to algorithms.
Algorithm visitors allow customization of algorithm behaviour.
depth_first_search (g, visitor);
Visitors have a number of member functions that are called at certain event points during algorithm execution.
struct dfs_printer
: default_dfs_visitor // inherit (empty) member functions
{
void discover_vertex (vertex_descriptor u, const Graph& g) const {
cout << get(name_map, u) << ' ';
}
}
// ...
depth_first_search(g, visitor(dfs_printer()));
Many algorithms have a large number of parameters, many of which have a default value.
dijkstra_shortest_paths (g, s, predecessor_map, distance_map
weight_map, vertex_index_map,
dist_compare, dist_combine,
dist_inf, dist_zero,
visitor, color_map);
Named parameters allow flexible overriding of defaults.
struct my_visitor;
vector<vertex_descriptor> pred (num_vertices(g));
vector<int> dist (num_vertices(g));
dijkstra_shortest_paths ( g, s, visitor(my_visitor).
distance_map(&dist[0]).
predecessor_map(&pred[0]));
Many basic algorithms:
Perhaps the most significant extension to the standard in TR1 are hash table containers.
In Boost, hash tables are available as a part of the Boost multi-index container, which is a set-like container that supports multiple keys and multiple sorting orders.
Boost hash library defines hash functions for many types. They can be used both with TR1-conformant hash tables and with Boost multi-index containers.
Boost contains many more libraries. Here are some highlights: