Tag Archives: Strings

Find and replace in C++

The standard C++ string class has 39 member functions, but never the one you need. A find-and-replace function one of those that is missing. Fortunately it can easily be implemented in terms of the find() and replace() methods:

#include <string>
#include <iostream>
#include <climits>

std::string string_replace(const std::string& str, const std::string& match, 
        const std::string& replacement, unsigned int max_replacements = UINT_MAX)
{
    size_t pos = 0;
    std::string newstr = str;
    unsigned int replacements = 0;
    while ((pos = newstr.find(match, pos)) != std::string::npos
            && replacements < max_replacements)
    {
         newstr.replace(pos, match.length(), replacement);
         pos += replacement.length();
         replacements++;
    }
    return newstr;
}

The Boost library has replace_all(), which does the replacement in-place, modifying the original string.

The pystring library has replace(), which not surprisingly works the same way as the Python string.replace() method.

Levenshtein distance in C

The Levenshtein distance is a measure of the similarity of two strings. It is defined as the minimum number of insertions, deletions, and substitutions necessary to transform the first string into the second.

For example, the Levenshtein distance between “CHALK” and “CHEESE” is 4, as follows:

  1. Substitute E for A
  2. Substitute E for L
  3. Substitute S for K
  4. Insert E

The Levenshtein distance can be calculated using a dynamic programming algorithm due to Wagner and Fischer. The algorithm fills a table with the distance between all of the prefixes of the two strings, the final entry being the distance between the two entire strings.

Below is an implementation in C. I have recorded in the matrix cells information about the edits and the previous cell from which each cell was derived to enable tracing back the sequence of edits – the edit script. The function levenshtein_distance() takes two strings, and the address of a pointer to which to assign an array containing the edit script. It returns the Levenshtein distance.

#include <string.h>
#include <stdlib.h>

typedef enum {
    INSERTION,
    DELETION,
    SUBSTITUTION,
    NONE
} edit_type;

struct edit {
    unsigned int score;
    edit_type type;
    char arg1;
    char arg2;
    unsigned int pos;
    struct edit *prev;
};
typedef struct edit edit;

static int min3(int a, int b, int c)
{
    if (a < b && a < c) {
        return a;
    }
    if (b < a && b < c) {
        return b;
    }
    return c;
}

static unsigned int levenshtein_matrix_calculate(edit **mat, const char *str1, size_t len1,
        const char *str2, size_t len2)
{
    unsigned int i, j;
    for (j = 1; j <= len2; j++) {
        for (i = 1; i <= len1; i++) {
            unsigned int substitution_cost;
            unsigned int del = 0, ins = 0, subst = 0;
            unsigned int best;
            if (str1[i - 1] == str2[j - 1]) {
                substitution_cost = 0;
            }
            else {
                substitution_cost = 1;
            }
            del = mat[i - 1][j].score + 1; /* deletion */
            ins = mat[i][j - 1].score + 1; /* insertion */
            subst = mat[i - 1][j - 1].score + substitution_cost; /* substitution */
            best = min3(del, ins, subst);
            mat[i][j].score = best;                  
            mat[i][j].arg1 = str1[i - 1];
            mat[i][j].arg2 = str2[j - 1];
            mat[i][j].pos = i - 1;
            if (best == del) {
                mat[i][j].type = DELETION;
                mat[i][j].prev = &mat[i - 1][j];
            }
            else if (best == ins) {
                mat[i][j].type = INSERTION;
                mat[i][j].prev = &mat[i][j - 1];
            }
            else {
                if (substitution_cost > 0) {
                    mat[i][j].type = SUBSTITUTION;
                }
                else {
                    mat[i][j].type = NONE;
                }
                mat[i][j].prev = &mat[i - 1][j - 1];
            }
        }
    }
    return mat[len1][len2].score;
}

