4

I am maintaining a container class with an interface similar to std::map/std::unordered_map.

The interface claims to store std::pair<const X,Y> (i.e that's what value_type is). Internally, however, the implementation stores a sorted array of std::pair<X,Y>.

The current implementation uses reinterpret_cast to implement the iterators. My question is, is there a better alternative?

Moving to storing an array of std::pair<const X,Y> wouldn't be possible, as the implementation needs to copy elements around in the array to implement insertion and deletion. One of the ways it does this is using std::sort.

Edit: Although I believe the reinterpret_cast invokes undefined behavior (or implementation defined?) I have yet to come across a compiler where this doesn't work - Am I worrying about nothing?

Current implementation of iterator's dereference:

template <class K, class M>
std::pair<const K,M>& operator*() {
  std::pair<K,M>& result = ...;
  return *reinterpret_cast<std::pair<const K,M>*)(&result);
}
JoeG
  • 12,994
  • 1
  • 38
  • 63
  • I haven't tried this, but wouldn't const_cast be preferable to reinterpret_cast? – Benj Jan 05 '12 at 17:44
  • 1
    @Benj `const_cast` can't do the job here. – Mark B Jan 05 '12 at 17:46
  • Why can't you have internal consts? Perhaps you can change assignment to destruction/reconstruction? – Kerrek SB Jan 05 '12 at 17:48
  • your problem with `const X` is that you need to copy elements when inserting or deleting. I'm not sure it's entirely legal, but you might be able to change `pair1 = pair2` to a manual call to the destructor (`pair1.~pair()`), followed by copy construction placement new (`new(&pair1) pair(pair2)`). Codesamples simplyfied for space reasons – Grizzly Jan 05 '12 at 18:06
  • 1
    @Kerrek SB: I think that's the only solution that works and is well defined. However, it will significantly complicate the implementation. I won't be able to call `std::sort` as it will try to copy/move rather than construct/destruct. – JoeG Jan 05 '12 at 19:49
  • 1
    @Grizzly: That's significantly messier than the reinterpret_cast solution, although it might be legal. I'll investigate. – JoeG Jan 05 '12 at 19:52
  • Mooing Duck's comment under Mark B's answer point to this duplicate [Is it possible to "constify" a field of `std::pair` without hacks?](http://stackoverflow.com/questions/3638541/is-it-possible-to-constify-a-field-of-stdpair-without-hacks) – JoeG Jan 05 '12 at 22:31

2 Answers2

2

I believe you can't solve this by returning a std::pair. Instead, you're going to have to return a proxy object that looks like a standard pair, but if you update the second member it propagates through to the main container, while the first member is expose as const as you desire.

Mark B
  • 95,107
  • 10
  • 109
  • 188
  • Having a similar project to the OP, This doesn't seem like it would be as easy as you make it sound. Maybe though. I'll give it a whirl. – Mooing Duck Jan 05 '12 at 20:20
  • http://stackoverflow.com/questions/3638541 gives the idea of returning a `std::pair(first, second)`, completely different object, but users shouldn't be able to tell. – Mooing Duck Jan 05 '12 at 20:25
1

"Better alternative?" What is wrong with reinterpret_cast? In this case, the cast is even well-defined since you're casting between objects with compatible (in fact, identical) representations.

zvrba
  • 24,186
  • 3
  • 55
  • 65