а оно по стандарту разве не должно быть равно 0?

Для людей, которые форвардят вместо реплая, есть отдельный котел в аду

У вконтактика вступительная задачка при подаче на вакуху: Вашей программе в качестве аргумента будет передано имя файла, в котором будет находиться множество строк (ASCII символы с кодами от 32 до 127). Далее Ваша программа должна считывать строки из stdin, пока не придет строка "exit". После каждой считанной строки Ваша программа должна выводить в stdout строку "YES" или "NO" в зависимости от того, встречается данная строка в переданном файле или нет. Размер файла со словарем не превосходит 128мб. У меня 3 варианта: 1) Загнать все строки в память в плоский массив, рядом создать массив указателей на эти строки, отсортировать массив указателей по возрастанию строк и искать бинарным поиском, O(log n) 2) Загнать все строки в память в плоский массив, напихать этих строк в хеш-таблицу (физически напихать указателей на эти строки в хеш-таблицу), искать за O(1) 3) Захерачить все строки в ахо-корасика, искать за O(1), но память раздует из-за построения графа. Ещё варианты?

У вконтактика вступительная задачка при подаче на вакуху: Вашей программе в качестве аргумента будет передано имя файла, в котором будет находиться множество строк (ASCII символы с кодами от 32 до 127). Далее Ваша программа должна считывать строки из stdin, пока не придет строка "exit". После каждой считанной строки Ваша программа должна выводить в stdout строку "YES" или "NO" в зависимости от того, встречается данная строка в переданном файле или нет. Размер файла со словарем не превосходит 128мб. У меня 3 варианта: 1) Загнать все строки в память в плоский массив, рядом создать массив указателей на эти строки, отсортировать массив указателей по возрастанию строк и искать бинарным поиском, O(log n) 2) Загнать все строки в память в плоский массив, напихать этих строк в хеш-таблицу (физически напихать указателей на эти строки в хеш-таблицу), искать за O(1) 3) Захерачить все строки в ахо-корасика, искать за O(1), но память раздует из-за построения графа. Ещё варианты?

set? или просто онлайн проверять?

set? или просто онлайн проверять?

Там похоже требование - без C++ писать на голимых сях. Сомнительно удовольствие конечно хеш-табицу херачить на сях.

У вконтактика вступительная задачка при подаче на вакуху: Вашей программе в качестве аргумента будет передано имя файла, в котором будет находиться множество строк (ASCII символы с кодами от 32 до 127). Далее Ваша программа должна считывать строки из stdin, пока не придет строка "exit". После каждой считанной строки Ваша программа должна выводить в stdout строку "YES" или "NO" в зависимости от того, встречается данная строка в переданном файле или нет. Размер файла со словарем не превосходит 128мб. У меня 3 варианта: 1) Загнать все строки в память в плоский массив, рядом создать массив указателей на эти строки, отсортировать массив указателей по возрастанию строк и искать бинарным поиском, O(log n) 2) Загнать все строки в память в плоский массив, напихать этих строк в хеш-таблицу (физически напихать указателей на эти строки в хеш-таблицу), искать за O(1) 3) Захерачить все строки в ахо-корасика, искать за O(1), но память раздует из-за построения графа. Ещё варианты?

https://brestprog.neocities.org/lections/trie.html

щас бы БОР построить

на 128 метрах текста

Ну Trie это почти ахо-корасик и есть... По смыслу. Такой же конечный автомат. Тот кто выбирает trie, почему против хеш-таблицы?

на рандомном тексте произвольной длины не уверен что лучшая идея

на рандомном тексте произвольной длины не уверен что лучшая идея

для определения факта принадлежности слова к словарю в самый раз

для определения факта принадлежности слова к словарю в самый раз

там может быть например ключ в 10 букв и 100 слов по метру

почему бы просто на ходу не сверять и вообще не хранить ничего

а упс

для определения факта принадлежности слова к словарю в самый раз

+1

неправильно прочитал

Там ограничения по памяти еще не было?

Там ограничения по памяти еще не было?

нет, словарь не более 128 метров

ТАк чо, какие аргументы в пользу trie против std::unordered_set например?

ТАк чо, какие аргументы в пользу trie против std::unordered_set например?

и тот и другой вариант приемлем, только trie более стабилен, поскольку не зависит от природы слов в словаре

и тот и другой вариант приемлем, только trie более стабилен, поскольку не зависит от природы слов в словаре

А что значит более стабилен и как нестабильна хеш-табля?

для хеш таблицы на определенный наборах ты банально можешь получать больше коллизий

ну, банальный пример: size_t degraded_hash_function(char const*) {return 1;} какую сложность ты получишь?

Получу O(n), да.

ну вот остюда trie более стабилен в плане независимости сложности от природы данных и равен O(l), l длина слова

то есть, ребята из VK могут подсунуть тебе исходных файл, как хороший для unordered_set, так и плохой.

а могут вообще сказать - чего это ты преждевременной оптимизацией занимаешься и выгонят взашей :)

Это ты о чем? Или даже к чему?

А на слово "рефакторинг" реагируют как на воровство

А на слово "рефакторинг" реагируют как на воровство

Кто?

http://jrfonseca.blogspot.com.by/2008/09/fast-sse2-pow-tables-or-polynomials.html

По поводу инклюдов я накинулся на тему и выяснил вот что - порядок имеет значение, и это не "вопрос стиля". Это вопрос времени компиляции. Типа чувак провел исследования, замеряя сколько раз каждый заголовочник компилится. Там цифры для проекта в 300 cpp-файлов и 300 заголовочных оказались дикие, типа самый "популярный" заголовочник компилится 10k раз. Ну и собссно правила он написал такие: 1. всегда в cpp первым включается собственный заголовочный файл 2. в заголовочном файле нужно включить все хедеры, которые требуются чтобы его можно было распарсить при сборке (этого я не понял, видимо автор знает какой-то способ не включать в хедерах другие хедеры вообще) 3. в заголовочном файле необходимо включить только самый минимум, который нужен для сборки, все остальное объявить через forward declarations 4. (это я сам дописываю, у него это есть но почему-то он не упомянул это как правило) любые большие либы и стандартные библиотеки включаются последними в списке http://gamesfromwithin.com/physical-structure-and-c-part-1-a-first-look http://gamesfromwithin.com/physical-structure-and-c-part-2-build-times

А гугл в своих гайдлайнах считает иначе: >Avoid using forward declarations where possible. Just #include the headers you need.

По поводу инклюдов я накинулся на тему и выяснил вот что - порядок имеет значение, и это не "вопрос стиля". Это вопрос времени компиляции. Типа чувак провел исследования, замеряя сколько раз каждый заголовочник компилится. Там цифры для проекта в 300 cpp-файлов и 300 заголовочных оказались дикие, типа самый "популярный" заголовочник компилится 10k раз. Ну и собссно правила он написал такие: 1. всегда в cpp первым включается собственный заголовочный файл 2. в заголовочном файле нужно включить все хедеры, которые требуются чтобы его можно было распарсить при сборке (этого я не понял, видимо автор знает какой-то способ не включать в хедерах другие хедеры вообще) 3. в заголовочном файле необходимо включить только самый минимум, который нужен для сборки, все остальное объявить через forward declarations 4. (это я сам дописываю, у него это есть но почему-то он не упомянул это как правило) любые большие либы и стандартные библиотеки включаются последними в списке http://gamesfromwithin.com/physical-structure-and-c-part-1-a-first-look http://gamesfromwithin.com/physical-structure-and-c-part-2-build-times

Стражи включения, pragma once не позволят для одной единицы трансляции компилировать один и тотже заголовчный файл, как бы ты их не переставлял. Так что, если взять один cpp с N заголовочными файлами и комбинаторно заняться перестановками ты должен получить примерно одинаковые времена. Так что, приведи ссылку на "исследования".

Для людей, которые форвардят вместо реплая, есть отдельный котел в аду

Та я раньше не знал, что так можн делать.)

