10
\$\begingroup\$

I wrote a program that, given a string of text, converts it to Title Case based on certain criteria. I would mainly like to know how I could improve readability and expressiveness, make a more clear API, and improve the efficiency of the algorithms, but any other feedback would also be appreciated. Here is an excerpt of the requirements from

https://www.fluentcpp.com/2018/06/29/7-more-ways-to-get-better-at-c-this-summer-2018-edition/ :

Step 1: Basic Title Case For each word in a sentence, make all of its letters lower case, except the first one that would be in upper case.

There is a list of “exceptions” words that need to be entirely in lower case, including their first letter. This lists includes “at” and “to”, along with another dozen words. For the sake of this project let’s say that the list of exceptions is: a, an, the, at, by, for, in, of, on, to, and, as and or.

Note that in all cases, the first word of the string must start with a capital letter.

Step 2: Title Case with customizations Make the list of exceptions customizable: the library user can add new exceptions, replace the list with their own, or add words that should not be changed by the library.

An additional requirement is that words in all caps should be left as is (“STL” must remain “STL”, and not be changed into “Stl”), but the library user should be able to opt-out of this feature.

TitleCase.h

#pragma once

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

class TitleCase
{
    //title case will not be applied to these words
    std::vector<std::string> m_exceptions = { "a", "an", "the", "at", "by", "for", "in", "of", "on", "to", "and", "as", "or" };
    //acronyms like "STL" will optionally be ignored when applying title case
    bool m_ignore_acronyms = true;

    void apply_title_case(std::string::iterator begin_word, std::string::iterator end_word);

    std::string_view get_word(std::string::iterator begin_word, std::string::iterator end_word);

    template<typename Pred>
    void apply_case_if_pred_met(std::string::iterator begin_word, std::string::iterator end_word, Pred pred)
    {
        if (pred(get_word(begin_word, end_word)))
        {
            apply_title_case(begin_word, end_word);
        }
    }

    template<typename Pred>
    void convert_impl(std::string& text, Pred pred)
    {
        auto begin_word = text.begin();
        auto end_word = std::find(begin_word, text.end(), ' ');
        if (end_word == text.end()) //check if there's only one word in string or string is empty
        {
            if (text.empty()) return;
            apply_case_if_pred_met(begin_word, end_word, pred);
            return;
        }

        while (end_word != text.end())
        {
            apply_case_if_pred_met(begin_word, end_word, pred);

            begin_word = end_word + 1;
            end_word = std::find(begin_word, text.end(), ' ');
        }
    }
public:
    TitleCase() = default;
    TitleCase(bool ignore_acronyms) : m_ignore_acronyms{ ignore_acronyms } {}
    TitleCase(const std::vector<std::string>& exceptions, bool ignore_acronyms = true) : m_exceptions(exceptions), m_ignore_acronyms(ignore_acronyms) {}

    void convert(std::string& text);

    std::string converted_copy(const std::string& text);

    bool is_exception(std::string_view str);
    bool is_acronym(std::string_view word);

    void ignore_acronyms(bool b) { m_ignore_acronyms = b; }

    template<typename T>
    void add_exception(T&& exception) { m_exceptions.emplace_back(std::forward<T>(exception)); }

    template<typename T>
    void remove_exception(T&& exception)
    {
        m_exceptions.erase(std::remove(m_exceptions.begin(), m_exceptions.end(), std::forward<T>(exception)), m_exceptions.end());
    }

    void replace_exceptions(const std::vector<std::string>& exceptions)
    {
        m_exceptions = exceptions;
    }

    const auto& exceptions()
    {
        return m_exceptions;
    }
};

TitleCase.cpp

#include "TitleCase.h"

#include <algorithm>
#include <cctype>

void TitleCase::apply_title_case(std::string::iterator begin_word, std::string::iterator end_word)
{
    *begin_word = std::toupper(*begin_word);
    std::for_each(++begin_word, end_word, [](char& c) { c = std::tolower(c); });
}

void TitleCase::convert(std::string & text)
{
    if (m_ignore_acronyms)
    {
        convert_impl(text, [this](std::string_view word) { return !is_exception(word) && !is_acronym(word); });
    }
    else
    {
        convert_impl(text, [this](std::string_view word) { return !is_exception(word); });
    }
}

