Tag Archives: C++

ELIZA in C++

Introduction

ELIZA was a chatterbot program developed by Joseph Weizenbaum at MIT Artificial Intelligence Laboratory in the 1960s. Although very simple in design, Weizenbaum was dismayed to find that people who talked to ELIZA often believed that the program actually understood them, and his secretary even asked to be left alone with ELIZA so that she could have a real conversation.

The original program was written in a variant of LISP, but was later translated to other languages, and became very popular with he rise of personal computers when it appeared in books of BASIC games, which was where I first saw it. This post contains an implementation of the program in C++.

How it works

ELIZA’s operation is based on pattern matching and the selection of ready-made responses. The program has a list of patterns to match with the user input, and for each pattern there are a number of response templates. Below are some examples:

    el.responds_to("Can you (.*)")
        .with("Don't you believe that I can %1%?")
        .with("You want me to be able to %1%?");

    el.responds_to("Can I ([^\\?]*)\\??")
        .with("Perhaps you don't want to %1%.")
        .with("Do you want to be able to %1%?")
        .with("If you could %1%, would you?");

    el.responds_to("You are (.*)")
        .with("Why do you think I am %1%?")
        .with("Does it please you to think that I'm %1%?")
        .with("Perhaps you would like be %1%.")
        .with("Do you sometimes wish you were %1%?");

    el.responds_to("I don'?t (.*)")
        .with("Don't you really %1%?")
        .with("Why don't you %1%?")
        .with("Do you wish to be able to %1%?");

As C++ isn’t very good with data literals I have used some proxy class magic to make a fluent syntax for defining the patterns and response templates.

The response templates contain placeholders for expansion (the %1% symbols) and these are filled in using the text captured by the pattern.

The whole algorithm for processing the input and generating the output requires just two small functions, which are shown below:

std::string eliza::translate(const std::string& input) const
{
    std::vector<std::string> words;
    boost::split(words, input, boost::is_any_of(" \t"));
    for (auto& word : words) {
        boost::algorithm::to_lower(word);
        for (auto& trans : translations_) {
            if (trans.first == word) {
                word = trans.second;
                break;
            }
        }
    }
    return boost::algorithm::join(words, " ");
}

std::string eliza::respond(const std::string& input) const
{
    std::string response;
    for (auto& ex : exchanges_) {
        boost::smatch m;
        if (boost::regex_search(input, m, ex.prompt_)) {
            response = ex.responses_[rand() % ex.responses_.size()];
            if (m.size() > 1 && response.find("%1%") != response.npos) {
                std::string translation = translate(std::string(m[1].first, m[1].second));
                boost::trim_right_if(translation, boost::is_punct());
                response = boost::str(boost::format(response) % translation);
            }
            break;
        }
    }
    return response;
}

The respond() function first goes through the list of patterns and finds the first one that matches. From that it randomly selects a response template. If the pattern captured some text, and the response has placeholders for replacement, these are filled in. Before using the captured text, it is passed to translate(), which converts pronouns, changing "I" to "you" "my" to "your" and so on. It is this translation, and the incorporation of captured phrases from the input in the response, that makes ELIZA surprisingly convincing.

There is a lot of scope for improving the program, not only by adding more patterns and responses, but also by making the parsing more sophisticated (for example collapsing similar inputs to a canonical form), adding a more capable, recursive templating system, and possibly connecting the program to external data sources.

The Code

This is the header file:

#ifndef ELIZA_HPP
#define ELIZA_HPP

#include <string>
#include <vector>
#include <boost/regex.hpp>

namespace MB
{

struct exchange
{
    boost::regex prompt_;
    std::vector<std::string> responses_;
    explicit exchange(const std::string& prompt)
      : prompt_(prompt, boost::regex::icase)
    {
    }
};

class exchange_builder;

class eliza
{
    std::string name_;
    std::vector<exchange> exchanges_;
    std::vector<std::pair<std::string, std::string> > translations_;
public:
    eliza(const std::string& name = "Eliza")
      : name_(name)
    {
        add_translations();
    }
    const std::string& name() const
    {
        return name_;
    }
    exchange_builder responds_to(const std::string& prompt);
    void add_exchange(const exchange& ex)
    {
        exchanges_.push_back(ex);
    }
    std::string respond(const std::string& input) const;
private:
    void add_translations();
    std::string translate(const std::string& input) const;
};

class exchange_builder
{
    friend eliza;
    eliza& eliza_;
    exchange exchange_;

