Удаление указанных символов из строки - Эффективные методы (сложность времени и пространства)

Question

Вот проблема: удалить указанные символы из заданной строки.

Input: The string is "Hello World!" and characters to be deleted are "lor"
Output: "He Wd!"

Решение этого состоит из двух частей:

1. Определение необходимости удаления данного символа
2. Если это так, то удаление символа

Чтобы решить первую часть, я читаю символы, которые нужно удалить, в std::unordered_map, то есть я анализирую строку «lor» и вставляю каждый символ в хэш-карту. Позже, когда я анализирую основную строку, я посмотрю на эту хэш-карту с каждым символом в качестве ключа, и если возвращаемое значение не равно нулю, то я удаляю символ из строки.

Вопрос 1: Это лучший подход?

Вопрос 2: Что лучше для этой проблемы? std::map или std::unordered_map? Так как я не заинтересован в заказе, я использовал unordered_map. Но есть ли более высокие издержки для создания хэш-таблицы? Что делать в таких ситуациях? Использовать map (сбалансированное дерево) или unordered_map (хеш-таблицу)?

Теперь перейдем к следующей части, то есть удаляем символы из строки. Один из подходов состоит в том, чтобы удалить символ и сдвинуть данные с этой точки назад на одну позицию. В худшем случае, когда нам нужно удалить все символы, потребуется O (n ^ 2).

Второй подход заключается в копировании только необходимых символов в другой буфер. Это потребовало бы выделения достаточного количества памяти для хранения исходной строки и копирования символа за символом, исключая те, которые должны быть удалены. Хотя для этого требуется дополнительная память, это будет операция O (n).

Третий подход - начать чтение и запись с 0-й позиции, увеличивать указатель источника при каждом чтении и увеличивать указатель назначения только при записи. Так как указатель источника всегда будет одинаковым или опережает указатель назначения, я могу записывать поверх одного и того же буфера. Это экономит память и также является операцией O (n). Я делаю то же самое и в конце вызываю resize, чтобы удалить дополнительные ненужные символы?

Вот функция, которую я написал:

// str contains the string (Hello World!)
// chars contains the characters to be deleted (lor)
void remove_chars(string& str, const string& chars)
{
    unordered_map<char, int> chars_map;

    for(string::size_type i = 0; i < chars.size(); ++i)
        chars_map[chars[i]] = 1;

    string::size_type i = 0; // source
    string::size_type j = 0; // destination
    while(i < str.size())
    {
        if(chars_map[str[i]] != 0)
            ++i;
        else
        {
            str[j] = str[i];
            ++i;
            ++j;
        }
    }

    str.resize(j);
}

Вопрос 3: Как можно улучшить эту функцию? Или это лучшее, что мы можем сделать?

Спасибо!

Answer 1

Хорошая работа, теперь изучите стандартные алгоритмы библиотеки и добавьте:

str.erase(std::remove_if(str.begin(), str.end(), boost::is_any_of("lor")), str.end());

Answer 2

Предполагая, что вы изучаете алгоритмы и не интересуетесь библиотечными решениями:

Хеш-таблицы наиболее ценны, когда число возможных ключей велико, но вам нужно хранить только несколько из них. Ваша хеш-таблица будет иметь смысл, если вы удаляете конкретные 32-битные целые числа из последовательностей цифр. Но с символами ASCII это излишне.

Просто создайте массив из 256 bools и установите флаг для символов, которые вы хотите удалить. Он использует только одну инструкцию поиска таблицы на каждый входной символ. Хеш-карта включает в себя как минимум еще несколько инструкций для вычисления хеш-функции. Что касается пространства, они, вероятно, не будут более компактными, когда вы сложите все вспомогательные данные.

void remove_chars(string& str, const string& chars)
{
    // set up the look-up table
    std::vector<bool> discard(256, false);
    for (int i = 0; i < chars.size(); ++i)
    {
        discard[chars[i]] = true;
    }

    for (int j = 0; j < str.size(); ++j)
    {
        if (discard[str[j]])
        {
            // do something, depending on your storage choice
        }
    }
}

Относительно ваших вариантов хранения: выберите между вариантами 2 и 3 в зависимости от того, нужно ли вам сохранять входные данные или нет. 3, очевидно, наиболее эффективен, но вам не всегда нужна процедура на месте.

Answer 3

Вот решение KISS со многими преимуществами:

void remove_chars (char *dest, const char *src, const char *excludes)
{
    do {
        if (!strchr (excludes, *src))
            *dest++ = *src;
    } while (*src++);
    *dest = '\000';
}

Answer 4

Вы можете пинг-понг между strcspn и strspn, чтобы избежать необходимости в хеш-таблице:

void remove_chars(
    const char *input, 
    char *output, 
    const char *characters)
{
    const char *next_input= input;
    char *next_output= output;

    while (*next_input!='\0')
    {
        int copy_length= strspn(next_input, characters);
        memcpy(next_output, next_input, copy_length);

        next_output+= copy_length;

        next_input+= copy_length;
        next_input+= strcspn(next_input, characters);
    }
}