Как я могу избежать расточительного копирования ключей на основе STL-подобной карты на основе B-дерева?

Я заменяю использование std::map горячим путем cpp-btree btree_map. Но при включенной оптимизации GCC и Clang жалуются на строгое нарушение псевдонимов. Проблема сводится к следующему:

template <typename Key, typename Value>
class btree_map {
public:
    // In order to match the standard library container interfaces
    using value_type = std::pair<const Key, Value>;

private:
    using mutable_value_type = std::pair<Key, Value>;

    struct node_type {
        mutable_value_type values[N];
        // ...
    };

public:
    class iterator {
        // ...

        value_type& operator*() {
            // Here we cast from const std::pair<Key, Value>&
            // to const std::pair<const Key, Value>&
            return reinterpret_cast<value_type&>(node->values[i]);
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // ...
        // At this point, we have to insert into the middle of a node.
        // Here we rely on nodes containing mutable_value_type, because
        // value_type isn't assignable due to the const Key member
        std::move_backward(node->values + i, node->values + j,
                           node->values + j + 1);
        node->values[i] = value;
        // ...
    }
};

Это заставило меня думать, есть ли способ сделать это так эффективно, что не полагается на поведение undefined? Ключи, которые я использую, эффективно перемещаются, но довольно медленно копируются, поэтому я бы хотел избежать копирования многих ключей при каждой вставке. Я рассмотрел

  • Используя value_type values[N], затем const_cast<Key&>(values[i].first) = std::move(key), чтобы переместить ключ, но я уверен, что все еще undefined
  • Возвращая std::pair<const Key&, Value&> вместо std::pair<const Key, Value>&, если это необходимо, но я не уверен, что это все равно будет удовлетворять требованиям контейнера (я слышу, что ...::reference должен быть ссылочным типом)
  • Не заботьтесь. Код работает как есть, но мне любопытно, можно ли это сделать стандартным образом. Также есть вероятность, что будущие компиляторы будут делать разные вещи с UB, и я не знаю, как применить -fno-strict-aliasing только к одному классу.

Любые другие идеи?

Ответы

Ответ 1

Цитата из правил строгой алиасии,

Если программа пытается получить доступ к сохраненному значению объекта через значение l, отличного от одного из следующих типов, поведение undefined:

  • ...

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

Следовательно, переход из std:: pair < Key, Value > to std:: pair < const Key, Value > через промежуточное нажатие на объединение или структуру, содержащую оба типа, поскольку члены не нарушают строгие правила псевдонимов.

Caveat: std:: pair в объединении не разрешается до тех пор, пока С++ 11 не сможет использовать структуру.

Предостережение: предположение о совместимости двух типов пар может не соответствовать действительности. Представьте себе реализацию, которая заказывает первый и второй по-разному в зависимости от константы типа Key.

Ответ 2

Изменено: расширено move_backward(...) в for-loop с явным вызовом деструктора и местом размещения, чтобы избежать ошибки присваивания.

Вместо простого назначения можно использовать новое размещение.

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

template <typename Key, typename Value>
class btree_map {
// ...
private:
    struct node_type {
        // Declare as value_type, not mutable_value_type.
        value_type values[N];
        // ...
    };

    class iterator {
        // ...

        value_type& operator*() {
            // Simply return values[i].
            return node->values[i];
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // ...
        // expand move_backward(...)
        for(size_t k = j + 1; k > i; k--) {
            // Manually delete the previous value prior to assignment.
            node->values[k].~value_type();
            // Assign the new value by placement new.
            // Note: it goes wrong if an exception occurred at this point.
            new(&node->values[k]) value_type(node->values[k - 1]);
        }
        // Matual delete and placement new too.
        node->values[i].~value_type();
        // Note: it goes wrong if an exception occurred at this point.
        new (&node->values[i]) value_type(value);
        // ...
    }
};

Ответ 3

Вы не используете BTREE как замененное сбалансированное двоичное дерево без каких-либо причин: обычно это связано с тем, что у вас есть физическое хранилище, которое намного медленнее и работает как блок-устройство, которое вам необходимо использовать в массиве node, который "несколько" представляет блок устройства. Поэтому попытка оптимизировать циклы, потраченные на обработку внутреннего массива, довольно незначительна.

Однако я подозреваю, что N является ключевым фактором в:

struct node_type {
    mutable_value_type values[N];
    // ...
};

Если он достаточно мал, вам может не понадобиться вставлять/искать/удалять элемент в порядке ключа. Производительность может быть лучше, чем пытаться упорядочить их в небольшом массиве. Чтобы избежать перемещения в функции "Удалить", вы также можете определить пустой слот, чтобы "Удалить" просто заменил элемент на пустой слот, а "Вставка" заменит первый встреченный пустой слот на элемент.

Для большего массива вы можете использовать два массива: один будет содержать в качестве элемента пару, состоящую из ключа, и индекс/итератор, указывающий на значение, хранящееся во втором массиве. Таким образом, вы можете сортировать первый массив быстро, независимо от типа value_type. Тем не менее, вам все равно придется обрабатывать второй массив при вставке или удалении элемента. Первый массив может также содержать специальные пары с заранее выделенными индексами во втором массиве при создании node. Специальная пара также устанавливается при удалении элемента (сохраняя индекс для последующего вставки другого элемента). При сортировке первого массива эти специальные пары будут помещены в конец. И зная количество вставленных элементов, вы можете использовать его в качестве индекса для выделения первой специальной пары для вставки элемента (выделения во втором массиве) в O (1). При удалении элемента специальная пара может заменить нормальную пару (сохраняя индекс) в первом массиве непосредственно перед ее сортировкой. И вам просто нужно использовать новый вызов места размещения или вызов деструктора для текущего элемента (вставка или удаление).