    exchange_builder(eliza& el, const std::string& prompt)
      : eliza_(el), exchange_(prompt)
    {
    }

public:
    ~exchange_builder()
    {
        eliza_.add_exchange(exchange_);
    }

    exchange_builder& with(const std::string& response)
    {
        exchange_.responses_.push_back(response);
        return *this;
    }
};

}; // namespace MB

#endif // ELIZA_HPP

The implementation:

#include <cstdlib>

#include <boost/algorithm/string.hpp>
#include <boost/format.hpp>

#include "eliza.hpp"

using namespace MB;

exchange_builder eliza::responds_to(const std::string& prompt)
{
    return exchange_builder(*this, prompt);
}

void eliza::add_translations()
{
    translations_.push_back(std::make_pair("am", "are"));
    translations_.push_back(std::make_pair("was", "were"));
    translations_.push_back(std::make_pair("i" , "you"));
    translations_.push_back(std::make_pair("i'd", "you would"));
    translations_.push_back(std::make_pair("you'd", "I would"));
    translations_.push_back(std::make_pair("you're", "I am"));
    translations_.push_back(std::make_pair("i've", "you have"));
    translations_.push_back(std::make_pair("i'll", "you will"));
    translations_.push_back(std::make_pair("i'm", "you are"));
    translations_.push_back(std::make_pair("my", "your"));
    translations_.push_back(std::make_pair("are", "am"));
    translations_.push_back(std::make_pair("you've", "I have"));
    translations_.push_back(std::make_pair("you'll", "I will"));
    translations_.push_back(std::make_pair("your", "my"));
    translations_.push_back(std::make_pair("yours", "mine"));
    translations_.push_back(std::make_pair("you", "me"));
    translations_.push_back(std::make_pair("me", "you"));
    translations_.push_back(std::make_pair("myself", "yourself"));
    translations_.push_back(std::make_pair("yourself", "myself"));

}

std::string eliza::translate(const std::string& input) const
{
    std::vector<std::string> words;
    boost::split(words, input, boost::is_any_of(" \t"));
    for (auto& word : words) {
        boost::algorithm::to_lower(word);
        for (auto& trans : translations_) {
            if (trans.first == word) {
                word = trans.second;
                break;
            }
        }
    }
    return boost::algorithm::join(words, " ");
}

std::string eliza::respond(const std::string& input) const
{
    std::string response;
    for (auto& ex : exchanges_) {
        boost::smatch m;
        if (boost::regex_search(input, m, ex.prompt_)) {
            response = ex.responses_[rand() % ex.responses_.size()];
            if (m.size() > 1 && response.find("%1%") != response.npos) {
                std::string translation = translate(std::string(m[1].first, m[1].second));
                boost::trim_right_if(translation, boost::is_punct());
                response = boost::str(boost::format(response) % translation);
            }
            break;
        }
    }
    return response;
}

An example program, which includes the initialisation of ELIZA with a default set of patterns and responses:

#include <iostream>

#include "eliza.hpp"

static void add_responses(MB::eliza& el);

int main()
{
    MB::eliza el;

    add_responses(el);

    std::cout << "Hello. I'm " << el.name() << ". How are you feeling today?\n";
    std::string input;
    while (std::getline(std::cin, input) && input != "quit") {
        std::cout << el.respond(input) << "\n";
    }
}

