What Is Difference Between Const and Non Const Key

What is difference between const and non const key?

int and const int are two distinct types.
std::map<int, float> and std::map<const int, float> are, similarly, different types.

The difference between std::map<const int, float> and std::map<int, float> is, to a degree, analogous to the difference between, say, std::map<int, float> and std::map<std::string, float>; you get a fresh map type for each.

In the non-const case, the internal key type is still non-const int:

std::map<const int, float>::key_type       => const int
std::map<int, float>::key_type             => int

However, map keys are semantically immutable, and all map operations that allow direct access to keys (for example, dereferencing iterators, which yields value_type) does constify the key_type:

std::map<const int, float>::value_type => std::pair<const int, float>
std::map<int, float>::value_type       => std::pair<const int, float>

So the difference may be largely invisible to you in every way that matters, if your implementation allows it.

That's not always the case, though: the standard officially requires your key type to be copyable and moveable, and some implementations re-use map nodes; under those implementations, attempting to use a const key simply won't work.

C++ Difference Between Const Reference to Non Const Object and Non Const Reference to Non Const Object

"What is the purpose for the "const" keyword for a reference if the object it is referencing is not a const object?"
The purpose is to prevent that reference being used to modify the object it is referencing.

int i = 42; // non const object
const int &r1 = i; // const reference to non const object
r1 = 6 * 9; // error, r1 cannot be used to modify i;

Difference between const map and map of const elements

Having a const container means the container is immutable. You can't change it.

Having a non-const container means the container is mutable. You can change it.

Changing a map means: adding to it, modifying the things it contains (if they are, themselves, mutable), removing from it.

By the way, putting const on a map key is largely pointless.

I'm not going to enumerate "when should each be used"; you use the right tool for the job, and there are a near-infinite number of possible jobs.

What is the difference between const int, const int const, and int const *?

Read it backwards (as driven by Clockwise/Spiral Rule):

int* - pointer to int
int const * - pointer to const int
int * const - const pointer to int
int const * const - const pointer to const int

Now the first const can be on either side of the type so:

const int * == int const *
const int * const == int const * const

If you want to go really crazy you can do things like this:

int ** - pointer to pointer to int
int ** const - a const pointer to a pointer to an int
int * const * - a pointer to a const pointer to an int
int const ** - a pointer to a pointer to a const int
int * const * const - a const pointer to a const pointer to an int
...

And to make sure we are clear on the meaning of const:

int a = 5, b = 10, c = 15;

const int* foo;     // pointer to constant int.
foo = &a;           // assignment to where foo points to.

/* dummy statement*/
*foo = 6;           // the value of a can´t get changed through the pointer.

foo = &b;           // the pointer foo can be changed.

int *const bar = &c;  // constant pointer to int 
                      // note, you actually need to set the pointer 
                      // here because you can't change it later ;)

*bar = 16;            // the value of c can be changed through the pointer.    

/* dummy statement*/
bar = &a;             // not possible because bar is a constant pointer.

foo is a variable pointer to a constant integer. This lets you change what you point to but not the value that you point to. Most often this is seen with C-style strings where you have a pointer to a const char. You may change which string you point to but you can't change the content of these strings. This is important when the string itself is in the data segment of a program and shouldn't be changed.

bar is a constant or fixed pointer to a value that can be changed. This is like a reference without the extra syntactic sugar. Because of this fact, usually you would use a reference where you would use a T* const pointer unless you need to allow NULL pointers.

const vs non-const variable with no change in value once assign

A clever compiler can understand that the value of a variable is never changed, thus optimizing the related code, even without the explicit const keyword by the programmer.

As for your second, question, when you mark a variable as const, then the follow might happen: the "compiler can optimize away this const by not providing storage to this variable rather add it in symbol table. So, subsequent read just need indirection into the symbol table rather than instructions to fetch value from memory". Read more in What kind of optimization does const offer in C/C++? (if any).

I said might, because const does not mean that this is a constant expression for sure, which can be done by using constexpr instead, as I explain bellow.

In general, you should think about safer code, rather than faster code when it comes to using the const keyword. So unless, you do it for safer and more readable code, then you are likely a victim of premature optimization.

Bonus:

C++ offers the constexpr keyword, which allows the programmer to mark a variable as what the Standard calls constant expressions. A constant expression is more than merely constant.

Read more in Difference between `constexpr` and `const` and When should you use constexpr capability in C++11?

PS: Constness prevents moving, so using const too liberally may turn your code to execute slower.

Both const and non-const version of the same function - an anti-pattern?

No, not always.

There are legitimate uses for this pattern. For example, suppose you are writing a collection, and the code for retrieving an element is fairly complex (e.g. a hash table). You don't want to duplicate all the code, but you also want your collection to be able to be used as both const and non-const.

So, you might do something like this:

struct HashTable {
    ...

    const Value &get(Key key) const {
        ... complex code for retrieving the key
    }

    Value &get(Key key) {
        return const_cast<Value &>(
            static_cast<const HashTable *>(this)->get(key)
        );
    }
};

Here, the const_cast<> is not really a lie. Since your function is non-const, you know that it can be called only if the object pointed to by this is also non-const. Hence, casting the constness away is valid.

(of course, similarly to this situation, you can call a non-const method by casting away the const-ness of a const instance, but at that point its the user of your class who has already introduced undefined behavior, so you are covered as long as your class is being used correctly.)

How to find by a const pointer key in a map with non-const pointer keys

I think I have found a solution, but it requires C++14 transparent comparators.

#include <map>
#include <iostream>

struct CompareIntPtrs
{
    using is_transparent = void; // enabling C++14 transparent comparators

    bool operator()(const int * l, const int * r) const
    {
        return l < r;
    }
};

std::map<int*, double, CompareIntPtrs> mymap;

double myfind(const int * key)
{
    return mymap.find(key)->second;
}

int main()
{
    int x {6};
    mymap[&x] = 66; // inserting to the map
    const int * px = &x; // creating a "const int *" variable

    std::cout << myfind(px) << std::endl; // using "const int *" for finding in map with "int*" keys
    std::cout << mymap.find(px)->second << std::endl; // we could even skip using myfind()
}

An excellent article about C++14 transparent comparators can be found here.
To be completely honest, by adding the comparator, the type of mymap slightly changed which I originally didn't want to, but it's the best solution I could find.

If C++14 is not available, there are at least two evils we can choose from.
The first one is to copy mymap to a new std::map<const int*, double> in myfind, which is horribly unefficient.
The second one is casting away constness by using a const_cast<int*>(mykey) which should be avoided if possible.

Copy paste of const and non-const methods

This is one of the legitmate uses of const_cast

const std::string* get(ID id) const override
{
    return const_cast<ConcreteStorage*>(this)->get(id);
}

Why can I pass the key of std::map to a function that expects non-const?

so I assume that the type of elem.first is const S*

No. The key stored in map is const, that means for std::map<S*, Data>, the key will be S* const (i.e. const pointer), not const S* (i.e. pointer to const). So it's fine to pass it to foo(S* ptr), the const pointer itself will be copied to the parameter.

What Is Difference Between Const and Non Const Key