Перегрузка [] в C ++ для возврата lvalue

Question

Я пишу простой класс хэш-карты:

template <class K, class V> class HashMap;

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

Vector<Pair<K, V> > *buckets;

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

HashMap<int, int> m;
m[0] = 10; m[0] = 20;
m[2] = m[1] = m[0];

В частности,

• Для m[k] = v, где m не содержит k, я хотел бы добавить новую запись.
• Для m[k] = v, где mсодержит k, я хотел бы заменить старое значение.
• В обоих этих случаях я хотел бы, чтобы присвоение вернуло v.

Предположительно код будет выглядеть примерно так:

V& operator[](K &key)
{
    if (contains(key))
    {
        // the easy case
        // return a reference to the associated value
    }
    else
    {
        Vector<Pair<K, V> > *buck = buckets + hash(k) % num_buckets;
        // unfinished
    }
}

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

Полагаю, я мог бы создать вспомогательный класс, который перегружает как оператор присваивания, так и приведение к V, но наверняка есть более простое решение?

Редактировать : Я не осознавал, что std :: map требует, чтобы тип значения имел конструктор с нулевым аргументом.Думаю, я просто создаю значение по умолчанию.

Answer 1

Как мне поступить, если ключ не найден?

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

if (!contains(key))
    insert(Pair<K, V>(key, V()));
return reference_to_the_element_with_that_key;

Это именно то, что ваше требование тоже. Вы сказали: «Для m[k] = v, где m не содержит k, я хотел бы добавить новую запись».

Answer 2

Как мне поступить, если ключ не найден?

std::map создает новый объект, вставляет его в карту и возвращает его ссылку.Вы также можете сделать то же самое.

В качестве альтернативы вы можете выдать исключение KeyNotFoundException, как при броске карты .NET.Конечно, вы должны определить KeyNotFoundException самостоятельно, возможно получая из std::runtime_exception.

Кстати, как правило, всегда используйте operator[] в паре как:

V &operator[](const K &key);
const V &operator[](const K &key) const;

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

См. Этот раздел часто задаваемых вопросов:

• Что такое «перегрузка констант»?

Answer 3

Звучит так, как будто вам нужна «умная ссылка», которую вы вообще не можете реализовать в C ++, потому что вы не можете перегрузить оператор точки (среди прочих причин).

Другими словами, вместо того, чтобы возвращать ссылку на V, вы бы возвращали «умную ссылку» на V, которая содержала бы указатель на V. Эта умная ссылка реализовала бы operator=(const V &v) как this->p = new V(v), что требуется только конструктор копирования (не конструктор с нулевым аргументом).

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

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

Как это:

template<class K, class V> class HashMap {
private:
    V default_val;
public:
    HashMap(const V& def = V()) : default_val(def) {
        ...
    }
...
};

Если в V отсутствует конструктор с нулевым аргументом, HashMap h не будет компилироваться; пользователь должен будет предоставить объект V, значение которого будет возвращено при первом обращении к ключу.

Это предполагает, что V имеет конструктор копирования, конечно. Но из ваших примеров это все равно кажется требованием.

Answer 4

Простое решение состоит в том, чтобы сделать std::map: создать новую запись, используя конструктор по умолчанию типа значения. Это имеет два Недостатки: вы не сможете использовать [] на HashMap const, и вы не может создать экземпляр HashMap с типом значения, который не имеет значения по умолчанию конструктор. Первый более или менее неявный в спецификации, который говорит, что [] может изменить карту. Есть несколько решений для второго: самый простой, вероятно, передать экземпляр значение по умолчанию для конструктора, который сохраняет его и использует для копирования создайте новый экземпляр, например ::1006

template <typename Key, typename Value>
class HashMap
{
    //  ...
    Value m_defaultValue;
public:
    HashMap( ..., Value const& defaultValue = Value() )
        : ... , m_defaultValue( defaultValue )...

    Value& operator[]( Key& key )
    {
        //  ...
        //  not found
        insert( key, m_defaultValue );
        //  return reference to newly inserted value.
    }
};

Кроме того, вы можете operator[] вернуть прокси, что-то вроде:

template <typename Key, typename Value>
class HashMap::Helper  //  Member class of HashMap
{
    HashMap* m_owner;
    Key m_key;
public:
    operator Value&() const
    {
        if ( ! m_owner->contains( m_key ) )
            m_owner->createEntryWithDefaultValue( m_key );
        return m_owner->getValue( m_key );
    }
    Helper& operator=( Value const& newValue ) const
    {
        m_owner->insert( m_key, newValue );
        return *this;
    }
};

Обратите внимание, что вам все равно понадобится значение по умолчанию для случая, когда кто-то пишет:

v = m[x];

и x отсутствуют на карте. И это такие вещи, как:

m[x].f();

не будет работать. Вы можете только скопировать все значение или присвоить ему. (Учитывая это, я бы предпочел первое решение в этом случае. Там Однако существуют и другие случаи, когда прокси-сервер является единственным решением, и мы жить с этим.)