static void add_responses(MB::eliza& el)
{
    el.responds_to("Can you (.*)")
        .with("Don't you believe that I can %1%?")
        .with("You want me to be able to %1%?");

    el.responds_to("Can I ([^\\?]*)\\??")
        .with("Perhaps you don't want to %1%.")
        .with("Do you want to be able to %1%?")
        .with("If you could %1%, would you?");

    el.responds_to("You are (.*)")
        .with("Why do you think I am %1%?")
        .with("Does it please you to think that I'm %1%?")
        .with("Perhaps you would like be %1%.")
        .with("Do you sometimes wish you were %1%?");

    el.responds_to("I don'?t (.*)")
        .with("Don't you really %1%?")
        .with("Why don't you %1%?")
        .with("Do you wish to be able to %1%?");

    el.responds_to("I feel (.*)")
        .with("Does it trouble you to feel %1%?")
        .with("Do you often feel %1%?")
        .with("Do you enjoy feeling %?%")
        .with("When do you usually feel %1%?")
        .with("When you feel %1%, what do you do?");

    el.responds_to("Why don'?t you ([^\\?]*)\\??")
        .with("Do you really believe I don't %1%?")
        .with("Perhaps in good time I will %1%.")
        .with("Do you want me to %1%?");

    el.responds_to("Why can'?t I ([^\\?]*)\\??")
        .with("Do you think you should be able to %1%?")
        .with("Why can't you?");

    el.responds_to("Are you ([^\\?]*)\\??")
        .with("Why are you interested in whether I am %1%?")
        .with("Would you prefer it if I were not %1%?")
        .with("Perhaps in your fantasies I am %1%.");

    el.responds_to("I can'?t (.*)")
        .with("How do you know you can't %1%?")
        .with("Have you tried to %1%?")
        .with("Perhaps now you can %1%");

    el.responds_to("I am (.*)")
        .with("Did you come to me because you are %1%?")
        .with("How long have you been %1%?");

    el.responds_to("I'?m (.*)")
        .with("Do you believe it is normal to be %1%?")
        .with("Do you enjoy being %1%?");

    el.responds_to("You (.*)")
        .with("We were discussing you - not me.")
        .with("Oh, I %1%?");

    el.responds_to("I want (.*)")
        .with("What would it mean to you if you got %1%?")
        .with("Why do you want %1%?")
        .with("Suppose you soon got %1%?")
        .with("What if you never got %1%?")
        .with("I sometimes also want %1%");

    el.responds_to("What (.*)")
        .with("Why do you ask?")
        .with("Does that question interest you?")
        .with("What answer would please you the most?")
        .with("What do you think?")
        .with("Are such questions on your mind often?")
        .with("What is it that you really want to know?")
        .with("Have you asked anyone else?")
        .with("Have you asked such questions before?")
        .with("What else comes to mind when you ask that?");

    el.responds_to("Because")
        .with("Is that the real reason?")
        .with("Don't any other reasons come to mind?")
        .with("Does that reason explain anything else?")
        .with("What other reasons might there be?");

    el.responds_to("Sorry")
        .with("There are many times when no apology is needed.")
        .with("What feelings do you have when you apologize?");

    el.responds_to("Dream")
        .with("What does that dream suggest to you?")
        .with("Do you dream often?")
        .with("What persons appear in your dreams?")
        .with("Are you disturbed by your dreams?");

    el.responds_to("^Hello")
        .with("How do you do... Please state your problem.");

    el.responds_to("^Maybe")
        .with("You don't seem quite certain.")
        .with("Why the uncertain tone?")
        .with("Can't you be more positive?")
        .with("You aren't sure?")
        .with("Don't you know?");

    el.responds_to("^No[.!]?$")
        .with("Are you saying that just to be negative?")
        .with("You are being a bit negative.")
        .with("Why not?")
        .with("Are you sure?")
        .with("Why no?");

    el.responds_to("Your (.*)")
        .with("Why are you concerned about my %1%?")
        .with("What about your own %1%?");

    el.responds_to("Always")
        .with("Can you think of a specific example?")
        .with("When?")
        .with("Really, always?");

    el.responds_to("Think (.*)")
        .with("What are you thinking of?")
        .with("Do you really think so?")
        .with("But you are not sure %1%?")
        .with("Do you doubt %1%?");

    el.responds_to("Alike")
        .with("In what way?")
        .with("What resemblance do you see?")
        .with("What does the similarity suggest to you?")
        .with("what other connections do you see?")
        .with("Could there really be some connection?")
        .with("How?");

    el.responds_to("^Yes[.!]?$")
        .with("You seem quite positive.")
        .with("Are you sure?")
        .with("I see.")
        .with("I understand.");

    el.responds_to("Friend")
        .with("Why do you bring up the topic of friends?")
        .with("Do your friends worry you?")
        .with("Do your friends pick on you?")
        .with("Are you sure you have any friends?")
        .with("Do you impose on your friends?")
        .with("Perhaps your love for friends worries you.");

    el.responds_to("Computer")
        .with("Do computers worry you?")
        .with("Are you talking about me in particular?")
        .with("Are you frightened by machines?")
        .with("Why do you mention computers?")
        .with("What do you think machines have to do with your problem?")
        .with("Don't you think computers can help people?")
        .with("What is it about machines that worries you?");

    el.responds_to("(.*)")
        .with("Say, do you have any psychological problems?")
        .with("What does that suggest to you?")
        .with("I see.")
        .with("I'm not sure I understand you fully.")
        .with("Come come elucidate your thoughts.")
        .with("Can you elaborate on that?")
        .with("That is quite interesting.");
}

