I have a custom map-like container with (integer index,value) pairs. Here is my iterator implementation for it:
// _v is a vector holding the data with next indices
typedef int ind; // index type
// T is the value type
class iterator {
private:
idmap& owner;
std::pair<ind, T&> _p;
public:
iterator(idmap& ic, ind x) : owner(ic), _p{x, *(T*)(&_p)} {}
iterator& operator++() {
_p.first = owner._v[_p.first]._next;
return *this;
}
// the star* operator is straight forward
std::pair<ind, T&> operator*() const {
return std::pair<ind, T&>(_p.first, owner._v[_p.first]._t);
}
// the -> operator is where the weirdness comes in
std::pair<ind, T&>* operator->() const {
// placement new seems to reconstruct the pair without
// accessing the old dangling T& reference. Assignmet construction
// (_p = std::pair<>...) ended up corrupting data.
new(&const_cast<iterator*>(this)->_p) std::pair<ind, T&>(_p.first, owner._v[_p.first]._t);
return &(const_cast<iterator*>(this)->_p);
}
bool operator!=(const iterator& other) {
return (&other.owner != &owner || other._p.first != _p.first);
}
bool operator==(const iterator& other) {
return (&other.owner == &owner && other._p.first == _p.first);
}
};
In order to implement the arrow operator->, I need to return a pointer to pair type aka std::pair<ind, T&>*
(pointer to live pair). To get this I have a local std::pair<x, T&> _p
in the iterator that I copy-initialize to the current pair under iteration and return it in operator->.
To get around the issue of the uninitialized T&
reference in _p
I have initialized it to *(T*)(&_p)
(_p
is not a valid T
object!) which looks super-sketch but I am pretty sure will never be accessed by the iterator before being updated in operator->
. Do you see any problems with this, besides being just treacherous?
EDIT1:
The code works for iteration, however, the dangling reference causes issue as soon as the reference is accessed. For instance, assigning two fresh iterators to each other causes the copy constructor of std::pair to kick in and access the reference corrupting data.
EDIT2:
I ended up using boost::variant<boost::blank, std::pair...>
to allow for an "uninitialized" pointer. The current code is:
class iterator {
private:
idmap& owner;
ind x;
boost::variant<boost::blank, std::pair<ind, T&>> _p;
public:
iterator(idmap& ic, ind x) : owner(ic), x(x) {}
iterator& operator++() {
x = owner._v[x]._next;
return *this;
}
const std::pair<ind, T&>& operator*() const {
const_cast<iterator*>(this)->_p = boost::blank();
const_cast<iterator*>(this)->_p = std::pair<ind, T&>(x, owner._v[x]._t);
return boost::get<std::pair<ind, T&>>(const_cast<iterator*>(this)->_p);
}
std::pair<ind, T&>* operator->() const {
const_cast<iterator*>(this)->_p = boost::blank();
const_cast<iterator*>(this)->_p = std::pair<ind, T&>(x, owner._v[x]._t);
return &(boost::get<const std::pair<ind, T&>&>(const_cast<iterator*>(this)->_p));
}
bool operator!=(const iterator& other) {
return (&other.owner != &owner || other.x != x);
}
bool operator==(const iterator& other) {
return (&other.owner == &owner && other.x == x);
}
};
This works well for iterating and the iterator is now copyable. The problem now is that:
for (const auto& x : idmp) {
x.second = T();
}
compiles without error even though const auto&
is supposed to capture a const std::pair
. That is how std::unordered_map
behaves in the same situation. Any ideas?
EDIT3 :
Even better idea is to use a byte storage and use placement new to keep the std::pair
in the iterator, getting rid of the boost variant:
class iterator {
private:
idmap& owner;
ind x;
static constexpr uint szp = sizeof(std::pair<ind, const T&>);
static constexpr uint szpr = sizeof(std::pair<ind, const T&>);
static constexpr uint sum_size = boost::static_unsigned_max<szp, szpr>::value + 1;
uint8_t _p[sum_size];
public:
iterator(idmap& ic, ind x) : owner(ic), x(x) {}
iterator& operator++() {
x = owner._v[x]._next;
return *this;
}
const std::pair<ind, T&>& operator*() const {
new (const_cast<iterator*>(this)->_p) std::pair<ind, T&>(x, owner._v[x]._t);
return *((std::pair<ind, T&>*)const_cast<iterator*>(this)->_p);
}
std::pair<ind, T&>* operator->() const {
new (const_cast<iterator*>(this)->_p) std::pair<ind, T&>(x, owner._v[x]._t);
return (std::pair<ind, T&>*)const_cast<iterator*>(this)->_p;
}
bool operator!=(const iterator& other) {
return (&other.owner != &owner || other.x != x);
}
bool operator==(const iterator& other) {
return (&other.owner == &owner && other.x == x);
}
};
The for(const auto& x : idmp)
still does not behave like std::map
would, aka x
becoming read-only.
question from:
https://stackoverflow.com/questions/65948691/iterator-for-custom-map-operator-overload-using-dummy-reference