C ++ - Проверьте, содержит ли один массив строк все элементы другого - PullRequest
Новая
       22

C ++ - Проверьте, содержит ли один массив строк все элементы другого

1 голос
/ 21 марта 2012

Я недавно портировал приложение Python на C ++, но теперь не могу понять, как я могу портировать определенную функцию. Вот соответствующий код Python: 

def foo(a, b): # Where `a' is a list of strings, as is `b'
    for x in a:
        if not x in b:
            return False

    return True

Я хочу иметь похожую функцию: 

bool
foo (char* a[], char* b[])
{
    // ...
}

Какой самый простой способ сделать это? Я пытался работать с алгоритмами STL, но не могу заставить их работать. Например, в настоящее время у меня есть это (используя типы glib): 

gboolean
foo (gchar* a[], gchar* b[])
{
    gboolean result;

    std::sort (a, (a + (sizeof (a) / sizeof (*a))); // The second argument corresponds to the size of the array.
    std::sort (b, (b + (sizeof (b) / sizeof (*b)));

    result = std::includes (b, (b + (sizeof (b) / sizeof (*b))),
                            a, (a + (sizeof (a) / sizeof (*a))));

    return result;
}

Я более чем готов использовать возможности C ++ 11.

Ответы [ 5 ]

3 голосов
/ 21 марта 2012

Я просто собираюсь добавить несколько комментариев к тому, что другие подчеркнули, и дать лучший алгоритм для того, что вы хотите.

Не используйте указатели здесь . Использование указателей не делает это с ++, это делает плохое кодирование. Если у вас есть книга, которая научила вас c ++ таким образом, выбросьте ее. То, что у языка есть особенность, не означает, что его следует использовать везде, где вы можете . Если вы хотите стать профессиональным программистом, вам нужно научиться использовать соответствующие части ваших языков для любого конкретного действия. Когда вам нужна структура данных, используйте ту, которая соответствует вашей деятельности. Указатели не являются структурами данных, они являются ссылочными типами, используемыми, когда вам нужен объект с временем жизни состояния, т.е. когда объект создается в одном асинхронном событии и уничтожается в другом. Если объект проживает свое время жизни без какого-либо асинхронного ожидания, он может быть смоделирован как объект стека и должен быть. Указатели никогда не должны подвергаться коду приложения, не будучи обернутым в объект, потому что стандартные операции (как новые) генерируют исключения, и указатели не очищают себя. Другими словами, указатели всегда должны использоваться только внутри классов и только тогда, когда необходимо реагировать динамически созданными объектами на внешние события класса (которые могут быть асинхронными).

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

Не сортировать вектор здесь . Это просто странно, потому что это не очень хороший перевод с вашей первоначальной проблемы, и я не уверен, откуда она взялась. Не оптимизируйте рано, но не пессимируйте рано, выбрав плохой алгоритм. Здесь необходимо искать каждую строку внутри другой коллекции строк. Сортированный вектор является инвариантом (поэтому, опять же, подумайте о том, что нужно инкапсулировать) - вы можете использовать существующие классы из библиотек, такие как boost или roll свои собственные. Однако немного лучше в среднем использовать хеш-таблицу. С поиском с амортизацией O (N) (с размером N строки поиска - помните, что это число амортизированных сравнений за O (1), а для строк это O (N)), естественный первый способ перевода: Строка "должна сделать unordered_set<string> вашим b в алгоритме. Это меняет сложность алгоритма с O (NM log P) (теперь N - это средний размер строк в a, M - размер коллекции a и P - размер коллекции b), до O ( NM). Если коллекция b становится большой, это может быть весьма экономно.

Другими словами 

gboolean foo(vector<string> const& a, unordered_set<string> const& b)

Обратите внимание, теперь вы можете передавать константу в функцию. Если вы создаете свои коллекции с учетом их использования, у вас часто есть потенциальная дополнительная экономия в будущем.

Смысл этого ответа в том, что вы действительно никогда не должны иметь привычку писать код, подобный опубликованному. Жаль, что есть несколько действительно (действительно) плохих книг, которые учат кодированию с такими строками, и это настоящий позор, потому что нет необходимости когда-либо выглядеть так ужасно. Он поддерживает идею о том, что c ++ является сложным языком, когда в нем есть действительно хорошие абстракции, которые делают это проще и с лучшей производительностью, чем многие стандартные идиомы в других языках. Примером хорошей книги, которая учит вас, как использовать всю мощь языка, чтобы не создавать вредных привычек, является «Ускоренный C ++» Кенига и Му.

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

2 голосов
/ 21 марта 2012

Ваша первая проблема связана с тем, как массивы обрабатываются (не) в C ++. Массивы живут своего рода очень хрупким теневым существованием, где, если вы посмотрите на них забавным образом, они преобразуются в указатели. Ваша функция не требует двух указателей на массивы, как вы ожидаете. Требуется два указателя на указатели.

Другими словами, вы теряете всю информацию о размере массивов. sizeof(a) не дает вам размер массива. Он дает вам размер указателя на указатель.

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

gboolean foo (gchar** a, int a_size, gchar** b, int b_size)

В качестве альтернативы, и гораздо приятнее, вы можете использовать векторы вместо массивов: 

gboolean foo (const std::vector<gchar*>& a, const std::vector<gchar*>& b)

Векторы - это массивы динамического размера, и поэтому они знают свой размер. a.size() даст вам количество элементов в векторе. Но они также имеют две удобные функции-члены, begin() и end(), предназначенные для работы со стандартными библиотечными алгоритмами.

Итак, чтобы отсортировать вектор: 

std::sort(a.begin(), a.end());

И аналогично для std::includes.

Ваша секунда проблема в том, что вы работаете не со строками, а с указателями символов. Другими словами, std::sort будет сортировать по адресу указателя, а не по содержимому строки.

Опять же, у вас есть два варианта:

Если вы настаиваете на использовании указателей на символы вместо строк, вы можете указать пользовательский компаратор для std::sort (используя лямбду, потому что вы упомянули, что с ними все в порядке) 

std::sort(a.begin(), a.end(), [](gchar* lhs, gchar* rhs) { return strcmp(lhs, rhs) < 0; });

Аналогично, std::includes принимает необязательный пятый параметр, используемый для сравнения элементов. Та же самая лямбда могла быть использована там.

В качестве альтернативы, вы просто используете std::string вместо указателей на символы. Тогда работает компаратор по умолчанию: 

gboolean
foo (const std::vector<std::string>& a, const std::vector<std::string>& b)
{
    gboolean result;

    std::sort (a.begin(), a.end());
    std::sort (b.begin(), b.end());

    result = std::includes (b.begin(), b.end(),
                            a.begin(), a.end());

    return result;
}

Проще, чище и безопаснее.

1 голос
/ 21 марта 2012

Наивная транскрипция версии Python будет: 

bool foo(std::vector<std::string> const &a,std::vector<std::string> const &b) {
    for(auto &s : a)
        if(end(b) == std::find(begin(b),end(b),s))
            return false;
    return true; 
}

Оказывается, сортировка ввода очень медленная. (И это неправильно в лице дублирующих элементов.) Даже наивная функция обычно намного быстрее. Это еще раз показывает, что преждевременная оптимизация - корень всего зла.

Вот версия unordered_set, которая обычно несколько быстрее, чем наивная версия (или была для протестированных значений / шаблонов использования): 

bool foo(std::vector<std::string> const& a,std::unordered_set<std::string> const& b) {
    for(auto &s:a)
        if(b.count(s) < 1)
            return false;
    return true;
}

С другой стороны, если векторы уже отсортированы и b относительно мал (для меня менее 200k), тогда std::includes очень быстро. Поэтому, если вы заботитесь о скорости, вам просто нужно оптимизировать данные и схему использования, с которыми вы на самом деле имеете дело.

1 голос
/ 21 марта 2012

В вашем примере фрагмента использование std::includes не имеет смысла, поскольку оно будет использовать operator< для сравнения ваших элементов.Если вы не храните одинаковые указатели в обоих ваших массивах, операция не даст желаемого результата.

Сравнение адресов - это не то же самое, что сравнение истинного содержимого вашего c-style-strings .

Вам также нужно будет снабдить std::sort необходимым компаратором, предпочтительно std::strcmp (завернутым в функтор ).

В настоящее время он страдает от той же проблемы, что и использование std::includes, он сравнивает адреса вместо содержимого ваших c-style-strings .

Этой всей "проблемы" можно было бы избежать, используя std::string s и std::vector s.

Пример фрагмента 

#include <iostream>
#include <algorithm>
#include <cstring>

typedef char gchar;

gchar const * a1[5] = {
  "hello", "world", "stack", "overflow", "internet"
};

gchar const * a2[] = {
  "world", "internet", "hello"
};

... 

int
main (int argc, char *argv[])
{
  auto Sorter = [](gchar const* lhs, gchar const* rhs) {
    return std::strcmp (lhs, rhs) < 0 ? true : false;
  };

  std::sort (a1, a1 + 5, Sorter);
  std::sort (a2, a2 + 3, Sorter);

  if (std::includes (a1, a1 + 5, a2, a2 + 3, Sorter)) {
    std::cerr << "all elements in a2  was   found in a1!\n";
  } else {
    std::cerr << "all elements in a2 wasn't found in a1!\n";
  }
}

вывод 

all elements in a2  was   found in a1!
1 голос
/ 21 марта 2012

Сортировка в версии C ++ не работает, потому что она сортирует значения указателя (сравнивая их с std::less, как и со всем остальным). Вы можете обойти это, предоставив правильный функтор сравнения. Но почему вы на самом деле не используете std::string в коде C ++? Строки Python - это реальные строки, поэтому имеет смысл портировать их как реальные строки.

...