# A very modest STL tutorial

I am using a software tool called hyperlatex to create this document. The tutorial is also available in postscript form.

## Disclaimer

This is as much a tutorial for myself as for others: I am in the process of learning STL, so I certainly don't claim to know the best way to do things. I would greatly appreciate comments or suggestions from those more knowledgeable than I. Of course, I also welcome comments about this tutorial from everyone.

I started looking at STL just a few months ago, though I have been using C++ for six or seven years, and teaching C++ and object-oriented design courses in industry for five. I think STL is really great, and I would like to encourage others to start using it. Since there seems to be very little documentation on STL, apart from the good but rather dense paper by Stepanov and Lee, I thought I would try to write something to give people a taste of what a good library will be do for them.

Another reason for getting people to start trying out STL soon is to put pressure on the compiler-writers to get their compilers patched up enough to take the strain it puts on them...

I hope I am not stepping on anyone's toes by writing this; if I am, please let me know: jak@cs.brown.edu

This is a recent project (started April 1995) to which I can't devote too much time, so it is still very short, and pretty poorly organized.

## Outline

STL contains five kinds of components: containers, iterators, algorithms, function objects and allocators.

In the section Example I present a simple example, introducing each of the five categories of STL components one at a time.

In the section Philosophy I explain the rationale behind the organization of STL, and give some hints on the best ways to use it.

The Components section goes into each category of component in more detail.

The section Extending STL shows how to define your own types to satisfy the STL requirements.

## A first example

Most of you probably use some kind of auto-allocating array-like type. STL has one called vector. To illustrate how vector works, we will start with a simple C++ program that reads integers, sorts them, and prints them out. I will gradually replace bits of this program with STL calls.

### Version 1: Standard C++

Here is a standard C++ program to read a list of integers, sort them and print them:
#include <stdlib.h>
#include <iostream.h>

// a and b point to integers.  cmp returns -1 if a is less than b,
// 0 if they are equal, and 1 if a is greater than b.
inline int cmp (const void *a, const void *b)
{
int aa = *(int *)a;
int bb = *(int *)b;
return (aa < bb) ? -1 : (aa > bb) ? 1 : 0;
}

// Sort (c library qsort)
// Print the time taken to sort

main (int argc, char *argv[])
{
const int size = 1e5;  // array of 100,000 integers
int array [size];
int n = 0;
// read an integer into the n+1 th element of array
while (cin >> array[n++]);
n--; // it got incremented once too many times

qsort (array, n, sizeof(int), cmp);

for (int i = 0; i < n; i++)
cout << array[i] << "\n";
}


### Version 2: containers, iterators, algorithms

STL provides a number of container types, representing objects that contain other objects. One of these containers is a class called vector that behaves like an array, but can grow itself as necessary. One of the operations on vector is push_back, which pushes an element onto the end of the vector (growing it by one).

A vector contains a block of contiguous initialized elements -- if element index k has been initialized, then so have all the ones with indices less than k. In particular, this means that you cannot just bang things into a vector and later remove the empty elements; this seems silly to me, but at the cost of some efficiency, you can use a Map instead, and then sort on the key.

You can ask a vector how many elements it has with size. This is the logical number of elements -- the number of elements up to the highest-indexed one you have used. There is a also a notion of capacity -- the number of elements the vector can hold before reallocating.

Let's read the elements and push them onto the end of a vector. This removes the arbitrary limit on the number of elements that can be read.

Also, instead of using qsort, we will use the STL sort routine, one of the many algorithms provided by STL. The sort routine is generic, in that it will work on many different types of containers. The way this is done is by having algorithms deal not with containers directly, but with iterators.

#### Preview of iterators

I'll go into iterators in detail later, but for now here is enough to get started.

Iterators provide a way of specifying a position in a container. An iterator can be incremented or dereferenced, and two iterators can be compared. There is a special iterator value called "past-the-end".

You can ask a vector for an iterator that points to the first element with the message begin. You can get a past-the-end iterator with the message end. The code

vector<int> v;
// add some integers to v
vector::iterator i1 = v.begin();
vector::iterator i2 = v.end();

will create two iterators like this:

Operations like sort take two iterators to specify the source range. To get the source elements, they increment and dereference the first iterator until it is equal to the second iterator. Note that this is a semi-open range: it includes the start but not the end.