Стражи включения, pragma once не позволят для одной единицы трансляции компилировать один и тотже заголовчный файл, как бы ты их не переставлял. Так что, если взять один cpp с N заголовочными файлами и комбинаторно заняться перестановками ты должен получить примерно одинаковые времена. Так что, приведи ссылку на "исследования".

Там две ссылки чуть выше, в которых это все подробно расписано. Например, With every header file having include guards around it, I turned on the /showincludes switch in Visual C++ and performed a full build. The total number of includes during the course of building the 300 classes in the library was an astounding 15,264. Better than the worst-case-scenario we calculated earlier, but still tremendously high.

Чой-то не помогли гварды

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

А, ну ок, не буду спорить

По поводу инклюдов я накинулся на тему и выяснил вот что - порядок имеет значение, и это не "вопрос стиля". Это вопрос времени компиляции. Типа чувак провел исследования, замеряя сколько раз каждый заголовочник компилится. Там цифры для проекта в 300 cpp-файлов и 300 заголовочных оказались дикие, типа самый "популярный" заголовочник компилится 10k раз. Ну и собссно правила он написал такие: 1. всегда в cpp первым включается собственный заголовочный файл 2. в заголовочном файле нужно включить все хедеры, которые требуются чтобы его можно было распарсить при сборке (этого я не понял, видимо автор знает какой-то способ не включать в хедерах другие хедеры вообще) 3. в заголовочном файле необходимо включить только самый минимум, который нужен для сборки, все остальное объявить через forward declarations 4. (это я сам дописываю, у него это есть но почему-то он не упомянул это как правило) любые большие либы и стандартные библиотеки включаются последними в списке http://gamesfromwithin.com/physical-structure-and-c-part-1-a-first-look http://gamesfromwithin.com/physical-structure-and-c-part-2-build-times

Если порядок имеет значение, того кто этот код написал, надо увольнять. Но да, на практике такое может случаться.

По поводу инклюдов я накинулся на тему и выяснил вот что - порядок имеет значение, и это не "вопрос стиля". Это вопрос времени компиляции. Типа чувак провел исследования, замеряя сколько раз каждый заголовочник компилится. Там цифры для проекта в 300 cpp-файлов и 300 заголовочных оказались дикие, типа самый "популярный" заголовочник компилится 10k раз. Ну и собссно правила он написал такие: 1. всегда в cpp первым включается собственный заголовочный файл 2. в заголовочном файле нужно включить все хедеры, которые требуются чтобы его можно было распарсить при сборке (этого я не понял, видимо автор знает какой-то способ не включать в хедерах другие хедеры вообще) 3. в заголовочном файле необходимо включить только самый минимум, который нужен для сборки, все остальное объявить через forward declarations 4. (это я сам дописываю, у него это есть но почему-то он не упомянул это как правило) любые большие либы и стандартные библиотеки включаются последними в списке http://gamesfromwithin.com/physical-structure-and-c-part-1-a-first-look http://gamesfromwithin.com/physical-structure-and-c-part-2-build-times

Время компиляции ни на что не влияет, это эфимерная сущность.

Там две ссылки чуть выше, в которых это все подробно расписано. Например, With every header file having include guards around it, I turned on the /showincludes switch in Visual C++ and performed a full build. The total number of includes during the course of building the 300 classes in the library was an astounding 15,264. Better than the worst-case-scenario we calculated earlier, but still tremendously high.

По моему так это просто говностатья очередная из интернета. Читай Лакоса лучше или что-то подобное

ERROR: S client not available

