Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

A completely reusable tokenizer

The word list examples use different approaches to extract tokens from a stream, neither of which is very flexible. Since the STL containers and algorithms all revolve around iterators, the most flexible solution will itself use an iterator. You could think of the TokenIterator as an iterator that wraps itself around any other iterator that can produce characters. Because it is certainly a type of input iterator (the most primitive type of iterator), it can provide input to any STL algorithm. Not only is it a useful tool in itself, the following TokenIterator is also a good example of how you can design your own iterators.[108]

The TokenIterator class is doubly flexible. First, you can choose the type of iterator that will produce the char input. Second, instead of just saying what characters represent the delimiters, TokenIterator will use a predicate that is a function object whose operator( ) takes a char and decides whether it should be in the token. Although the two examples given here have a static concept of what characters belong in a token, you could easily design your own function object to change its state as the characters are read, producing a more sophisticated parser.

The following header file contains two basic predicates, Isalpha and Delimiters, along with the template for TokenIterator:

//: C07:TokenIterator.h
#include <algorithm>
#include <cctype>
#include <functional>
#include <iterator>
#include <string>
struct Isalpha : std::unary_function<char, bool> {
bool operator()(char c) { return std::isalpha(c); }
class Delimiters : std::unary_function<char, bool> {
std::string exclude;
Delimiters() {}
Delimiters(const std::string& excl) : exclude(excl) {}
bool operator()(char c) {
return exclude.find(c) == std::string::npos;
template<class InputIter, class Pred = Isalpha>
class TokenIterator : public std::iterator<
std::input_iterator_tag, std::string, std::ptrdiff_t> {
InputIter first;
InputIter last;
std::string word;
Pred predicate;
TokenIterator(InputIter begin, InputIter end,
Pred pred = Pred())
: first(begin), last(end), predicate(pred) {
TokenIterator() {} // End sentinel
// Prefix increment:
TokenIterator& operator++() {
first = std::find_if(first, last, predicate);
while(first != last && predicate(*first))
word += *first++;
return *this;
// Postfix increment
class CaptureState {
std::string word;
CaptureState(const std::string& w) : word(w) {}
std::string operator*() { return word; }
CaptureState operator++(int) {
CaptureState d(word);
return d;
// Produce the actual value:
std::string operator*() const { return word; }
const std::string* operator->() const { return &word; }
// Compare iterators:
bool operator==(const TokenIterator&) {
return word.size() == 0 && first == last;
bool operator!=(const TokenIterator& rv) {
return !(*this == rv);
#endif // TOKENITERATOR_H ///:~

The TokenIterator class derives from the std::iterator template. It might appear that some kind of functionality comes with std::iterator, but it is purely a way of tagging an iterator, to tell a container that uses it what it can do. Here, you can see input_iterator_tag as the iterator_category template argument this tells anyone who asks that a TokenIterator only has the capabilities of an input iterator and cannot be used with algorithms requiring more sophisticated iterators. Apart from the tagging, std::iterator doesn t do anything beyond providing several useful type definitions. You must implement all other functionality yourself.

The TokenIterator class may look a little strange at first, because the first constructor requires both a begin and an end iterator as arguments, along with the predicate. Remember, this is a wrapper iterator that has no idea how to tell when it s at the end of its input, so the ending iterator is necessary in the first constructor. The reason for the second (default) constructor is that the STL algorithms (and any algorithms you write) need a TokenIterator sentinel to be the past-the-end value. Since all the information necessary to see if the TokenIterator has reached the end of its input is collected in the first constructor, this second constructor creates a TokenIterator that is merely used as a placeholder in algorithms.

The core of the behavior happens in operator++. This erases the current value of word using string::resize( ) and then finds the first character that satisfies the predicate (thus discovering the beginning of the new token) using find_if( ). The resulting iterator is assigned to first, thus moving first forward to the beginning of the token. Then, as long as the end of the input is not reached and the predicate is satisfied, input characters are copied into word. Finally, the TokenIterator object is returned and must be dereferenced to access the new token.

The postfix increment requires an object of type CaptureState to hold the value before the increment, so it can be returned. Producing the actual value is a straightforward operator*. The only other functions to define for an output iterator are the operator== and operator!= to indicate whether the TokenIterator has reached the end of its input. You can see that the argument for operator== is ignored it only cares about whether it has reached its internal last iterator. Notice that operator!= is defined in terms of operator==.

A good test of TokenIterator includes a number of different sources of input characters, including a streambuf_iterator, a char*, and a deque<char>::iterator. Finally, the original word list problem is solved:

//: C07:TokenIteratorTest.cpp {-g++}
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include "TokenIterator.h"
#include "../require.h"
using namespace std;
int main(int argc, char* argv[]) {
char* fname = "TokenIteratorTest.cpp";
if(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
ostream_iterator<string> out(cout, "\n");
typedef istreambuf_iterator<char> IsbIt;
IsbIt begin(in), isbEnd;
Delimiters delimiters(" \t\n~;()\"<>:{}[]+-=&*#.,/\\");
TokenIterator<IsbIt, Delimiters>
wordIter(begin, isbEnd, delimiters), end;
vector<string> wordlist;
copy(wordIter, end, back_inserter(wordlist));
// Output results:
copy(wordlist.begin(), wordlist.end(), out);
*out++ = "-----------------------------------";
// Use a char array as the source:
char* cp = "typedef std::istreambuf_iterator<char> It";
TokenIterator<char*, Delimiters>
charIter(cp, cp + strlen(cp), delimiters), end2;
vector<string> wordlist2;
copy(charIter, end2, back_inserter(wordlist2));
copy(wordlist2.begin(), wordlist2.end(), out);
*out++ = "-----------------------------------";
// Use a deque<char> as the source:
ifstream in2("TokenIteratorTest.cpp");
deque<char> dc;
copy(IsbIt(in2), IsbIt(), back_inserter(dc));
dcIter(dc.begin(), dc.end(), delimiters), end3;
vector<string> wordlist3;
copy(dcIter, end3, back_inserter(wordlist3));
copy(wordlist3.begin(), wordlist3.end(), out);
*out++ = "-----------------------------------";
// Reproduce the Wordlist.cpp example:
ifstream in3("TokenIteratorTest.cpp");
TokenIterator<IsbIt, Delimiters>
wordIter2(IsbIt(in3), isbEnd, delimiters);
set<string> wordlist4;
while(wordIter2 != end)
copy(wordlist4.begin(), wordlist4.end(), out);
} ///:~

When using an istreambuf_iterator, you create one to attach to the istream object and one with the default constructor as the past-the-end marker. Both are used to create the TokenIterator that will produce the tokens; the default constructor produces the faux TokenIterator past-the-end sentinel. (This is just a placeholder and is ignored.) The TokenIterator produces strings that are inserted into a container of string here a vector<string> is used in all cases except the last. (You could also concatenate the results onto a string.) Other than that, a TokenIterator works like any other input iterator.

When defining a bidirectional (and therefore also a random access) iterator, you can get reverse iterators for free by using the std::reverse_iterator adaptor. If you have already defined an iterator for a container with bidirectional capabilities, you can get a reverse iterator from your forward-traversing iterator with lines like the following inside your container class:

// Assume "iterator" is your nested iterator type
typedef std::reverse_iterator<iterator> reverse_iterator;
reverse_iterator rbegin() {return reverse_iterator(end());
reverse_iterator rend() {return reverse_iterator(begin());

The std::reverse_iterator adaptor does all the work for you. For example, if you use the * operator to dereference your reverse iterator, it automatically decrements a temporary copy of the forward iterator it is holding in order to return the correct element, since reverse iterators logically point one position past the element they refer to.

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire