Q:

Компилятор ругается на использование в константном методе не константного map

Можно использовать map без удаления const?
template <typename T>
class CTest {
public:

    size_t Get(T str) const{ //Тут ругается
        return A[str];
    }

// другие методы убрал для большей понятности

private:
    map< T, size_t> A;
};

A:

Метод [] является модифицирующим методом std::map, по каковой причине применить его к константному std::map не получится.
Немодифицирующий метод называется at
return A.at(str);

Имейте только в виду, что он бросает исключение std::out_of_range в случае ненайденного ключа.

A:

Можно, достаточно убрать вызов оператора [] (который может модифицировать мапу, вставляя в нее элемент с требуемым индексом):
size_t Get(T const & str) const
{
    auto const p_entry{A.find(str)};
    if(A.end() == p_entry)
    {
         throw ::std::out_of_range{"not found"};
    }
    return p_entry->second;
}