Two vector iterators compare equal if they refer to the same element of the same vector.

Putting this together, here is the new program:

#include <string.h>
#include <algo.h>
#include <vector.h>
#include <stdlib.h>
#include <iostream.h>

main ()
{
vector<int> v;  // create an empty vector of integers
int input;
while (cin >> input)    // while not end of file
v.push_back (input);  // append to vector

// sort takes two random iterators, and sorts the elements between
// them.  As is always the case in STL, this includes the value
// referred to by first but not the one referred to by last; indeed,
// this is often the past-the-end value, and is therefore not
// dereferenceable.
sort(v.begin(), v.end());

int n = v.size();
for (int i = 0; i < n; i++)
cout << v[i] << "\n";
}

Incidentally, this is much faster than qsort; at least a factor of 20 on the examples I tried. This is presumably due to the fact that comparisons are done inline.

In addition to iterating through containers, iterators can iterate over streams, either to read elements or to write them.

An input stream like cin has the right functionality for an input iterator: it provides access to a sequence of elements. The trouble is, it has the wrong interface for an iterator: operations that use iterators expect to be able to increment them and dereference them.

STL provides adaptors, types that transform the interface of other types. This is very much how electrical adaptors work. One very useful adaptor is istream_iterator. This is a template type (of course!); you parameterize it by the type of object you want to read from the stream. In this case we want integers, so we would use an istream_iterator<int>. These iterators are initialized by giving them a stream, and thereafter they behave the way that the STL algorithms expect.

In order to read the elements into the vector from standard input, we will use the STL copy algorithm; this takes three iterators. The first two specify the source range, and the third specifies the destination.

The names can get pretty messy, so make good use of typedefs. Iterators are actually parameterized on two types; the second is a distance type, which I believe is really of use only on operating systems with multiple memory models. Here is a typedef for an iterator that will read from a stream of integers:

typedef istream_iterator<int,ptrdiff_t> istream_iterator_int;

Some implementations of STL, particularly for compilers that do not support default template arguments, define istream_iterators with only one parameter, and supply a hard-coded distance type. In this case, you would write:
typedef istream_iterator<int> istream_iterator_int;

So to copy from standard input into a vector, we can do this:
copy (istream_iterator_int (cin), istream_iterator_int (), v.begin());

The first iterator will be incremented and read from until it is equal to the second iterator. The second iterator is just created with the default constructor; this gives it the past-the-end value. The first iterator will also have this value when the end of the stream is reached. Therefore the range specified by these two iterators is from the current position in the input stream to the end of the stream.

There is a bit of a problem with the third iterator, though: if v does not have enough space to hold all the elements, the iterator will run off the end, and we will dereference a past-the-end iterator (which will cause a segfault).

What we really want is an iterator that will do insertion rather than overwriting. There is an adaptor to do this, called back_insert_iterator. This type is parameterized by the container type you want to insert into.

So input is done like this:

  typedef istream_iterator<int,ptrdiff_t> istream_iterator_int;

vector<int> v;
istream_iterator_int start (cin);
istream_iterator_int end;
back_insert_iterator<vector<int> > dest (v);

copy (start, end, dest);

Similarly, to print out the values after sorting, we use copy:
  copy (v.begin(), v.end(), ostream_iterator<int> (cout, "\n"));

ostream_iterator is another adaptor; it provides output iterator functionality: assigning to the dereferenced iterator will write the data out. The ostream_iterator constructor takes two arguments: the stream to use and the separator. It prints the separator between elements.

Putting this all together,

#include <string.h>
#include <algo.h>
#include <vector.h>
#include <stdlib.h>
#include <iostream.h>

main ()
{
vector<int> v;
istream_iterator<int,ptrdiff_t> start (cin);
istream_iterator<int,ptrdiff_t> end;
back_insert_iterator<vector<int> > dest (v);

copy (start, end, dest);
sort(v.begin(), v.end());
copy (v.begin(), v.end(), ostream_iterator<int>(cout, "\n"));
}


### Discussion

I find the final version of the program the cleanest, because it reflects the way I think of the computation happening: the vector is copied into memory, sorted, and copied out again.

In general, in STL, operations are done on containers as a whole, rather than iterating through the elements of the container explicitly in a loop. One obvious advantage of this is that it lends itself easily to parallelization or hairy optimizations (e.g., one could be clever about the order the elements were accessed in to help avoid thrashing).

