Есть ли способ получить смещение элемента в предикатах, переданных в алгоритмы std? - PullRequest
Новая
       81

Есть ли способ получить смещение элемента в предикатах, переданных в алгоритмы std?

0 голосов
/ 13 июля 2020

Предикаты / операторы, используемые в библиотеке алгоритмов принимают элементы по значению_типа соответствующих итераторов. Я хотел бы написать предикат, который использует смещение элемента в диапазоне.

Например, рассмотрим следующий код : 

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{0, 1, 2, 3, 4, 5, 6};

    auto offset_value_mismatch = [&v](int const & x){
        return (x != (&x-&v.front()));
    };

    return std::any_of(v.begin(), v.end(), offset_value_mismatch);
}

Мои вопросы:

  1. Есть ли «приятный» способ (т.е. лучший, чем то, что я представил выше), чтобы найти смещение элемента в диапазоне?
  2. Гарантированно ли вышеуказанный метод работает для любого типа данных (вместо int)? Поскольку const & может связываться с r-значением, я беспокоюсь, что могу получить адрес какой-то временной копии.
  3. Можно ли что-то подобное реализовать для ассоциативных (не непрерывных) структур данных?
  4. Изменится ли какой-либо из ответов, если я использую перегрузки алгоритма, принимающие std :: ExecutionPolicy?

РЕДАКТИРОВАТЬ:

Дополнительная информация о моей проблеме: Рассмотрим многомерную структуру данных, созданную поверх std::vector. В этой структуре данных индексы «управляются», так что я могу выполнять некоторые действия со всеми структурами данных одновременно. Более того, тип данных сам по себе может быть индексами. Для этого я использовал al oop. Я хотел бы посмотреть, смогу ли я улучшить производительность, используя стандартные параллельные алгоритмы.

РЕДАКТИРОВАТЬ # 2:

В итоге я реализовал простой последовательный алгоритм на основе l oop для (редких) случаев, когда определенный тип индекса появляется как в домене, так и в диапазоне. В других случаях в приведенном выше упражнении нет необходимости, и я получаю ускорение примерно на 60% с политикой выполнения par_unseq! (но по какой-то причине не с par).

Ответы [ 2 ]

2 голосов
/ 13 июля 2020

Гарантируется ли работа описанной выше техники для любого типа данных (вместо int)? Поскольку const & может связываться с r-значением, я беспокоюсь, что могу получить адрес какой-то временной копии.

Нет. Это будет работать только для std::vector или std::array или необработанных указателей, что гарантирует, что все элементы хранятся в непрерывной памяти. Для них это будет работать для любого типа данных, хранящегося там. Но этот метод приведет к UB даже для итератора произвольного доступа, например, из std::deque.

Можно ли что-то подобное реализовать для ассоциативных структур данных?

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

1 голос
/ 13 июля 2020
  1. Есть ли «приятный» способ (т.е. лучший, чем то, что я представил выше) найти смещение элемента в диапазоне?

Нет, не в общий.

Гарантированно ли вышеописанный метод работает для любого типа данных?

Почти (за исключением того, что вам, очевидно, нужно изменить тип аргумента, чтобы он соответствовал любому типу данных, который повторяется). Вам нужно будет использовать std::addressof, чтобы он работал с типами, которые перегружают оператор addressof (но кто это делает?).

Можно ли что-то подобное реализовать для ассоциативных структур данных?

Не совсем так. То, что вы показали, работает, но только для смежных итераторов, то есть итераторов для массивов (в общем смысле, который включает векторы и строки).

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

auto offset_value_mismatch = [](auto& x) {
    static int i;
    return i++ == x;
}
Изменится ли какой-либо из ответов, если я использую перегрузки алгоритма, принимающие std :: ExecutionPolicy?

Как вычитание адреса, так и аккумулятор работают только с последовательными алгоритмами, а не с параллельные. Технически аккумулятор можно заставить работать с параллельной политикой (но не неупорядоченной) с использованием блокировок, но, насколько мне известно, в этом нет никакого преимущества.

...