Finally, here is a makefile:

ALL := eliza
all : $(ALL)
eliza : eliza.cpp eliza.hpp main.cpp
$(CXX) $(CXXFLAGS) -g -std=c++11 eliza.cpp main.cpp -o eliza -lboost_regex
.PHONY : clean
clean :
$(RM) $(ALL)

	

BK-Tree in C++

A BK-tree is an efficient data structure for storing items for which there is some concept of distance between them. A common use is to store words for approximate string matching, using the Levenshtein distance metric. Another use is to store phrases using some measure of semantic distance in order to implement an AI system like a chatterbot.

This is a simple implementation of a BK-tree in C++.

#ifndef BK_TREE_HPP
#define BK_TREE_HPP

#include <map>
#include <memory>
#include <type_traits>

namespace MB
{

template <typename T, typename Unit, typename Metric> class bktree;

namespace detail
{

template <typename T, typename Unit, typename Metric>
class bktree_node
{
    friend class bktree<T, Unit, Metric>;
	typedef bktree_node<T, Unit, Metric> node_type;
    typedef std::unique_ptr<node_type> node_ptr_type;
	
	T value_;
	std::map<Unit, node_ptr_type> children_;

	bktree_node(const T &value)
		: value_(value)
    {
    }

	bool insert(const T& value, const Metric& distance)
    {
        bool inserted = false;
		Unit dist = distance(value, this->value_);
		if (dist > 0) {
            // Not already here 
            auto it = children_.find(dist);
            if (it == children_.end()) {
                // Attach a new edge here
                children_.insert(std::make_pair(dist, node_ptr_type(new node_type(value))));
                inserted = true;
            }
            else {
                // Follow existing edge
                inserted = it->second->insert(value, distance);
            }
            return inserted;
        }
	}

    template <class OutputIt>
	OutputIt find(const T &value, const Unit& limit, const Metric& distance, OutputIt it) const
    {
		Unit dist = distance(value, this->value_);
		if (dist <= limit) {
            // Found one
			*it++ = std::make_pair(this->value_, dist);
        }
		for (auto iter = children_.begin(); iter != children_.end(); ++iter) {
            // Follow edges between dist + limit and dist - limit
			if (dist - limit <= iter->first && dist + limit >= iter->first) {
				iter->second->find(value, limit, distance, it);
            }
		}
        return it;
	}
};

}; // namespace detail

template <typename T, typename Unit, typename Metric>
class bktree
{
private:
	typedef typename detail::bktree_node<T, Unit, Metric>::node_type node_type;
    typedef typename detail::bktree_node<T, Unit, Metric>::node_ptr_type node_ptr_type;

    node_ptr_type head_;
    const Metric distance_;
	size_t size_;

public:
	bktree(const Metric& distance = Metric())
        : head_(nullptr), distance_(distance), size_(0L)
    {
        static_assert(std::is_integral<Unit>::value, "Integral unit type required.");
    }

