Реализовать Counting Sort в стиле C++

В C++ советуют вместо массивов везде использовать векторы. Можно каким-то образом в строке int *c = new int[max + 1]; использовать вектор?

Да, примерно так:

std::vector<int> c(max + 1, 0);

Оно же будет и инициализацией нулями.

И надо ли это вообще?

Это Ваша гарантия того, что в случае exception ниже, выделенная память будет освобождена. Т.е. в общем случае да, надо.

В первой части c[in.at(i)]++; я использую функцию at() вместо прямого обращения по индексу in[i], а в конце обращаюсь к элементам напрямую. Какой способ лучше? Например, что в последнем цикле множество функций at() будет очень затруднять чтение кода.

at - генерирует out_of_range exception, в случае, если Вы пытаетесь обратиться к элементу вне размеров массива. Обращение "напрямую" в этом случае приведет к undefined behavior. В остальном они идентичны. На мой взгляд, т.к. Вы точно знаете размеры своего массива и никак не рискуете обратиться вне, и никто, кроме Вас и этого потока этот массив не изменяет, Вы смело можете обращаться "напрямую".

Как еще можно переписать этот код?

Красивый пример предложен в соседнем ответе :)

Я же предложу обратить внимание на возможные проблемы кода.

1) int i = in.size() - 1 - размер массива имеет тип size_t, который с хорошим шансом больше, чем int. И самая печаль, если он имеет ту же разрядность, но, например, unsigned. Это может при определенном размере массива дать Вам отрицательное стартовое значение. И в случае обращения по at(), Вы получите exception, и просто потечете памятью там, где делаете new int, а в случае обращения напрямую, будет undefined behavior, и Ваш процесс, например, полезет взламывать Пентагон :)

2) c[i] = c[i] + c[i - 1]; - теоретически это может привести к переполнению, и получению веселья. Но метод подсчета не используется при большом разбросе значений, а минимум у Вас не устанавливается и по дефолту 0, поэтому на это можно (из соображений здравого смысла) не обращать внимания.

3) Эту часть я бы заменил на более простое.

out.resize(in.size());
//...
for(int i = 1; i < max + 1; i++)
    c[i] = c[i] + c[i - 1];
for(int i = in.size() - 1; i >= 0; i--){
    c[in[i]]--;
    out[c[in[i]]] = in[i];

Вот на это:

out.reserve(in.size());
for(size_t i = 0; i < max + 1; i++) 
    for (size_t j = c[i]; j > 0; --j) 
        out.push_back(i);

Имхо так понятнее, что происходит.

Как правильно писать абстракцию типа данных, которые не являются числами и которые надо сортировать?

Зависит от того, по какому признаку их надо сортировать. Исходя из этого и будет необходимо сформировать целочисленное представление этого признака. Если же признаков для сортировки нет, и надо отсортировать "как-нибудь", лучше всего сразу на месте объявить массив отсортированным. Ну, по какому-то существующему, известному только Вам секретному правилу :)

Простая копирующая сортировка подсчетом может выглядеть так:

#include <algorithm>
#include <numeric>
#include <vector>
// Сортировка подсчетом требует функцию, возвращающую ключ сортировки.
// Identity-функция возвращает переданный ей аргумент без изменений.
// Мы будем использовать ее в качестве функции для ключа по-умолчанию.
const auto identity = [](auto x) { return x; };
using Identity = decltype(identity);
// Сортировка подсчетом использует последовательный доступ для элементов на входе,
// и произвольный доступ для элементов на выходе алгоритма.
template<typename ForwardIterator, typename RandomAccessIterator, typename Key = Identity>
void counting_sort(
    ForwardIterator first, ForwardIterator last, // входная последовательность
    RandomAccessIterator out, // результат
    Key key = identity) // функция, выдающая ключ элемента
{
    // Проверяем что последовательность не пустая.
    if (first == last)
        return;
    // Определяем минимальный и максимальные ключи элементов.
    auto compare = [&](const auto& lhs, const auto& rhs) { return key(lhs) < key(rhs); };
    auto minmax = std::minmax_element(first, last, compare);
    auto min_key = key(*minmax.first);
    auto max_key = key(*minmax.second);
    // Если ключи не отличаются, то последовательность уже отсортирована.
    if (min_key == max_key) {
        std::copy(first, last, out);
        return;
    }
    // Выделяем массив для подсчета элементов.
    // Тут можно оптимизировать потребление памяти, если использовать счетчики меньшие
    // чем size_t, если размер входной последовательности достаточно мал.
    std::vector<std::size_t> count(max_key - min_key + 1);
    // Подсчитываем количество элементов с одинаковым ключом.
    std::for_each(first, last, [&](const auto& x) { ++count[key(x) - min_key]; });
    // Обнуляем первый счетчик и вычисляем частичные суммы.
    // Если после подсчета в count было {2,2,2,2},
    // то после partial_sum там будет   {0,2,4,6},
    // т.е. индексы, по которым должны лежать элементы с одинаковым ключом.
    count[0] = 0;
    std::partial_sum(count.begin(), count.end(), count.begin());
    // Копируем элементы в выходной массив, увеличивая индексы в "count".
    // Копирование можно заменить на перемещение.
    std::for_each(first, last, [&](auto& x) { out[count[key(x) - min_key]++] = x; });
    // Код "count[key(x) - min_key]" встречается два раза, и его можно вынести в отдельную функцию, например
    // auto count_ref = [&](const auto& x) -> std::size_t& { return count[key(x) - min_key]; };
}