Most of the STL algorithms apply to ranges of elements in a container, rather than to the container as a whole. While this is obviously more general than having operations always apply to the entire container, it makes for slightly clumsy syntax. Some implementations of STL (e.g., ObjectSpace), provide supplementary versions of the algorithms for common cases. For example, STL has an algorithm count that counts the number of times a particular element appears in a container:

template <class InputIterator, class T, class Size>
void count (InputIterator start, InputIterator end, const T& value, Size& n);

To find how many elements have the value 42 in a vector v, you would write:
int n = 0;
count (v.begin(), v.end(), 42, n);

ObjectSpace defines an algorithm os_count that provides a simpler interface:
int n = os_count (v, 42);


## STL components

### Containers

Containers are objects that conceptually contain other objects. They use certain basic properties of the objects (ability to copy, etc.) but otherwise do not depend on the type of object they contain.

STL containers may contain pointers to objects, though in this case you will need to do a little extra work.

vectors, lists, deques, sets, multisets, maps, multimaps, queues, stacks, and priority queues, did I miss any? are all provided.

Perhaps more importantly, built-in containers (C arrays) and user-defined containers can also be used as STL containers; this is generally useful when applying operations to the containers, e.g., sorting a container. Using user-defined types as STL containers can be accomplished by satisfying the requirements listed in the STL container requirements definition.

If this is not feasible, you can define an adaptor class that changes the interface to satisfy the requirements.

All the types are "templated", of course, so you can have a vector of ints or Windows or a vector of vector of sets of multimaps of strings to Students. Sweat, compiler-writers, sweat!

To give you a brief idea of the containers that are available, here is the heirarchy:

#### Sequences

Contiguous blocks of objects; you can insert elements at any point in the sequence, but the performance will depend on the type of sequence and where you are inserting.

##### Vectors
Fast insertion at end, and allow random access.
##### Lists
Fast insertion anywhere, but provide only sequential access.
##### Deques
Fast insertion at either end, and allow random access. Restricted types, such as stack and queue, are built from these using adaptors.
##### Stacks and queues

Provide restricted versions of these types, in which some operations are not allowed.

#### Associative containers

Associative containers are a generalization of sequences. Sequences are indexed by integers; associative containers can be indexed by any type.

The most common type to use as a key is a string; you can have a set of strings, or a map from strings to employees, and so forth.

It is often useful to have other types as keys; for example, if I want to keep track of the names of all the Widgets in an application, I could use a map from Widgets to Strings.

##### Sets

Sets allow you to add and delete elements, query for membership, and iterate through the set.

##### Multisets

Multisets are just like sets, except that you can have several copies of the same element (these are often called bags).

##### Maps
Maps represent a mapping from one type (the key type) to another type (the value type). You can associate a value with a key, or find the value associated with a key, very efficiently; you can also iterate through all the keys.
##### Multimaps

Multimaps are just like maps except that a key can be associated with several values.

Should add other containers: priority queue, bit vector, queue.

### Iterators

Iterators are like location specifiers for containers or streams of data, in the same way that an int* can be used as a location specifier for an array of integers, or an ifstream can be used as a location specifier for a file. STL provides a variety of iterator for its different collection types and for streams.

#### Input iterators

Input iterators provide access to data sources. The source may be an STL container, another type of container, a stream, a virtual source (such as a set of permutations), etc.

#### Output iterators

Output iterators provide access to data sinks: locations to store the results of a computation. The sink may be an STL container, a user-defined container, a stream, etc.

#### Using input and output iterators

Just input and output iterators are enough to do quite a lot, since many operations boil down to copying objects around. For example, this function copies all the elements of a container v to standard output. ostream_iterator is an adaptor; it is an output iterator type. The iterator operations are defined so that in the case below, assigning through the iterator prints to standard output, with each print followed by a newline.

copy (v.begin(), v.end(), ostream_iterator<int> (cout, "\\n"));

The first two arguments specify the source data: start an iterator that points to the beginning of the vector v, and keep going until the iterator compares equal with v.end(), which is called a past-the-end value. Almost all STL operations have one or more pairs of input iterators specifying the data to work with.

The third argument is an adaptor that turns an ostream like cout into an output iterator; don't worry about the details for now.