	bool insert(const T &value)
    {
        bool inserted = false;
		if (head_ == nullptr) {
            // Inserting the first value
			head_ = node_ptr_type(new node_type(value));
			size_ = 1;
            inserted = true;
		}
        else if (head_->insert(value, distance_)) {
            ++size_;
            inserted = true;
        }
        return inserted;
	}

    template <class OutputIt>
	OutputIt find(const T& value, const Unit& limit, OutputIt it) const
    {
		return head_->find(value, limit, distance_, it);
	}

	size_t size() const
    {
		return size_;
	}
};

}; // namespace MB

#endif // BK_TREE_HPP

Here is an example program. It loads a dictionary from a file, and then prompts the user to enter words and a limit on distance, and it will return all words within that Levenshtein distance of the word entered. I used this dictionary with it:

#include <fstream>
#include <iostream>
#include <string>

#include "bk_tree.hpp"
#include "levenshtein_distance.hpp"

int main()
{
    const char filename[] = "dictionary.txt";
    std::ifstream ifs(filename);
    if (!ifs) {
        std::cerr << "Couldn't open " << filename << " for reading\n";
        return 1;
    }
    MB::bktree<std::string, int, levenshtein_distance> tree;
    std::string word;
    while (ifs >> word) {
        tree.insert(word);
    }
    std::cout << "Inserted " << tree.size() << " words\n";
    std::vector<std::pair<std::string, int> > results;
    do {
        std::cout << "Enter a word (\"quit!\" to quit)> ";
        std::cin >> word;
        if (word != "quit!") {
            int limit;
            std::cout << "Enter a limit> ";
            std::cin >> limit;
            tree.find(word, limit, std::back_inserter(results));
            for (auto it = results.begin(); it != results.end(); ++it) {
                std::cout << it->first << "(distance " << it->second << ")\n";
            }
            results.clear();
        }
    }  while (word != "quit!");
}

Example run:

$ ./dictionary
Inserted 127142 words
Enter a word ("quit!" to quit)> mispelling
Enter a limit> 2
spelling(distance 2)
misdealing(distance 2)
impelling(distance 2)
miscalling(distance 2)
mispenning(distance 2)
misrelying(distance 2)
respelling(distance 2)
dispelling(distance 1)
misbilling(distance 2)
misspelling(distance 1)
misspellings(distance 2)
Enter a word ("quit!" to quit)> quit!
$

Here is an implementation of the Levenshtein distance:

#include <string>
#include <vector>
#include <algorithm>

namespace MB
{

namespace detail
{

template <typename T>
T min3(const T& a, const T& b, const T& c)
{
   return std::min(std::min(a, b), c);
}

}; // namespace detail

class levenshtein_distance 
{
    mutable std::vector<std::vector<unsigned int> > matrix_;

public:
    explicit levenshtein_distance(size_t initial_size = 8)
        : matrix_(initial_size, std::vector<unsigned int>(initial_size))
    {
    }

    unsigned int operator()(const std::string& s, const std::string& t) const
    {
        const size_t m = s.size();
        const size_t n = t.size();
        // The distance between a string and the empty string is the string's length
        if (m == 0) {
            return n;
        }
        if (n == 0) {
            return m;
        }
        // Size the matrix as necessary
        if (matrix_.size() < m + 1) {
            matrix_.resize(m + 1, matrix_[0]);
        }
        if (matrix_[0].size() < n + 1) {
            for (auto& mat : matrix_) {
                mat.resize(n + 1);
            }
        }
        // The top row and left column are prefixes that can be reached by
        // insertions and deletions alone
        unsigned int i, j;
        for (i = 1;  i <= m; ++i) {
            matrix_[i][0] = i;
        }
        for (j = 1; j <= n; ++j) {
            matrix_[0][j] = j;
        }
        // Fill in the rest of the matrix
        for (j = 1; j <= n; ++j) {
            for (i = 1; i <= m; ++i) {
                unsigned int substitution_cost = s[i - 1] == t[j - 1] ? 0 : 1;
                matrix_[i][j] =
                    detail::min3(matrix_[i - 1][j] + 1,         // Deletion
                    matrix_[i][j - 1] + 1,                      // Insertion
                    matrix_[i - 1][j - 1] + substitution_cost); // Substitution
            }
        }
        return matrix_[m][n];
    }
};

}; // namespace MB

