Удобное место, чтобы написать свою статью или просто почитать


Показаны статьи и заметки из категорий: Задачи по программированию ×

Кортеж (std::tuple) появился в стандартной библиотеке начиная с С++11. Это неоднородный список элементов, типы которых задаются или выводятся на этапе компиляции. Кортеж "похож" на пару (std::pair), однако он может содержать произвольное (хотя и конечное) количество элементов. Интерфейс кортежа довольно простой: http://en.cppreference.com/w/cpp/utility/tuple

Создать кортеж можно так:

#include <tuple>

std::tuple<std::string, int, double> tuple_("hello", 42, 3.14);

Про кортеж говорят, что это коллекция гетерогенных значений (разнородных). Поэтому тип элемента (value_type), который определен в любом стандартном контейнере, не имеет смысла в кортеже, и просто отсутствует, ровно как и любой из типов итераторов. Кортеж не является обычным контейнерным классом, и не отвечает концепции контейнеров в С++ (http://en.cppreference.com/w/cpp/concept/Container). Поэтому простого способа обхода элементов кортежа нет. К нему не применимы какие-либо циклы:

for (auto& x : tuple_);  // Ошибка компиляции!

error: no viable 'begin' function available

"Пройтись" по элементам кортежа можно только точно зная количество его аргументов на этапе компиляции. Для этого нужно использовать функцию get:

std::get<0>(tuple_); // индекс элемента в качестве аргумента шаблона
std::get<1>(tuple_);
std::get<2>(tuple_);

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

int i = 0;
std::get<i>(tuple_);  // Ошибка компиляции!

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

Читать полностью | | | | 12326



Интересная задача на собеседовании

Однажды, на собеседовании в крупной российской IT компании, было предложено решить одну интересную задачу. Точный текст условия, к сожалению, привести нет возможности, однако суть задачи простая. 

Задача

Пусть дана последовательность целых чисел. Длина последовательности известна. Числа не отсортированы и могут повторяться. Необходимо найти в данной последовательности такие два числа M и N, чтобы их сумма была равна целому числу K ( M + N = K ). Будем считать, что K равно 5. Хотя можно выбрать любое другое целое число.

Для примера, возьмем последовательность (1):

7, -1, 1, -7, 0, -4, 3, 2, -5, -6, 8, -2  (1)

Тогда M = 3, а N = 2 ( 3 + 2 = 5 ), 
или   M = 7, а N = -2 ( 7 + (-2) = 5 )

Для решения задачи достаточно найти хотя бы одну подходящую пару чисел M и N. Ограничения по памяти не накладываются и главным критерием является асимптотическая сложность алгоритма. Решим эту задачу.

Читать полностью | | | | 4251


Показаны статьи и заметки из категорий: Задачи по программированию ×