A similar operation reads data into a vector (for now, we will assume the vector has enough space allocated already):

copy (istream_iterator<int> (cin), istream_iterator<int> (), v.begin());

Moreover, input and output iterators are necessary to do many things, since we usually need to specify what data we want to work with, and where to put the result.

#### Forward iterators

A forward iterator allows traversal of the sequence, reading and/or writing each element, but no backing up. Many algorithms request a forward iterator, for example

long *p = new int [1000];
fill (p, p+100, 0);

Fill's first two arguments specify the range the operation should take place on, and the third specifies the value to write through the iterator at each position.

#### Bidirectional iterators

Bidirectional iterators can be moved forward or backward, and can be used to read or write the elements of the sequence. Moving an iterator from one part of the sequence to another takes time proportional to the number of elements between the two.

#### Containers and iterators

All the STL containers provide at least bidirectional iterators: lists, sets, maps, and so on can be traversed forward or backward. Some containers provide even more flexible indexing:

#### Random access iterators

Random access iterators can jump from any place to any other place in constant time I am not sure that this is required, and it is certainly allowed to be amortized constant time. Every C pointer type is an STL random iterator for a C array container. If you have a random-access container, you can perform all sorts of nifty operations on it, such as mapping over a vector, with or without accumulation, finding and replacing elements satisfying predicates, partitions, shuffling, and many more. The extent of this library never ceases to amaze me given that the source code is really quite small. I think that is a testimony to this kind of generic programming.

### Algorithms

The STL algorithms are template C++ functions to perform operations on containers. In order to be able to work with many different types of containers, the algorithms do not take containers as arguments. Instead, they take iterators that specify part or all of a container. In this way the algorithms can be used to work on entities that are not containers; for example, the function copy can be used to copy data from standard input into a vector.

Some algorithms require only the capabilities of input iterators, while others require random access (e.g., to sort).

The algorithms include sorting operations (sort, merge, min, max...), searching operations (find, count, equal...), mutating operations (transform, replace, fill, rotate, shuffle...), and generalized numeric operations (accumulate, adjacent difference...).

### Function objects

Function objects are STL's way of representing "executable data". For example, one of the STL algorithms is for_each. This applies a function to each object in a container. You need to be able to specify what to do to each object in the container.

#### Overview

Function objects are objects on which at least one parenthesis operation (. . .) is defined. They are used for three main purposes: generating data, testing data (predicates), and applying operations.

#### Generators

Algorithms like generate walk through a range, calling a function object at each step, and assigning the result of the function to the current element.

[picture]

For example, here is a function that always returns 0:

int zero() { return 0; }

To fill a vector with zeroes, one could use the algorithm generate with the function object zero:

vector<int> v (100);
generate (v.begin(), v.end(), zero);

Of course, it would be nice if our function were a bit more widely useful -- for example, allowing an arbitrary arithmetic sequence. In order to do this, the function object has to store some state indicating where in the sequence it is. There are two ways to do this. One is to use static variables inside a global function, the other is to define a class of function objects.

[In an aside] There are several problems with using static variables in a function to store state. There can only be one position remembered in the sequence -- copies of the function object will all always be positioned at the same point in the sequence. [Other problems?] <p> Here is a class Iota. It provides an arithmetic sequence, starting with some initial value, and repeatedly adding an increment to it. The function call operator returns the current value and moves on to the next element of the sequence. The template is defined with two types S and T. Usually these will be the same, but they might be different, e.g., Date and int. It is usually a good idea to ask yourself if there is some straightforward generalization of what you are about to do -- if it doesn't make things much more complicated, it is probably worth it.

template <class S, class T>
class Iota
{
S cur;
T inc;
public:
Iota (const S& initial, const T& increment)
: cur (initial), inc (increment)
{ }
S operator()() { S tmp (cur); cur += inc; return tmp; }
};


Requirements: if a is an instance of the type S, and b is an instance of the type T, the following expressions must be valid:

S a (b)
a += b

This template class can be used with any types S and T that satisfy the requirements; for example, if both S and T are int, the requirements are satisfied:

vector<int> v (365);
generate (v.begin(), v.end(), Iota<int,int> (0, 1));
cout << v << endl;
end{verbatim}