Typedef super

A useful addition to a derived class is a typedef aliasing the base class as super:

class Derived : public Base
{
private:
    typedef Base super;
};

This allows you to use super to call the base class constructor from the derived class:

    Derived(int i, int j)
        : super(i), j_(j)
    {
    }

You can also use super to call the base class version of a virtual function in a derived class override:

 virtual void Show()
{
    super::Show();
    std::cout << "Derived Show()\n";
}

It means that if you need to add another layer of inheritance, you only need to change the inheritance part of the class declaration and this typedef.

class Derived : public Intermediate
{
private:
    typedef Intermediate super;
};

You should make the typedef private, to prevent it from being inherited and accidentally used from derived classes that do not declare it.

Visual C++ has a non-standard extension __super: __super.

It is available in Java: Using the Keyword super.

Nowadays you should probably use using:

class Derived : public Base
{
private:
    using super = Base;
};

So it should probably be called the "using super =" idiom.

How to find a substring in C++

Say we have the following string:

std::string str = "The quick brown fox jumps over the lazy dog";

And we want to find "fox"

Here are three methods:

  1. Use std::string::find()
  2. Use boost::contains()
  3. Use pystring::find()

Method 1: Use std::string::find

bool found = str.find("fox") != str.npos;

This returns an iterator pointing at the beginning of the substring if found, or std::string::npos otherwise.

Method 2: Use boost::contains

#include <boost/algorithm/string/predicate.hpp>
found = boost::contains(str, "fox");

This has the advantage of returning a boolean.

Reference: Function contains

Method 3: Use pystring::find

#include <pystring.h>
found = pystring::find(str, "fox") != -1;

Reference: imageworks/pystring

Related

Default operator== in C++

At first sight, it seems surprising that there is no compiler-generated default operator== in C++, when there is a compiler-generated default assignment operator and copy constructor. It could simply do a memberwise comparison, just as the assignment operator and copy constructor do a memberwise copy.

The reason is out of compatibility with C. In C, struct comparison is illegal, so a default operator== in C++ would have made C code that shouldn’t compile as C compile, and potentially changed its behaviour. Compatibility is the same reason why C++ does have a default assignment operator and copy constructor, which is ironic given that those are rarely wanted and are often disabled by making them private.

There is a proposal to include default comparison operators in C++17, as described here: A bit of background for the default comparison proposal — Bjarne Stroustrup.

Related

Operator overloading in C++

Looping over the keys and values in a map

Say we have this map:

#include <map>
#include <string>

typedef std::map<std::string, unsigned int> map_string_to_uint;
const size_t n = 12;

map_string_to_uint monthdays;
const char *months[] 
        = {"JAN", "FEB", "MAR", "APR", "MAY", "JUN", "JUL", "AUG", "SEP", "OCT", "NOV", "DEC"};
unsigned int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for (int m = 0; m < n; ++m) {
    monthdays[months[m]] = days[m];
}

And we want to loop over the keys and values.

Method 1: Use an iterator

    for (map_string_to_uint::const_iterator it = monthdays.begin(); it != monthdays.end(); ++it) {
        std::cout << it->first << ": " << it->second << "\n";
    }

Method 2: Use a range-based for loop (C++11)

    for (const auto& pair : monthdays) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

Method 3: Use Boost.Foreach

#include <boost/foreach.hpp>

BOOST_FOREACH(const map_string_to_uint::value_type& pair, monthdays) {
    std::cout << pair.first << ": " << pair.second << "\n";
}

Reference: Boost.Foreach

Why STL iterator ranges go [begin, end)

At first sight, it seems strange that STL iterators go [begin, end), including begin but not end in the range, but when you think about it more you realise that this is exactly the way conventional loops work.

STL iteration loop

A typical STL iteration loop goes:

for (it = begin; it != end; ++it) {
    // do something with *it
}

Note that:

  • The iterator end is not part of the range processed
  • After the end of the loop it is equal to end, i.e., one past the end of the range
  • The size of range traversed is endbegin

