Рефакторинг код с <char, T> в вектор <T>

Question

На самом деле, проблема в названии. У меня есть рабочий код, где я сильно использую std::map<char, T> table. Профилер сказал мне, что метод operator[] занимает довольно много времени. Поэтому я думаю, что поскольку char имеет только несколько разных значений (от -128 до 127, я полагаю), можно изменить тип моей переменной table на std::vector<T> или даже T[256]. Мой вопрос - как это сделать безопасно. Я имею в виду, что я не могу полагаться на то, что тип char имеет ровно 256 различных значений, поэтому я хочу добавить переносимый код, который будет использовать что-то вроде std :: numeric_limits и будет гарантировать, что размер table охватывает все возможные значения char. И еще одна проблема заключается в том, что мне не нравились отрицательные значения при использовании std::map. Но я не могу сделать то же самое с std::vector, потому что table[(char)-15] создаст исключение. Означает ли это, что самым простым решением является передача всех ключей от char до unsigned char перед вызовом operator[] моего table? Если это не так, как мне это сделать?

Answer 1

Я бы предложил ввести свой собственный класс для использования, который каким-то образом инкапсулирует std::vector<T> и предоставит необходимый вам интерфейс.

Если вы собираетесь повторно использовать много интерфейса std::vector «s, вы можете даже рассмотреть возможность использования внедренных-в-плана-отношений:

template <class T> 
struct MyMap : protected std::vector<T> 
{ 
    using std::vector::vector; 
    using std::vector::push_back; 
    // ... 
    // List other members which you want to inherit verbatim 

    T& operator[] (char idx) 
    { 
    return std::vector::operator[](idx - std::numeric_limits<char>::min()); 
    } 
    // Re-implement the members which you need to 
}; 

Answer 2

Я предлагаю перейти на std::unordered_map<char, T> .

std::unordered_map Для сложность operator[] формулируется как approximatley O(1)

усредненными: постоянная, наихудший случай: линейная по размеру.

Для std::map сложность operator[] является O(logN)

Логарифмические в размере контейнера.