У вконтактика вступительная задачка при подаче на вакуху: Вашей программе в качестве аргумента будет передано имя файла, в котором будет находиться множество строк (ASCII символы с кодами от 32 до 127). Далее Ваша программа должна считывать строки из stdin, пока не придет строка "exit". После каждой считанной строки Ваша программа должна выводить в stdout строку "YES" или "NO" в зависимости от того, встречается данная строка в переданном файле или нет. Размер файла со словарем не превосходит 128мб. У меня 3 варианта: 1) Загнать все строки в память в плоский массив, рядом создать массив указателей на эти строки, отсортировать массив указателей по возрастанию строк и искать бинарным поиском, O(log n) 2) Загнать все строки в память в плоский массив, напихать этих строк в хеш-таблицу (физически напихать указателей на эти строки в хеш-таблицу), искать за O(1) 3) Захерачить все строки в ахо-корасика, искать за O(1), но память раздует из-за построения графа. Ещё варианты?

Память не раздует

Ахокорасик не нужен ты же не подстроки ищешь

У вконтактика вступительная задачка при подаче на вакуху: Вашей программе в качестве аргумента будет передано имя файла, в котором будет находиться множество строк (ASCII символы с кодами от 32 до 127). Далее Ваша программа должна считывать строки из stdin, пока не придет строка "exit". После каждой считанной строки Ваша программа должна выводить в stdout строку "YES" или "NO" в зависимости от того, встречается данная строка в переданном файле или нет. Размер файла со словарем не превосходит 128мб. У меня 3 варианта: 1) Загнать все строки в память в плоский массив, рядом создать массив указателей на эти строки, отсортировать массив указателей по возрастанию строк и искать бинарным поиском, O(log n) 2) Загнать все строки в память в плоский массив, напихать этих строк в хеш-таблицу (физически напихать указателей на эти строки в хеш-таблицу), искать за O(1) 3) Захерачить все строки в ахо-корасика, искать за O(1), но память раздует из-за построения графа. Ещё варианты?

Бойер-Мур

У вконтактика вступительная задачка при подаче на вакуху: Вашей программе в качестве аргумента будет передано имя файла, в котором будет находиться множество строк (ASCII символы с кодами от 32 до 127). Далее Ваша программа должна считывать строки из stdin, пока не придет строка "exit". После каждой считанной строки Ваша программа должна выводить в stdout строку "YES" или "NO" в зависимости от того, встречается данная строка в переданном файле или нет. Размер файла со словарем не превосходит 128мб. У меня 3 варианта: 1) Загнать все строки в память в плоский массив, рядом создать массив указателей на эти строки, отсортировать массив указателей по возрастанию строк и искать бинарным поиском, O(log n) 2) Загнать все строки в память в плоский массив, напихать этих строк в хеш-таблицу (физически напихать указателей на эти строки в хеш-таблицу), искать за O(1) 3) Захерачить все строки в ахо-корасика, искать за O(1), но память раздует из-за построения графа. Ещё варианты?

1) указатели не нужны. String и так хранит указатель

Сравнения долгие

+

struct Cust { int x = 0; }; int main() { Cust a = {0}; return 0; } >>>> g++ -std=c++11 Почему оно собирается только если выкинуть = 0 из структуры?

Буть может из за стандарта? (С++11)

Т.е. есль хочешь чтоб работало надо инициализацию в struct удальть

Т.е. есль хочешь чтоб работало надо инициализацию в struct удальть

Выше выяснили что C++14 решает проблему

а вот такой с моей стороны неожиданный вопрос: есть способы регулировать размер чанков в std::deque?

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

Всем привет Есть определённый набор координат, как можно из него получить изображение bmp?

Всем привет Есть определённый набор координат, как можно из него получить изображение bmp?

https://stackoverflow.com/questions/2654480/writing-bmp-image-in-pure-c-c-without-other-libraries

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

Нет способа

Это всё детали реализации

кто знает про allegro? она изначально software рендерит?

Есть какой-нибудь шорткат для передачи member-function как лямбду? e.g: Вместо f([&obj](auto t) { obj.g(t); }) Использовать f(&obj.g)

Есть какой-нибудь шорткат для передачи member-function как лямбду? e.g: Вместо f([&obj](auto t) { obj.g(t); }) Использовать f(&obj.g)

std::bind, но вроде не короче

бинд совсем печально смотрится, ну лан, спасибо

ну учитывая, что this — это указатель, тебе в любом случае придётся во что-нибудь оборачивать