4

I have the following code:

#include <map>
using namespace std;
struct A {};

map</*const*/ A *, int> data;

int get_attached_value(const A *p) {
    return data.at(p);
}
void reset_all() {
    for (const auto &p : data) *p.first = A();
}

My problem is that this code fails on a type error both when I comment and uncomment the const in the type of data. Is there any way I can solve this without using const_cast and without losing the const in get_attached_value?

tohava
  • 5,344
  • 1
  • 25
  • 47

1 Answers1

2

The problem seems to be in the pointee type, which has to be the same in both pointer declarations (map key type and the get_attached_value's argument).

OP's code uses const A*, which is a pointer to a const instance of class A (an alternative spelling is A const *). Leaving this const in both map declaration and in get_attached_value' argument almost works, but reset_all does not allow you to assign a new value to *p.first, because the resulting type is A const& (which cannot be assigned into).

Removing both consts works as well, but OP wants to keep a const in get_attached_value.

One solution for OP's requirements, keeping as many consts as possible, seems to be to change the pointer type to a const pointer to a non-const instance of A. This will keep reset_all working, while allowing to use a const pointer in both map declaration and get_attached_value's argument:

#include <map>
using namespace std;
struct A {};

map<A * const, int> data;

int get_attached_value(A * const p) {
    return data.at(p);
}
void reset_all() {
    for (const auto &p : data)
        *p.first = A();
}

Another possible solution, with map's key as non-const but the get_attached_value's parameter const, could use std::lower_bound with a custom comparator to replace the data.at() call:

#include <map>
#include <algorithm>

using namespace std;
struct A {};

map<A*, int> data;

int get_attached_value(A const * const p) {
    auto it = std::lower_bound(data.begin(), data.end(), p,
        [] (const std::pair<A* const, int>& a, A const* const b) {
            return a.first < b;
        }
    );
    return it->second;
}
void reset_all() {
    for (const auto &p : data)
        *p.first = A();
}

However, this solution will be significantly less efficient than one that would use map's native search functions - std::lower_bound uses linear search when input iterators are not random access.

To conclude, the most efficient solution in C++11 or lower would probably use a const pointer as the map's key, and a const_cast in the reset_all function.

A bit more reading about const notation and pointers can be found here.

Community
  • 1
  • 1
Martin Prazak
  • 1,476
  • 12
  • 20
  • 1
    @tohava But then the `reset_all` method cannot work, because you are trying to assign a new value to the pointee (a const reference in that case). – Martin Prazak Mar 15 '15 at 23:34
  • In an ideal world, the map would be a map with a key who is a non-const pointer, and there would be an `at` method which works for const pointers as well (since it only gives access to the value, and avoids exposing the non-const pointer back to the caller) – tohava Mar 15 '15 at 23:40
  • @tohava What about using `std::lower_bound` to replace `at`? Would that be a solution satisfying your requirements? However, I'd argue that your question is a bit unclear and inconsistent with your previous comment, because uncommenting the const in your code would always break the `reset_all` method. – Martin Prazak Mar 16 '15 at 00:01
  • Wouldn't lower_bound require me to use `const_cast`? – tohava Mar 16 '15 at 00:03
  • Nope, the code I've written in the second example above compiles in gcc 4.8.1 . – Martin Prazak Mar 16 '15 at 00:04
  • `std::lower_bound` typically won't be efficient on `std::map`. The map has a special implementation as a member function: `std::map::lower_bound`. – dyp Mar 16 '15 at 00:05
  • @martin_pr - Did you try on your code or on the code where the const is on pointee and not pointer – tohava Mar 16 '15 at 00:07
  • 1
    @tohava - If you mean for `p` parameter, then yes, the code above works for all const combinations around `p`. – Martin Prazak Mar 16 '15 at 00:09
  • @martin_pr - ok, I get it now. Btw, dyp mentioned heterogenous C++14 containers, which I think may be a way to combine your solution with the efficency of `map` – tohava Mar 16 '15 at 00:11
  • @dyp - `std::map` does have its own implementation of `lower_bound`, but it won't allow you to pass a custom comparator, which means that what OP is trying to achieve is not possible. About efficiency, you are probably right, but I'd argue that the difference won't be huge. – Martin Prazak Mar 16 '15 at 00:11
  • @tohava - Probably, but you said you can't use C++14 :) – Martin Prazak Mar 16 '15 at 00:12
  • The difference is that `std::lower_bound` will probably perform a **linear search** since it probably won't use the tree structure of the `std::map`. And a linear search in a tree is slow. See http://stackoverflow.com/q/20934717/ – dyp Mar 16 '15 at 00:16
  • @dyp - Yes, you're right - for non-random access iterators, it will go linearly. Shame... I am not sure if there is a better solution without a const_cast in C++11 (or lower), though. I'll stick a warning in my answer. – Martin Prazak Mar 16 '15 at 00:20