std::string TitleCase::converted_copy(const std::string& text)
{
    auto text_copy = text;
    convert(text_copy);
    return text_copy;
}

bool TitleCase::is_exception(std::string_view word)
{
    return std::find(m_exceptions.begin(), m_exceptions.end(), word) != m_exceptions.end();
}

bool TitleCase::is_acronym(std::string_view word)
{
    return std::all_of(word.begin(), word.end(), [](char c) { return std::isupper(c); });
}

std::string_view TitleCase::get_word(std::string::iterator begin_word, std::string::iterator end_word)
{
    const char* begin_word_ptr = &(*begin_word);
    std::string_view::size_type word_size = std::distance(begin_word, end_word);
    auto word = std::string_view{ begin_word_ptr, word_size };
    return word;
}
\$\endgroup\$
11
\$\begingroup\$

It's cool to see someone taking on Jonathan Boccara's challenges!

Overview

The key thing with this challenge was not actually doing it - the actual problem itself is not all that hard. The key thing is designing an easy-to-use interface.

As a C++ programmer, the interface I would like for a job like this is simply:

auto result = title_case(input);

Or to title-case in-place:

auto text = "some text"s;
title_case_inplace(text);

Or something similar (maybe the in-place version is just called title_case and the other version is title_case_copy, for example).

Here's what it looks like to use your interface:

auto title_caser = TitleCase{};
auto result = title_caser.converted_copy(input);

// Or, as a one-liner:
auto result = TitleCase{}.converted_copy(input);

The in-place version is:

auto text = "some text"s;
auto title_caser = TitleCase{};
title_caser.convert(text);

// Or, as a one-liner:
TitleCase{}.convert(text);

That's not a very handy interface.

There are also performance issues. If I do:

auto text = "some text"; // NOTE: text is a char array, not a std::string

auto title_caser = TitleCase{};
auto result = title_caser.converted_copy(text);

Then under the hood, the result string is being created - as I would expect... but another string is also being created because text has be to converted to a string... and then in the class a whole vector of strings is being created. That's a lot of things being constructed and allocated just to convert a char array to a string and title case it!