static edit **levenshtein_matrix_create(const char *str1, size_t len1, const char *str2,
        size_t len2)
{
    unsigned int i, j;
    edit **mat = malloc((len1 + 1) * sizeof(edit *));
    if (mat == NULL) {
        return NULL;
    }
    for (i = 0; i <= len1; i++) {
        mat[i] = malloc((len2 + 1) * sizeof(edit));
        if (mat[i] == NULL) {
            for (j = 0; j < i; j++) {
                free(mat[j]);
            }
            free(mat);
            return NULL;
        }
    }
    for (i = 0; i <= len1; i++) {
        mat[i][0].score = i;
        mat[i][0].prev = NULL;
        mat[i][0].arg1 = 0;
        mat[i][0].arg2 = 0;
    }

    for (j = 0; j <= len2; j++) {
        mat[0][j].score = j;
        mat[0][j].prev = NULL;
        mat[0][j].arg1 = 0;
        mat[0][j].arg2 = 0;
    }
    return mat; 
}

unsigned int levenshtein_distance(const char *str1, const char *str2, edit **script)
{
    const size_t len1 = strlen(str1), len2 = strlen(str2);
    unsigned int i, distance;
    edit **mat, *head;

    /* If either string is empty, the distance is the other string's length */
    if (len1 == 0) {
        return len2;
    }
    if (len2 == 0) {
        return len1;
    }
    /* Initialise the matrix */
    mat = levenshtein_matrix_create(str1, len1, str2, len2);
    if (!mat) {
        *script = NULL;
        return 0;
    }
    /* Main algorithm */
    distance = levenshtein_matrix_calculate(mat, str1, len1, str2, len2);
    /* Read back the edit script */
    *script = malloc(distance * sizeof(edit));
    if (*script) {
        i = distance - 1;
        for (head = &mat[len1][len2];
                head->prev != NULL;
                head = head->prev) {
            if (head->type != NONE) {
                memcpy(*script + i, head, sizeof(edit));
                i--;
            }
        }
    }
    else {
        distance = 0;
    }
    /* Clean up */
    for (i = 0; i <= len1; i++) {
        free(mat[i]);
    }
    free(mat);

    return distance;

Here is an example program that finds the distance from CHALK to CHEESE and prints the edit script:

#include <stdlib.h>
#include <stdio.h>

void print(const edit *e)
{
    if (e->type == INSERTION) {
        printf("Insert %c", e->arg2);
    }
    else if (e->type == DELETION) {
        printf("Delete %c", e->arg1);
    }
    else {
        printf("Substitute %c for %c", e->arg2, e->arg1);
    }
    printf(" at %u\n", e->pos);
}

int main(void)
{
    edit *script;
    unsigned int distance;
    unsigned int i;
    const char str1[] = "CHALK";
    const char str2[] = "CHEESE";
    distance = levenshtein_distance(str1, str2, &script);
    printf("Distance is %d:\n", distance);
    for (i = 0; i < distance; i++) {
        print(&script[i]);
    }
    free(script);
    return 0;
}

The output:

Distance is 4:
Substitute E for A at 2
Substitute E for L at 3
Substitute S for K at 4
Insert E at 4

Aho-Corasick algorithm in C++

The Aho-Corasick algorithm constructs a finite-state automaton (FSA) that can match multiple strings simultaneously. It begins by constructing a conventional prefix tree and then adds transition edges that allow the automaton to recover efficiently from failures.

Below is an implementation in C++. The constructor takes a pair of iterators to a sequence of strings, which the automaton will then be able to match. Once the automaton has been constructed, its search() method can be used to search a string of text. It takes an output iterator, to which it writes pairs containing the strings found and their starting positions.

#ifndef AHO_CORASICK_HPP
#define AHO_CORASICK_HPP

#include <queue>
#include <string>
#include <vector>
#include <set>

namespace MB
{

namespace detail
{

// Maximum number of characters in alphabet
static constexpr int MAXCHARS = 256;

struct state
{
    std::set<int> output_function;
    int failure_function;
    std::vector<int> goto_function;
    state()
        : failure_function(-1),
          goto_function(detail::MAXCHARS, -1)
    {
    }
};

} // namespace detail

class ac_automaton
{
public:
    template <class InputIt>
    ac_automaton(InputIt first, InputIt last)
        : states(1)
    {
        // Build the prefix tree
        for (InputIt it = first; it != last; ++it) {
            add_word(*it);
        }
        // Turn it into an automaton
        construct_automaton();
    }

    template <class OutputIt>
    OutputIt search(std::string text, OutputIt it) const
    {
        int current_state = 0;
     
        for (int i = 0; i < text.size(); ++i) {
            current_state = find_next_state(current_state, text[i]);
            if (states[current_state].output_function.size()) {
                for (auto length : states[current_state].output_function) {
                    *it++ = std::make_pair(std::string(text, i - length + 1, length),
                            i - length + 1);
                }
            }
        }
        return it;
    }

private:
    std::vector<detail::state> states;

private:
    void add_word(const std::string &word)
    {
        int current_state = 0;
        // Add to prefix tree
        for (int c : word) {
            if (states[current_state].goto_function == -1) {
                states[current_state].goto_function = states.size();
                states.push_back(detail::state());
            }
            current_state = states[current_state].goto_function;
        }
        // Add to output function for this state
        states[current_state].output_function.insert(word.size());
    }

    void construct_automaton()
    {
        // Complete the goto function by setting it to 0 for each
        // letter that doesn't have an edge from the root
        for (int c = 0; c < detail::MAXCHARS; ++c) {
            if (states[0].goto_function == -1) {
                states[0].goto_function = 0;
            }
        }
     
        // Compute failure and output functions
        std::queue<int> state_queue;
        for (int c = 0; c < detail::MAXCHARS; ++c) {
            if (states[0].goto_function != 0) {
                states[states[0].goto_function].failure_function = 0;
                state_queue.push(states[0].goto_function);
            }
        }
        while (state_queue.size()) {
            int s = state_queue.front();
            state_queue.pop();
     
            for (int c = 0; c < detail::MAXCHARS; ++c) {
                if (states[s].goto_function != -1) {
                    int failure = states[s].failure_function;
                    while (states[failure].goto_function == -1) {
                         failure = states[failure].failure_function;
                    }
                    failure = states[failure].goto_function;
                    states[states[s].goto_function].failure_function = failure;
                    for (auto length : states[failure].output_function) {
                        states[states[s].goto_function].output_function.insert(length);
                    }
                    state_queue.push(states[s].goto_function);
                }
            }
        }
    }
 
    int find_next_state(int current_state, char c) const
    {
        int next_state = current_state;
     
        while (states[next_state].goto_function == -1) {
            next_state = states[next_state].failure_function;
        }
     
        return states[next_state].goto_function;
    }
 
};

} // namespace MB

#endif // AHO_CORASICK_HPP

Here is an example program:

#include <iostream>

#include "aho_corasick.hpp"

int main()
{
    std::string words[] = {"brown", "dog", "fox", "jumps", "lazy", "over", "quick", "the"};
    const size_t len = sizeof(words) / sizeof(words[0]);
    std::string text = "the quick brown fox jumps over the lazy dog";
 
    MB::ac_automaton automaton(words, words + len);
    std::vector<std::pair<std::string, int> > results;

    automaton.search(text, std::back_inserter(results));
    for (auto it = results.begin(); it != results.end(); ++it) {
        std::cout << it->first << " starting at " << it->second << '\n';
    }
 
    return 0;
}

Output:

the starting at 0
quick starting at 4
brown starting at 10
fox starting at 16
jumps starting at 20
over starting at 26
the starting at 31
lazy starting at 35
dog starting at 40

Reference: Biosequence Algorithms, Spring 2005 Lecture 4: Set Matching and Aho-Corasick Algorithm

Count the number of occurences of characters in a string in Python

To count the number of occurrences of a character in a string, use the string’s count() method:

string = 'The quick brown fox jumps over the lazy dog'
print(string.count('z'))
1

Note that you can also count substrings with count():

string = 'spam, eggs, ham, spam, spam, spam'
print(string.count('spam'))
4

To count the number of occurrences of all characters in a string, use a collections.Counter:

string = 'The quick brown fox jumps over the lazy dog'
counter = Counter(string)
print(counter)
Counter({'a': 5, ' ': 5, 'm': 5, ',': 5, 's': 5, 'p': 4, 'g': 2, 'e': 1, 'h': 1})

Finding 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"

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

Trim a string in C

Left trim

To left trim a string, find the length of prefix containing the characters to trim with strspn(), and then move the rest of the string forwards on top of it with memmove(), not forgetting to move the terminating nul character. Note that checking for the prefix being greater than zero will cover the case where the string is empty.

char *ltrim(char *str, const char *seps)
{
    size_t totrim;
    if (seps == NULL) {
        seps = "\t\n\v\f\r ";
    }
    totrim = strspn(str, seps);
    if (totrim > 0) {
        size_t len = strlen(str);
        if (totrim == len) {
            str[0] = '\0';
        }
        else {
            memmove(str, str + totrim, len + 1 - totrim);
        }
    }
    return str;
}

Right trim

To right trim, scan the string from the right and replace any characters to trim with nul characters, until you find a character you want to keep or you run out of string.

char *rtrim(char *str, const char *seps)
{
    int i;
    if (seps == NULL) {
        seps = "\t\n\v\f\r ";
    }
    i = strlen(str) - 1;
    while (i >= 0 && strchr(seps, str[i]) != NULL) {
        str[i] = '\0';
        i--;
    }
    return str;
}

Trim

To trim both ends of a string, just right trim it and then left trim it, or vice-versa.

char *trim(char *str, const char *seps)
{
    return ltrim(rtrim(str, seps), seps);
}

Test program

This tries all of the important cases with a space as the separator.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <trim.h>

size_t maxlen(char **strings, size_t len)
{
    unsigned int i;
    size_t max = 0;
    for (i = 0; i < len; i++) {
        if (strlen(strings[i]) > max) {
            max = strlen(strings[i]);
        }
    }
    return max;
}

int main(void)
{
    char *strings[] = {"", " ", "  " "test", " test", "test ", " test ",
        "  test", "test  ", "  test  "};
    const size_t n = sizeof(strings) / sizeof(char *);
    unsigned int i;
    char *str = malloc(maxlen(strings, n) + 1);
    for (i = 0; i < n; i++) {
        strcpy(str, strings[i]);
        trim(str, NULL);
        printf("%s\n", str);
    }
    free(str);
    return 0;
}

String formatting in C++

Method 1: Use vsnprintf() (C++11 and POSIX)

#include <iostream>
#include <vector>
#include <string>
#include <cstdarg>
#include <cstring>

std::string format(const std::string& format, ...)
{
    va_list args;
    va_start (args, format);
    size_t len = std::vsnprintf(NULL, 0, format.c_str(), args);
    va_end (args);
    std::vector<char> vec(len + 1);
    va_start (args, format);
    std::vsnprintf(&vec[0], len + 1, format.c_str(), args);
    va_end (args);
    return &vec[0];
}

int main()
{
    char str[] = "%s => %d";
    std::cout << string_format(str, "apples", 7) << "\n";
}

Method 2: Use Boost.Format

#include <iostream>
#include <boost/format.hpp>

int main()
{
    char str[] = "%s => %d";
    std::cout <<  boost::str(boost::format(str) % "apples" % 7) << "\n";
}

Reference: Boost Format library

Method 3: Use folly::format()

#include <iostream>
#include <folly/Format.h>

int main()
{
    char str[] = "{} => {}";
    std::cout <<  folly::format(str, "apples", 7) << "\n";
}

Reference: folly/Format.h

Split a string in C

There are two problems with the standard C strtok function, which is used to split strings:

  • It stores the string being split between calls. This means that while a string is in the process of being split, another string cannot be split in the current thread, or any other thread – i.e., strtok is non-reentrant
  • strtokoverwrites the separators in the string being split with nul characters, so the original string is unusable afterwards. i.e., strtok is destructive

Here’s a function to split a string that has neither of the problems of strok. It takes a pointer to a function from the caller – a callback, which is then passed the start address and length of each token found as the string is split.

typedef void(*split_fn)(const char *, size_t, void *);

void split(const char *str, char sep, split_fn fun, void *data)
{
    unsigned int start = 0, stop;
    for (stop = 0; str[stop]; stop++) {
        if (str[stop] == sep) {
            fun(str + start, stop - start, data);
            start = stop + 1;
        }
    }
    fun(str + start, stop - start, data);
}

Here’s how to use it to print the tokens:

#include <stdio.h>

#include <split.h>

void print(const char *str, size_t len, void *data)
{
    printf("%.*s\n", (int)len, str);
}

int main(void)
{
    char str[] = "first,second,third,fourth";
    split(str, ',', print, NULL);
    return 0;
}
first
second
third
fourth

The third argument to split is a void* pointer, which the caller can use to pass in anything it wants to use within its callback during the splitting process, such as a collection to which to add the tokens.

For example, here’s how to add the tokens to a dynamic array:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <split.h>
#include <dynarray.h>

void add_to_dynarray(const char *str, size_t len, void *data)
{
    dynarray *array = data;
    char *token = calloc(len + 1, 1);
    memcpy(token, str, len);
    dynarray_add_tail(array, token);
}

int main(void)
{
    char str[] = "first,second,third,fourth";
    dynarray *array = dynarray_create(0);
    split(str, ',', add_to_dynarray, array);
    dynarray_for_each(array, (dynarray_forfn)puts);
    dynarray_for_each(array, free);
    dynarray_delete(array);
    return 0;
}

See also: How to split a string in C++

Prefixes, suffixes, and substrings in C

Prefixes

To find all prefixes of a string, just find all substrings starting at the beginning of the string of length from 1 to the length of the string. A good way of returning these to the client is to allow the client to pass in a function pointer, which is called for each prefix found:

typedef void(*substring_fn)(const char *, size_t, void *);

void prefixes(const char *str, size_t len, substring_fn fun, void *data)
{
    unsigned int length;
    for (length = 1; length <= len; length++) {
        fun(str, length, data);
    }
}

The client function is given the beginning of the string and a length, rather than a nul-terminated string. This means that the original string does not need to be modified or copied, which is much more efficient. The client can use the length to do something with the string, like printing it using printf with the * format specifier to specify the length:

#include <stdio.h>
#include <string.h>

#include <substring.h>

void print(const char *str, size_t len, void *data)
{
    printf("%.*s\n", (int)len, str);
}

int main(void)
{
    char str[] = "abracadabra";
    prefixes(str, strlen(str), print, NULL);
    return 0;
}

This produces the following output:

a
ab
abr
abra
abrac
abraca
abracad
abracada
abracadab
abracadabr
abracadabra

The third argument to the client function is a void * pointer that the client can use to pass anything it needs into the function. For example, it might pass in a dynamic array and add the prefixes to that:

#include <stdio.h>
#include <string.h>

#include <substring.h>
#include <dynarray.h>

void add_to_dynarray(const char *str, size_t len, void *data)
{
    dynarray *array = data;
    char *token = calloc(len + 1, 1);
    memcpy(token, str, len);
    dynarray_add_tail(array, token);
}

int main(void)
{
    char str[] = "abracadabra";
    dynarray *array = dynarray_create(0);
    prefixes(str, strlen(str), add_to_dynarray, array);
    dynarray_for_each(array, (dynarray_forfn)puts);
    dynarray_for_each(array, free);
    dynarray_delete(array);
    return 0;
}

Suffixes

To find all suffixes of a string, walk a pointer from the beginning of the string to 1 before the end, passing the client the pointer and the length remaining to the end of the string.

void suffixes(const char *str, size_t len, substring_fn fun, void *data)
{
    unsigned int start;
    for (start = 0; start < len; start++) {
        fun(str + start, len - start, data);
    }
}
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Substrings

A substring is simply a prefix of a suffix, or a suffix of a prefix, so you can find all substrings by finding all suffixes and then finding all of their prefixes, or vice-versa. We can use the function pointer interface above for this by wrapping the client function pointer and data in our own structure and passing that from prefixes to suffixes as the third argument as follows:

typedef struct {
    substring_fn fun;
    void *data;
} substrings_data;

void call_suffixes(const char *str, size_t len, void *data)
{
    substrings_data *sd = data;
    suffixes(str, len, sd->fun, sd->data);
}

void substrings(const char *str, size_t len, substring_fn fun, void *data)
{
    substrings_data sd = {fun, data};
    prefixes(str, len, call_suffixes, &sd);
}

This produces the following output:

a
ab
b
abr
br
r
abra
bra
ra
a
abrac
brac
rac
ac
c
abraca
braca
raca
aca
ca
a
abracad
bracad
racad
acad
cad
ad
d
abracada
bracada
racada
acada
cada
ada
da
a
abracadab
bracadab
racadab
acadab
cadab
adab
dab
ab
b
abracadabr
bracadabr
racadabr
acadabr
cadabr
adabr
dabr
abr
br
r
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Unique substrings

The substrings function will produce all substrings, which can include duplicates, as you can see in the output above. You can use a set data structure like a hash table to find just the unique substrings. Again, we can make good use of the function pointer interface by wrapping the client function and the hashtable in a structure, and then passing that to hashtable‘s own iteration function hashtable_for_each2.

void add_to_hashtable(const char *str, size_t len, void *data)
{
    hashtable *table = data;
    char *buf = malloc(len + 1);
    strncpy(buf, str, len);
    buf[len] = '\0';
    buf = hashtable_add(table, buf);
    if (buf) {
        free(buf);
    }
}

void call_substring_fun(const char *substring, void *data)
{
    substrings_data *sd = data;
    sd->fun(substring, strlen(substring), data);
}

void unique_substrings(const char *str, size_t len, substring_fn fun, void *data)
{
    hashtable *table = hashtable_create(7, (hashtable_cmpfn)strcmp);
    substrings(str, len, add_to_hashtable, table);
    substrings_data sd = {fun, data};
    hashtable_for_each2(table, (hashtable_forfn2)call_substring_fun, &sd);
    hashtable_for_each(table, free);
    hashtable_delete(table);
}

The substrings produced are now unique:

abrac
abraca
abracad
acada
ad
adabr
b
brac
bracada
bracadab
cada
dabr
rac
acadabra
c
ca
abra
abracadabra
br
bracadabra
d
dabra
r
racada
racadabra
acad
adabra
bra
cadabra
da
ra
racad
racadabr
aca
acadabr
bracad
cad
ab
abr
abracada
abracadabr
adab
bracadabr
cadab
racadab
a
abracadab
ac
acadab
ada
braca
cadabr
dab
raca

Reverse an array without affecting special characters

I found this little programming challenge here. The task is to take a string and reverse only the alphabetic characters in it, leaving any other characters unaffected.
So, given the string:

a,b$c

The program should output:

c,b$a

I think that the best method is to walk a pair of pointers inwards from both ends of the string at the same time, examining the characters they point to. If the character being examined at either end is not a letter, keep going inwards. Once both characters are letters, swap them. Finish when the pointers meet in the middle.

Here is my implementation in C:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

void swap(char *a, char *b)
{
    char temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(char *str)
{
    char *p1 = str;
    char *p2 = str + strlen(str) - 1;
    while (p1 < p2) {
        while (!isalpha(*p1)) p1++;
        while (!isalpha(*p2)) p2--;
        if (p1 < p2) {
            swap(p1, p2);
            p1++;
            p2--;
        }
    }
}

int main(void)
{
    char str[6];
    strcpy(str, "a,b$c");
    reverse2(str);
    printf("%s\n", str);
    return 0;
}

While I was writing this it occurred to me that it would be nice if you could have a filtered view into the string that hid the special characters, and then you could just reverse what you can see. Then I remembered boost::filter_iterator, and found that it can do just that, so here’s my C++ version using filter_iterator from Boost:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <boost/iterator/filter_iterator.hpp>

struct is_alpha
{
    bool operator()(char c)
    {
        return std::isalpha(c);
    }
};

void reverse(char *str)
{
    const size_t len = std::strlen(str);
    typedef boost::filter_iterator<is_alpha, char*> FilterIter;
    is_alpha predicate;
    FilterIter first(predicate, str, str + len);
    FilterIter last(predicate, str + len, str + len);
    std::reverse(first, last);
}

int main()
{
    char str[6];
    strcpy(str, "a,b$c");
    reverse(str);
    std::cout << str << "\n";
}

Reference: Filter Iterator