Now consider the following loops:

Loop over an array with an index

    int numbers[] = {1, 2, 3, 4, 5, 6};
    const size_t n = sizeof(numbers) / sizeof(int);
    int i;
    for (int i = 0; i < n; ++i) {
        std::cout << numbers[i] << "\n";
    }
    std::cout << i << "\n";

Here, our range of indices processed is [0, n).

  • numbers[n] is not part of the range processed
  • After the end of the loop, i is n, i.e., one past the end of the range
  • The size of range traversed is n - 0 = n , i.e., the end – the beginning

Loop over a string


    const char str[] = "The quick brown fox jumps over the lazy dog";
    for (i = 0; str[i] != '\0'; ++i) {
        std::cout << str[i] << "\n";
    }
    for (const char* c = str; c != '\0'; ++c) {
        std::cout << *str << "\n";
    }

A string is defined by [str[0], '\0'), or [*str, '\0')

  • The '\0' character is not part of the string
  • After the end of the loop, the pointer or index points to the '\0'.
  • The size of range traversed is (position of the '\0') – 0 = strlen(str), i.e., the end – the beginning

Loop over an array of pointers with sentinel

    const char* strings[] = {"apples", "pears", "bananas", "cherries", NULL};
    for (i = 0; strings[i] != NULL; ++i) {
        std::cout << strings[i] << "\n";
    }
    for (const char** pc = strings; *pc != NULL ; ++pc) {
        std::cout << *pc << "\n";
    }

Similarly, here the range is [strings[0], NULL), or [*strings, NULL)

  • The NULL is not considered part of the range processed
  • After the end of the loop, the pointer or index points to the NULL
  • The size of range traversed is (position of the NULL) – 0 = the position of the NULL, i.e., the end – the beginning

Hopefully, this has demonstrated that STL iterators have exactly the same semantics as ordinary loop variables.

I’ll leave the last word to E. W. Dijkstra, with his explanation of Why numbering should start at zero.

Related

Getting the date and time in C++

I use this little function to get a nicely formatted date and time:

#include <ctime>
#include <string>
#include <vector>

std::string stringftime(const char* format = "%c", const struct tm* tm = NULL)
{
    if (tm == NULL) {
        time_t t = std::time(NULL);
        tm = std::localtime(&t);
    }
    const size_t size = 256;
    std::vector<char> vtime(size);
    if (std::strftime(&vtime[0], size, format, tm) == 0) {
        vtime[0] = '\0';
    }
    return &vtime[0];
}

Example of its use:

#include <iostream>

int main (void)
{
    std::cout << stringftime() << "\n";
    std::cout << stringftime("Today is %A, %B %d.") << "\n";
    std::cout << stringftime("The time is %I:%M %p.") << "\n";
}
Fri Sep  9 16:07:58 2016
Today is Friday, September 09.
The time is 04:07 PM.

The format specifiers accepted are listed here: strftime.

Template specialisation with a non-type template parameter

The problem

Say you have a generic matrix class like this with non-type template parameters for the number of rows and columns:

template <typename ElementType, size_t Rows, size_t Columns>
class Matrix
{
    ElementType entries_[Rows][Columns];
    // etc...
};

You would like to create a specialization for a column vector, where the number of columns is always 1. However, the following typedef doesn’t compile:

typedef Matrix<size_t, Rows, 1> ColumnVector;

C++03

In C++03, you have 2 options.
Firstly, you can use inheritance:

template <typename ElementType, size_t Rows>
class ColumnVector : public Matrix<ElementType, Rows, 1>
{
};

Secondly, you could use a class with a nested typedef:

template <typename ElementType, size_t Rows>
struct ColumnVector
{
    typedef Matrix<ElementType, Rows, 1> type;
};

In this case, you could declare a column vector with:

ColumnVector<int, 3>::type vec;

C++11

In C++11, you can use an alias declaration to solve the problem more neatly:

template <typename ElementType, size_t Rows>
using ColumnVector = Matrix<ElementType, Rows, 1>;

This is a good example of how much more powerful the new alias declarations with using are than typedefs.