I would suggest a couple important design changes right up from:

  • The interfaces should either take string_view or just string - not string const&. Normally string_view would be the best choice, but since you're constructing a string for the return value anyway, you might as well take the string as input and modify it in-place - you won't need to do a single allocation! (And if you do it that way, you don't even need an in-place version, because you can effectively do an in-place title-casing with the cost of just two moves.)
  • Don't try to jam everything into a single class. This is called the "god object" design pattern, and it is an anti-pattern. Because your TitleCase class has to be all things to all people, it has to dynamically create the exception list every time... even when it's just using the default exception list. In fact, if I make my own exception list, it will have be to copied unnecessarily into the class, rather than just being used as-is.

Step back and consider the interface first, before writing a single line of code. Think of it from a user perspective.

For example - and you don't need to copy this, because it's not the "right" answer (there is no "right" answer) - here is one possible interface:

// The most basic use case (step 1) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
auto title_case(std::string text) -> std::string;

// Use a custom exception list (step 2a) ~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Take the exception list as a forward range of string_view-like
// objects.
template <typename ForwardRange>
auto title_case(std::string text, ForwardRange const& exceptions) -> std::string;

// Handy helper function to get the default exception list so the
// user can inspect it or modify it as they please.
constexpr auto title_case_default_exceptions_list() noexcept -> std::span<std::string_view>;
// std::span requires C++20; before that you'd have to use gsl::span

// Opt-out of ignoring all-caps (step 2b) ~~~~~~~~~~~~~~~~~~~~~~~~~~
auto title_case(std::string text, bool ignore_all_caps) -> std::string;

// With custom exceptions list.
template <typename ForwardRange>
auto title_case(std::string text, bool ignore_all_caps, ForwardRange const& exceptions) -> std::string;

// BONUS! Generalize using policy class (step 3) ~~~~~~~~~~~~~~~~~~~
class TitleCasePolicy
{
    // In this class you'd define functions like:
    //    find_next_word -> returns the start and end of the next word (this could be defined in a base class, because it's very reusable)
    //    transform_word -> for title-casing, capitalize first word unless it's all-caps or in the exception list
    //    transform_spaces -> for title-casing, do nothing (but for snake-casing, will convert spaces to underscore)
};

class TitleCaseIncludingAllCapsPolicy : public TitleCasePolicy
{
    // all you'd need to do is override transform_word and also title-case all-caps words
};

template <typename TransformWordsPolicy>
auto transform_words(std::string text, TransformWordsPolicy&& policy) -> std::string;

And then you can look at the interface and define more specific functions in terms of more general ones. For example, the step 1 function can easily be defined in terms of the step 2a functions:

auto title_case(std::string text) -> std::string
{
    return title_case(std::move(text), title_case_default_exceptions_list());
}

The step 2a functions can be defined in terms of the step 2b functions, and so on.

And then you can even add more flexible interfaces, like iterator and range interfaces:

template <typename InputIterator, typename Sentinel, typename OutputIterator>
auto title_case(InputIterator first, InputIterator last, OutputIterator out) -> OutputIterator;

template <typename InputRange, typename OutputIterator>
auto title_case(InputRange&& in, OutputIterator out) -> OutputIterator;

and so on, using proper constraints, etc..

This is just a very rough idea, of course - there's a lot you'd need to figure out on your own to actually implement it sensibly. And this may not be the best interface at all! But that's what the challenge is all about. It's not about implementing a title-case algorithm... it's about designing a good interface. That's what you should spend 95% of your time thinking about. Actually title-casing a string is trivial.

On with the code review!

TitleCase.h

#pragma once

This is not standard C++ is not entirely portable. Worse, even when it "works", it doesn't really work. Use include guards instead.

std::vector<std::string> m_exceptions = { "a", "an", "the", ...

There is no real reason why this needs to be a data member of the class. If you think about it, the title case algorithm doesn't need to own the exception list. It just needs to know the exception list. In other words, it just needs a reference of some kind to the list. And you can change the list that's used simply by changing the reference.

You can still have this as a static data member of the class. That way it's not constructed every time an instance is. (Of course, in that case you'd probably want it to be const, so the global default list can't be changed.)

Simply moving this out of the class will net you immediate gains. Your class should construct hundreds of times faster, easily, and in the most common case it will be a pure gain.

But there's more!

Why does the exceptions list need to be a vector<string>. Why can't it be a vector<string_view> or list<string>?

If you modify the class or the actual conversion functions to work with iterators, you can take anything as the exceptions list. You can still have default versions of the conversion functions that aren't templates, that use the default exceptions list, and then versions that are templates that can work with anything.

If you do that - if you allow the exceptions list to be anything - then you can make the default exceptions list constexpr!

inline constexpr auto exceptions = std::array{ std::string_view{"a"}, std::string_view{"an"}, std::string_view{"the"}, ...

That could be the first step to offering constexpr versions of the title case algorithm. With no vector or string members, TitleCase itself could be a literal type (which means it could be mostly or all constexpr).

void apply_title_case(std::string::iterator begin_word, std::string::iterator end_word);

This function might be better defined as a template, for a couple reasons. It would prevent binding your interface to std::string, and lead to a more flexible design.

In both cases, they could be rewritten so that they don't force an in-place modification design. For example, apply_title_case() would be:

template <typename InputIterator, typename OutputIterator>
void apply_title_case(InputIterator first, InputIterator last, OutputIterator out) -> OutputIterator;

And you could still do an in-place modification by doing:

auto word = "word"s;
apply_title_case(word.cbegin(), word.cend(), word.begin());

With optimization on, there should be no efficiency lost by doing it this way.

But you would also be able to support more advanced cases, including situations where changing the case of a letter means changing the number of bytes:

auto word = "\xC3\x9F"s; // lower case "ß", two UTF-8 bytes... now uppercase is "ẞ", three UTF-8 bytes
auto result = std::string{};
apply_title_case(word.cbegin(), word.cend(), std::back_inserter(result));
// could correctly leave result as the 3-byte string "\xE1\xBA\x9E", or "ẞ" in UTF-8

Next:

std::string_view get_word(std::string::iterator begin_word, std::string::iterator end_word);

Correct me if I'm wrong, but the entire purpose of this function seems to be just std::string_view(&(*begin_word), std::distance(begin_word, end_word)). It should probably have a more honest name, like "convert to string view".

template<typename Pred>
void apply_case_if_pred_met(std::string::iterator begin_word, std::string::iterator end_word, Pred pred)

Since you're already working with a template here - and with convert_impl - you might as well just go all in and use templated iterators throughout. You could even use iterators in the predicate, eliminating the need for get_word():

template <typename ForwardIterator, typename OutputIterator, typename Pred>
auto apply_case_if_pred_met(ForwardIterator begin_word, ForwardIterator end_word, OutputIterator out, Pred pred) -> OutputIterator
{
    if (pred(begin_word, end_word))
        out = apply_title_case(begin_word, end_word, out);
    return out;
}

Same idea goes for convert_impl(), which already uses iterators internally, and could be trivially changed to have an iterator interface.

TitleCase() = default;
TitleCase(bool ignore_acronyms) : m_ignore_acronyms{ ignore_acronyms } {}

If you remove the data member for exceptions, these can both be constexpr and noexcept.

So how would you handle the exceptions then?

Well, one possibility (and there are many - you'll have to decide what's the best interface) is to make TitleCase a template class with iterator members that point to the begin and end of the exceptions list. By default, it will use the default exceptions list, but a user can provide a different exceptions list if they want.

void convert(std::string& text);

std::string converted_copy(const std::string& text);

bool is_exception(std::string_view str);
bool is_acronym(std::string_view word);

void ignore_acronyms(bool b) { m_ignore_acronyms = b; }

Most of these functions can be const, unless you want to imply there is internal state being modified. And some can possibly noexcept and even constexpr.

All of the exceptions management functions would be superfluous if the exceptions list wasn't in the class (which it shouldn't be for other reasons). However....

template<typename T>
void remove_exception(T&& exception)
{
    m_exceptions.erase(std::remove(m_exceptions.begin(), m_exceptions.end(), std::forward<T>(exception)), m_exceptions.end());
}

You don't really gain anything by using perfect forwarding here. You might as well just take T const& and forget std::forward(). On the other hand:

void replace_exceptions(const std::vector<std::string>& exceptions)
{
    m_exceptions = exceptions;
}

You could potentially gain a lot from taking the argument as just vector<string>, no const&, and std::move()ing it into m_exceptions. There are situations were taking vector sink arguments by const& is more efficient, but that's a pretty wacky use case where you're repeatedly re-assigning the vector... and that doesn't seem likely here.

TitleCase.cpp

void TitleCase::apply_title_case(std::string::iterator begin_word, std::string::iterator end_word)
{
    *begin_word = std::toupper(*begin_word);
    std::for_each(++begin_word, end_word, [](char& c) { c = std::tolower(c); });
}

I would recommend incrementing begin_word the moment it's assigned, to, like this:

*begin_word++ = std::toupper(*begin_word);
std::for_each(begin_word, end_word, [](char& c) { c = std::tolower(c); });

But even better would be to have a dedicated output iterator:

auto out = begin_word; // not a problem unless begin_word is an input iterator
*out++ = std::toupper(*begin_word++);
out = std::transform(begin_word, end_word, out, [](char& c) { c = std::tolower(c); });

Now the algorithm can be transformed into something more <algorithm>-ish easily.

std::string TitleCase::converted_copy(const std::string& text)
{
    auto text_copy = text;
    convert(text_copy);
    return text_copy;
}

Since you're copying text anyway, you might as well just take it by value:

std::string TitleCase::converted_copy(std::string text)
{
    convert(text);
    return text;
}

That could give you an efficiency boost, because users can move strings into the function - no copies will happen at all! In fact, if you did that:

auto text = "some text"s;
/*...*/.convert(text);

// and

auto text = "some text"s;
text = /*...*/.converted_copy(std::move(text));

will both have functionally identical performance. (The latter will cost just two moves extra... but string moves are dirt cheap, and at least one is almost certainly going to be elided away, probably both.)

Summary

  • Boccara's real motive with this challenge is all about designing a good interface. Actually doing the title-casing is pretty trivial; the "tricky" part is thinking of a way to satisfy the Stroustrupian ideal of "make simple things simple", and "make interfaces easy to use right, hard to use wrong".

    Think of the problem first as a user of your code, rather than a maintainer. Start from how a user would want to title case things. Think of all the different use cases a user might be approaching your code from. The "natural" or "default" usage should be... natural and default - something like auto result = title_case(input);. Other obvious uses should be supported too. For example:

    • Title-casing a char array and writing the result to cout could be as easy as title_case(input, std::ostreambuf_iterator<char>{cout});, with no unnecessary string allocations.

    • Or I might want to read the exception list in from a file as a deque<string>, rather than a vector<string> (there are good reasons for using a deque for that kind of thing), and I'd like to do auto result = title_case(input, begin(exceptions), end(exceptions)); (or maybe with a range interface: auto result = title_case(input, exceptions);).

    • I might want to do title-casing in a language where characters are not 1 byte in size, or where there's not a 1-to-1 match between the size of uppercase and lowercase characters. I might want to use more advanced functions for toupper() and tolower(), and for comparisons (to handle case-folding comparisons, for example) - for example, I might want to use something like ICU.

    • I might want to do title-casing at compile time! Could it be constexpr?

    • Having iterator versions is very handy, but what kind of iterators should they take? Forward iterators? Are input iterators practical?

    Note that you don't actually need to support ALL of these use cases if you don't want to... and in fact, supporting everything might get a little insane. It's your code; you decide what it will and won't support. The point is just to think about what your interface might need to look like to support the use cases you want to support.

    Figuring out the interface is the challenge here. Don't write a line of code until you've done that.

  • Don't try to make one class that does everything. That's the "god object" pattern, and it usually just turns into a mess. Delegate different use cases to different classes/functions, and use static (templates, function overloading) or run-time (virtual functions) polymorphism to handle them all. That also makes reusing large chunks of the code feasible (for Boccara's step 3).

  • Don't tie yourself to certain types unnecessarily. There are many, many good reasons why a user might want to have their exception list as something other than a vector<string>, or do title-casing on things that aren't std::strings. std::string_view is a very good start to making a string interface more generic.

  • It's generally wise to start from an <algorithm>-like interface, using iterators. Once you have that, it is so easy to build anything else on top of it, often with no loss in efficiency. And <algorithm>-style functions are just what C++ programmers are used to.

\$\endgroup\$
  • \$\begingroup\$ Thanks for this advice. I learned a lot from reworking my program and studying your answer. \$\endgroup\$ – Equilibrium Jul 8 '18 at 17:27
4
\$\begingroup\$

First, call it “English Title Case” so it is clear that it is hard-coded for this rule set. A function named TitleCase ought to use the current locale and/or have parameters specifying the language and culture.

void convert(std::string& text);

You are converting in-place I guess. Why not allow any kind of character range, not just a std::string? I see you are using string_view in other places.

: m_exceptions(exceptions), m_ignore_acronyms(ignore_acronyms)

You used old-style (parens) here, though you used uniform initialization syntax in the previous constructor.

void replace_exceptions(const std::vector<std::string>& exceptions)
{
    m_exceptions = exceptions;
}

This one doesn’t have an rvalue form. That would be handy if you built the list from another information model for the sole purpose of passing to this function.

*begin_word = std::toupper(*begin_word);
std::for_each(++begin_word, end_word, [](char& c) { c = std::tolower(c); });

So, you must be using an 8-bit character set. And, you are using the currently set locale even though your rule base is hard-coded for English.

Note that the proper way to call the to_upper and to_lower functions involves casting to unsigned char. See https://en.cppreference.com/w/cpp/string/byte/toupper

void TitleCase::convert(std::string & text)
{
    if (m_ignore_acronyms)
    {
        convert_impl(text, [this](std::string_view word) { return !is_exception(word) && !is_acronym(word); });
    }
    else
    {
        convert_impl(text, [this](std::string_view word) { return !is_exception(word); });
    }
}

You are duplicating almost everything except one little bit. It would be cleaner to (at least) choose the lambda conditionally but call convert_impl only once.

The use of the lambda and a template that takes a predicate is very general, but you do not expose such generality. Having the test built-in and the test for acronym guarded by a test of the ignore_acronyms flag would be much simpler. If you do want to provide a general predicate form, then just having a single member function as the predicate used for the built-in case is enough.

std::string TitleCase::converted_copy(const std::string& text)
{
    auto text_copy = text;
    convert(text_copy);
    return text_copy;
}

I don’t think that is really necessary. The user can just as easily copy the string.


In general, you are making good use of library features, and are using a modern style. I’d say it’s good.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.