It is a bit tedious to have to keep specifying the types of the
arguments; you might hope that the compiler could figure them out from
the expressions provided.  Unfortunately, you can't create an instance
of a template class without providing the types, but you <em>can</em>
use a function to help out, and get the same effect:

\begin{verbatim}
template <class S, class T>
Iota<S, T> makeIota (const S& s, const T& t)
{
return Iota<S, T> (s, t);
}
end{verbatim}

And now the user code becomes:

\begin{verbatim}
vector<int> v (365);
generate (v.begin(), v.end(), makeIota (0, 1));
cout << v << endl;
end{verbatim}

Here, the function object is storing some state between calls; it is
what is called a <em>closure</em> in some languages.  Anything needed to
initialize the data is provided in the construction of the function
object.

\subsubsection{Predicates}

The second type of function object is used to test things; the
parenthesis operator will be defined to return something that can be
tested for truth.

\code{find_if} uses a function object to test
each element of a range, returning an iterator pointing to the first
element that satisfies the test.  In this case, the function object
takes an argument, the element of the range, and returns a boolean:

\code{bool greaterThanZero (int i) { return i > 0; }}

This could be used to move to the first strictly positive element of a
range:

\begin{verbatim}
typedef vector<int>::iterator iterator;
typedef vector<int> vector;
typedef ostream_iterator<int> output;

vector v;
iterator iter = find_if (v.begin(), v.end(), greaterThanZero);
if (iter == v.end())
cout << "no elements greater than zero" << endl;
else
{
cout << "elements starting from first greater than zero: ";
copy (iter, v.end(), output (cout, " "));
}
end{verbatim}

Again, it is often useful to be able to provide state in the predicate
object.  Here is a predicate that tests true if the element is within a
specified range:

\begin{verbatim}
class InRange
{
const T& low;
const T& high;
public:
InRange (const T& l, const T& h) : low (l), high (h) { }
bool operator()(const T& t) { return ! (t < l) && t < h; }
};
end{verbatim}

Here we find, and print, all the elements of a vector that fall within a
particular range:

\begin{verbatim}
typedef vector<int>::iterator iterator;
typedef vector<int> vector;
typedef ostream_iterator<int> output;

vector v (100);
generate (v.begin(), v.end(), rand);

iterator iter (v);
while (iter != v.end())
{
iter = find (v.begin(), v.end(), InRange (0, 10000));
cout << *iter << endl;
}

end{verbatim}

It is possible to \link{simulate lexical scoping}[(see
Appendix~\ref{lambda-expressions})]{lambda-expressions}.

There are many pre-defined (templated, of course)  function
objects that can be used -- many algorithms expect a function as an
argument.

\note{example}

Sometimes you have a class that does the right thing, but has the
between you and another class, and translate the messages you want to
send into the messages the other class wants to receive.

For example, the \code{copy} function expects an input iterator to
get its data from.  The \code{istream} class has the right
functionality: it acts as a source of data, but it has the wrong
interface: it uses \code{<<} etc.

There is an adaptor called \code{istream_iterator} that provides
the interface that \code{copy} expects, translating requests into
\code{istream} operations.

Other adaptors provide backward-moving iterators from forward-moving
iterators, and queues from lists, for example.

Adaptors are very useful, but you don't have to understand them to use
STL; treat them as black magic for now.

\subsection{Allocators}
\label{components-allocators}

I confess I don't really understand STL's allocation model properly
anything about them for now either.

\section{Extending STL}
\label{extending}

\section{Examples}

\paragraph{Iterators}

The STL iterator model is somewhat different from most iterators I have
seen.  Most importantly, it is very flexible in regards to the type of
thing iterators are ranging over.  Containers are conceptually grouped
by the type of access iterators can provide to them, and iterations on
\emph{any} random access container (for example) is done the same
way -- the object doing the iteration does not know what kind of
container it is.

The other important difference is that whereas many iterator mechanisms
are mainly intended for iteration over the entire collection, STL always
deals in terms of ranges, though of course the entire collection is just
a particular range.

Be careful not to confuse the past-the-end iterator value with the
"null" value that other iterator types often provide to indicate the end
of the container.  In particular, don't use the past-the-end iterator to
indicate an error; if you want to indicate errors, you should provide
\emph{singular} iterator values; I will describe these in the section
on iterators.

\subsection{Example 2: Finding scheduling conflicts}

