Студент

Мартюшев Алексей

Задача

Простой класс String

Состояние

Завершено

Баллов

4

Дедлайн

Назначено

11.03.2020, 12:37

Завершено

01.04.2020, 06:50

Реализовать класс String для работы со строками c применением техники reference counting и copy-on-write. Класс представляет собой динамический массив char'ов с NULL-терминатором на конце.

Справочная информация

Основная идея copy-on-write & reference counting следующая: при копировании и присваивании объектов не происходит полного копирования строк. Копируются только указатели на буфер и увеличивается счетчик ссылок. Но при модификации объекта мы уменьшаем счетчик ссылок и выполняем полное копирование. Важно отметить, что при вызове деструктора, мы уменьшаем счетчик ссылок и если он становится равен нулю, тогда освобождаем динамически выделенную память. В противном случае, ничего не делаем.

Постановка задачи

Реализовать класс String. public и protected методы классов фиксированы, кроме спецификаторов. Т.е. нельзя менять названия методов, а также типы и количество аргументов. НО в этих методах отсутствуют спецификаторы const и static, которые были удалены намеренно. Их необходимо вернуть на место.

private поля и private методы можно добавлять в класс String.

//String.hpp
class String {
public:
    String();
    String(const char* str);
    String(const char* str, size_t n);
    String(size_t n, char c);
    String(const String& str);
    String(const String& str, size_t pos, size_t len = npos);
    virtual ~String();

    size_t size();
    size_t capacity();
    void reserve(size_t n = 0);
    void clear();
    bool empty();

    char& at(size_t pos);
    const char& at(size_t pos) const;

    char& operator[](size_t pos);
    const char& operator[](size_t pos) const;

    char& back();
    const char& back() const;

    char& front();
    const char& front() const;

    String& operator+=(const String& str);
    String& operator+=(const char* str);
    String& operator+=(char c);

    String& operator=(const String& str);
    String& operator=(const char* str);

    String& insert(size_t pos, const String&  str);
    String& insert(size_t pos, const char* str);
    String& insert(size_t pos, size_t n, char c);

    String& erase(size_t pos = 0, size_t len = npos);

    String& replace(size_t pos, size_t len, const String& str);
    String& replace(size_t pos, size_t len, const char* str);
    String& replace(size_t pos, size_t len, size_t n, char c);

    void swap(String& str);
    const char* data();

    size_t find(const String& str, size_t pos = 0);
    size_t find(const char* str, size_t pos = 0);
    size_t find(char c, size_t pos = 0);

    String substr(size_t pos = 0, size_t len = npos);

    int compare(const String& str);
    int compare(const char* str);

    static const size_t npos = -1;

    size_t countRef();
};

• npos -- статическая константа с максимальным значением size_t. Это значением может быть использовано в методах для параметра len, что означает "до конца строки". Также эта константа может быть использована в качестве возвращаемого значения для указания отсутствия совпадений.

• String() -- конструктор по умолчанию.

• String(const char* str) -- конструктор принимающий C-строку. Конструктор выполняет полное копирование строки.

• String(const char* str, size_t n) -- копирует первые n символов из строки str.

• String(size_t n, char c) -- заполняет строку символами c в количестве n штук.

• String(const String& str) -- конструктор копий. Полного копирования не происходит. Применяется техника reference counting.

• String(const String& str, size_t pos, size_t len = npos) -- копирование части строки str начиная с позиции pos и охватывая len символов. Если len равняет npos, то копируем до конца строки str. Если pos больше размера строки, то выбрасывается исключение throw std::out_of_range("message");.

• ~String() -- деструктор. Уменьшаем счетчик ссылок и если он равен нулю, то освобождаем динамически выделенную память, в противном случае, ничего не делаем.

• size() -- возвращает текущий размер строки без учета NULL-терминатора.

• capacity() -- возвращает размер выделенной памяти.

• reserve(size_t n = 0) -- изменение размера выделенной памяти. Если запрашиваемый размер n больше текущего, то перевыделяем память и копируем туда данные. Иначе ничего не делаем. Стоит отметить, что данный метод никак не влияет на размер строки и её содержимое. Также не забываем про copy-on-write идиому.

