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

Question

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

template <typename Key, typename Value> 
class btree_map { 
public: 
    // In order to match the standard library's 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; 
     // ... 
    } 
}; 

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

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

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

Answer 1

Цитируя strict aliasing rules,

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

• . ..

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

Поэтому переход от Std :: пары < Key, Value > к StD :: Пара < константный Key, Value > через промежуточный бросок к профсоюзу или структуры, содержащей как типы как члены не нарушают строгие правила псевдонимов.

Предостережение: std :: пара в объединении не допускается до C++ 11, может использовать структуру вместо этого.

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

Answer 2

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

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

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

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); 
     // ... 
    } 
}; 

Answer 3

Вы не используете ВТКЕЙ в качестве замены сбалансированного бинарного дерева без причины: как правило, это происходит потому, что у вас есть физическое хранилище, которое намного медленнее и работает как блок-устройство, которое нужно использовать массив в узле, который «несколько» представляет блок устройства. Поэтому попытка оптимизировать циклы, потраченные на обработку внутреннего массива, довольно незначительна.

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

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

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

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