Перегруженный оператор [] для хэш-таблицы в вектор
Я работаю над простой хэш-таблицей в C ++. У меня есть методы для вставки, удаления и поиска в хэш-таблице указанного ключа. Я знаю, что контейнер STL карты C ++ может справиться с моей ситуацией, но я бы хотел написать свой собственный в качестве учебного упражнения.
По сути, у меня есть хеш-таблица, которая возьмет одну строку и отобразит ее в векторе других строк. Это легко сделать в методе, потому что вызов .Add () или .Delete () будет вести себя как ожидалось. Однако я хотел бы создать перегруженный оператор [] для класса, который может выполнять эти операции над вектором.
Например, если я хочу добавить элемент в вектор, я могу написать что-то вроде этого:
hashTable [string1] = newString;
Это установит новую строку в качестве члена моего вектора. То же самое можно сказать и об удалении и поиске.
hashTable [string1] = ""; соиЬ << HashTable [строка1] << епсИ;
Моя главная проблема в том, что я не знаю, как перегрузить [] оператор, чтобы получить эту функциональность. У меня эта функция закодирована прямо сейчас. Он работает с базовым соответствием строки 1 к 1, но не с соответствием строки с вектором.
// Возвращаем ссылку на вектор для обновления и переназначения?
вектор HashClass :: operator [] (постоянный строковый индекс)
{
утверждают (размер >= 0 размер < MaxSize);
Hash (ключ);
return hashTable [index];
}
Я думаю, что я больше всего застрял в идее возврата вектора, который позже должен быть назначен. Как пользователь, я бы нашел этот клудый.
Решение
В C ++ [] доступ к ассоциативным контейнерам, как правило, обеспечивается семантикой конструирования по умолчанию объекта сопоставленного типа, вставки его с ключом и возврата ссылки на вставленный сопоставленный объект.
Так что ваши operator[] будет реализован как:
string& HashClass::operator[](const string index)
{
assert(size >= 0 && size < maxSize);
Hash(key);
vector &v = hashTable[index];
if (index in v) {
...
} else {
v.push_back(string());
return v.back();
}
}
Другие решения
Этот вопрос тесно связан с другим вопросом: какое поведение делать
вы хотите, когда вы получаете доступ к несуществующему значению, кроме как в
назначение? Другими словами, что вы хотите, чтобы произошло, когда вы пишете:
std::cout << hashTable[string] << std::endl;
а также string нет в таблице?
Есть два возможных подхода: вы можете считать это ошибкой, и
бросить исключение, или отменить, или что-то подобное; или вы можете вернуться
какой-то тип по умолчанию, построенный с помощью конструктора по умолчанию, или предоставленный
клиент раньше.
Стандартная карта и unordered_map используют второй подход, используя
конструктор по умолчанию для создания нового значения. Это позволяет очень просто
решение: если operator[] нет, вставляешь, инициализируешь
со значением по умолчанию. Затем вы возвращаете ссылку на него;
hashTable[string] = newString; присваивает через ссылку на
уже существующее значение.
Во многих случаях использование первого подхода будет предпочтительным (возможно, с
contains функция, так что вы можете проверить ли operator[]
найду что нибудь или нет). Чтобы реализовать первый подход, вы должны
Сначала реализуйте определенные функции для каждого типа доступа:
template <typename Key, typename Value>
class HashTable
{
public:
Value* get( Key const& key ) const;
void set( Key const& key, Value const& value );
};
(Я обычно делаю их публичными; нет причин запрещать их использование
клиент.)
Затем вы определяете operator[] вернуть прокси, следующим образом:
template <typename Key, typename Value>
class HashTable
{
public:
class Proxy
{
HashTable* myOwner;
Key myKey;
public:
Proxy( HashTable* owner, Key const& key )
: myOwner( owner )
, myKey( key )
{
}
operator Value const&() const
{
Value const* result = myOwner->get( myKey );
if ( result == NULL ) {
// Desired error behavior here...
}
return *result;
}
Proxy const& operator==( Value const& value ) const
{
myOwner->set( myKey, value );
return *this;
}
};
Value* get( Key const& key ) const;
void set( Key const& key, Value const& value );
Proxy operator[]( Key const& key )
{
return Proxy( this, key );
}
};
Таким образом, когда вы пишете:
hashTable[key] = newString;
, прокси operator= позвоню hashTable.put( key, newString );
однако в других контекстах он вызовет неявное преобразование типов на
прокси, который вызывает hashTable.get( key ),
В некоторых случаях, даже если вы хотите вернуть значение по умолчанию, это может быть
предпочтительнее использовать это решение: get функция не требуется для
вставьте что-нибудь в хеш-таблицу, чтобы таблица не заполнялась
все пропуски, и вы можете перегрузить operator[] на const, так
Вы можете использовать его на const Хеш-таблица также. Кроме того, это не
требует, чтобы тип значения имел конструктор по умолчанию.
Это имеет один недостаток в отношении решения, используемого в
стандарт; так как вы не можете перегрузить operator., вы не можете сделать прокси
вести себя как ссылка, и такие вещи, как:
hashTable[string].someFunction();
не работает Обходной путь должен перегрузить operator-> в прокси, но
это приводит к несколько неестественному синтаксису:
hashTable[string]->someFunction(); // But the hash table contains
// values, not pointers!!!
(Не вводите в заблуждение неявным преобразованием в ссылку.
неявное преобразование не будет рассматриваться для a в выражении
a.b.)