• clear() -- очищаем строку. Строка становится пустой (с длиной 0). Не забываем про copy-on-write идиому.

• empty() -- проверяет, является ли строка пустой.

• at(size_t pos) -- по индексу возвращает ссылку на символ. В случае выхода за пределы размера строки, метод должен выбросить исключение throw std::out_of_range("message");.

• at(size_t pos) const -- по индексу возвращает константную ссылку на символ. В случае выхода за пределы размера строки, метод должен выбросить исключение throw std::out_of_range("message");. Если pos равняется длине строки, то метод должен вернуть константную ссылку на '\0'.

• operator[](size_t pos) -- оператор доступа к элементу по индексу. Возвращает ссылку на символ. Если pos больше либо равен длине строки, то будет undefined behaviour (неопределенное поведение).

• operator[](size_t pos) const -- оператор доступа к элементу по индексу. Возвращает ссылку на символ. Если pos больше длины строки, то будет undefined behaviour (неопределенное поведение). Если pos равняется длине строки, то оператор должен вернуть константную ссылку на '\0'.

• back() -- возвращает ссылку на последний символ строки. Если строка пустая, то будет undefined behaviour.

• back() const -- возвращает константную ссылку на последний символ строки. Если строка пустая, то будет undefined behaviour.

• front() -- возвращает ссылку на первый символ строки. Если строка пустая, то будет undefined behaviour.

• front() const -- возвращает константную ссылку на первый символ строки. Если строка пустая, то будет undefined behaviour.

• operator+= -- выполняет конкатенацию строк, либо строки и символа. Возвращает ссылку на объект, который вызвал данный оператор.

• operator=(const String& str) -- оператор присваивания. Полного копирования не происходит. Применяется техника reference counting.

• operator=(const char* str) -- оператор присваивания принимающий C-строку. Оператор выполняет полное копирование строки.

• insert -- выполняет вставку строки str в позицию pos. В случае insert(size_t pos, size_t n, char c) происходит вставка символов c в количестве n штук. Если pos больше размера строки, то выбрасывается исключение throw std::out_of_range("message");.

• erase(size_t pos = 0, size_t len = npos) -- выполняет удаление подстроки в строке начиная с позиции pos и охватывая len символов. Если len равняется npos, то удаление происходит с позиции pos до конца строки. Если pos больше размера строки, то выбрасывается исключение throw std::out_of_range("message");.

• replace -- выполняет замену подстроки в строке начиная с позиции pos и охватывая len символов. Если len равняется npos, то удаление происходит с позиции pos до конца строки. Если pos больше размера строки, то выбрасывается исключение throw std::out_of_range("message");.

• swap(String& str) -- обмен строками.

• data() -- возвращает указатель на константные символы строки.

• find -- возвращает индекс подстроки str (или символа c) в строке. pos - задает позицию с которой начинать поиск. Если подстроку не нашли или pos больше размера строки, метод возращает npos.

• substr(size_t pos = 0, size_t len = npos) -- возвращает новую строку созданную из подстроки. Подстрока начинается с позиции pos и охватывает len символов. Если pos больше размера строки, то выбрасывается исключение throw std::out_of_range("message");. Если pos равняется размеру строки, то метод должен вернуть пустую строку.

• compare -- метод для сравнения строк. Применяем лексикографическое сравнение.

• countRef() -- возвращает текущее количество ссылок на строку. Т.е. количество объектов, которые ссылаются на данную строку. Этот метод нужен для unit test'ов.

Требования

1. К public методам, класса String, необходимо добавить спецификаторы static и const. Но только в те места, где это необходимо.
2. public и protected методы классов фиксированы, кроме спецификаторов. Т.е. нельзя менять названия методов, а также типы и количество аргументов.
3. Названия header и source файлов следующие: String.hpp, String.cpp.
4. Написать unit test'ы для реализованных классов.

Примечания

Некоторые предоставленные тесты не проходят, при использовании референсной реализации String. Это происходит из-за разной стратегии резервирования памяти (capacity).Так как в задании не оговорено как/сколько резервировать памяти, то будем считать, что задание выполнено!