There is just a sketch of the problem and solution here.  Students
are associated with a list of courses, and courses with a list of
timeslots.  We want to know which students have different courses with
same timeslot.  Uses:
\begin{itemize}
\item algorithms: copy, find
\item iterators: istream_iterator, ostream_iterator
\item containers: multiset, set
\end{itemize}

\subsubsection{Problem}
I have a file of information about students, of the form:
\begin{verbatim}
name [course...]
...

and a file of information about courses, of the form:
course [timeslot...]
...

The names, courses and timeslots are arbitrary strings, but for simplicity we will assume that each token is one word (e.g., we write student names like Jak_Kirman.

The program must print out the names of students who have collisions in their course schedules, along with the courses causing the collisions. Repetitions in the lists of courses or lists of timeslots should be ignored.

### Example 3: Stream calculator

There is just a sketch of the problem and solution here. I want to give my program command-line expressions in Reverse Polish Notation, like a b + to mean (a+b). The elements of expressions can be constants or filenames. The program should repeatedly evaluate the expression, replacing any occurrence of a file name with the next number read from that file.

As an added bonus, the types we define will allow us to combine arbitrary streams of input with arbitrary operations.

• algorithms: copy, find
• iterators: input_iterator, istream_iterator, ostream_iterator
• functions: binary_function, unary_function
• containers: stack, vector

#### Problem

I want a program that will let me perform arithmetic operations on streams of numbers, with each stream coming from a different file. So as not to complicate the example with parsing, I will use reverse Polish notation, e.g., 2 cost1 * 3 cost2 * + 5 /. The calculator has an internal stack. The expression is read left to right; if we find a number, we push it onto the stack. If we find a name, we read a number from that file and push it onto the stack. If we find an operator, we apply it, popping elements off the stack as arguments. The above expression computes ((2 * cost1) + (3 * cost2))/5.

#### Sketch of design

I will have a stack of input_iterators:

template <class T>
typedef input_iterator<T> *input_iterator_p;

template <class T>
typedef stack<vector<input_iterator_p<T> > > input_stack;

As each token is read from the command line, we create an iterator, using the stack as the source of any arguments. At the end, the stack should have a single iterator, which we can then copy to the output stream. The only tricky part here is the "dynamic inheritance".

I will have a kind of input_iterator called constant_source, for which

• increment does nothing
• dereference returns the constant
template <class T, class Distance> // default Distance = ptrdiff_t
class constant_source : public input_iterator<T,Distance>
{
private:
const T& value;
public:
friend bool operator==(const number_source<T, Distance>& x,
const number_source<T, Distance>& y)
number_source (const T& t) : value (t), bad (false){}
number_source<T,Distance>& operator++(int = 0) { return *this; }
const T& operator*() const { return value; }
};

A combiner input iterator is created from two input iterators s1 and s2, and a function object func of type binary_function<T,T,T>.
increment
increments s1 and s2
dereference
dereferences s1 and s2, applies func and returns the result
template <class T, class Distance> // default Distance = ptrdiff_t
class combiner : public input_iterator<T,Distance>
{
protected:
void read() { ++source1; ++source2; value = func (*source1, *source2); }
friend bool operator==(const combiner<T, Distance>& x,
const combiner<T, Distance>& y)
{ return (x.source1 == source1) && (y.source1 == source2); }

combiner() : source1(), source2() {}
combiner (input_iterator<T,Distance>& s1,
input_iterator<T,Distance>& s2,
binary_function<T,T,T> f) : source1 (s1), source2 (s2), func (f)
combiner<T,Distance>& operator++() { read(); return *this; }
combiner<T,Distance>& operator++(int)
{ combiner<T,Distance>& tmp = *this; read(); return tmp;
const T& operator*() const { return value; }
};

Now, for example, to read pairs from file1 and file2 and print their sums:
main (int argc, char *argv[])
{
istream_iterator<double>(ifstream (argv[2])),
plus<double>);

}


## Lambda expressions

Suppose we want to apply a function to all the elements of a vector. We can define the function locally, since it is a type definition. It can take any context it needs in the constructor, and store it internally.

This is not as elegant as lisp or perl's lexical scoping, but it is better than nothing.

function addOffset(vector<int>& v, int n)
{

// we want to add n to each element of v
{ AddN(int n) : _n (n) {};
int operator() (const int& k) { return k + n; }
};