[slot_map] R1/R2 criticisms

[p-groarke]

I would like to challenge some decisions made in P0661r1 from SG14.

P0661r2 states the following question was asked and answered.
R1 | Should raw access to the underlying container be provided? | No. | SG14

This is inconsistent with the current behavior, as the container returns the underlying container iterators. This means you already have access to the underlying container either through begin and end.
I believe const access to the underlying container should be available, at a minimum. I would prefer full access to the underlying container. See my next contention point for more details on why this is preferred.

Another decision I would like to challenge is direct access to the underlying container iterators.

It also provides the following iterator type aliases. Note that the adapted container must provide iterators satisfying the constraints of RandomAccessIterator.

using iterator = typename Container<value_type>::iterator;
using const_iterator = typename Container<value_type>::const_iterator;
using reverse_iterator = typename Container<value_type>::reverse_iterator;
using const_reverse_iterator = typename Container<value_type>::const_reverse_iterator;

The access to the underlying container iterators is dangerous. I've already shot myself in the foot assuming coherent behavior between slot_map iterators and its keys. I believe many more will.

Furthermore, it precludes using standard algorithms like std::partition. I fear the slot_map api will grow, with many custom cases that will need special implementations. It is already starting : #133

An alternative would be to provide custom, "smart and safe", iterators that do not invalidate the relationship between keys and elements stored in the container. Iterator swap, for example, should swap elements and shouldn't invalidate keys. In fact, no iterator operation should invalidate keys, ever.

This may make slot_map iterators heavy or less performant (TBD in test implementation), which may be a problem. Again, I believe direct access to the underlying container would be a better way to deal with this issue. When a user accesses the underlying container, it is clear he is in "no mans land". When you use slot_map iterators, operations should be safe, always.

Currently, using slot_map iterators is no mans land... Yet SG14 doesn't agree underlying container access is a good idea. This doesn't seem coherent.

I would appreciate some feedback on the types of pitfall you may fall into with custom iterators.

Thank you, looking forward to your feedback.

[Quuxplusone]

iterators ... std::partition ... #133

I'm intrigued by the idea of slot_map::iterator being able to preserve keys across standard algorithms, but I'm afraid I don't see how that's implementable. I'd like to see you (or someone, but I disvolunteer myself) come up with a set of (failing) unit tests that we want to make pass. That means unit tests for iter_swap (I assume that's what you meant by iterator swap?), partition, sort, remove_if, and whatever else you'd expect to work. Once we have the test cases, then we can think concretely about how to make them pass.

There's nothing inherently wrong with making algorithms into member functions when that's the performant or correct thing to do: see list::sort and set::find for examples. (And note that running e.g. std::remove_if on a set isn't going to work at all.) Slotmap has its own unique set of weirdnesses, but I don't think it's necessarily more weird than list or set; it's just unfamiliar.

---

access to the underlying container

Personally I'd be strongly in favor of public access to the container — Container& container(), const Container& container() const — if this were my own codebase. As you say, it's the right thing to do. The only qualm I have is that the standard container adaptors don't do that (but they do a wacky protected-data-member thing that we're definitely not going to copy, so, maybe whatever).

[p-groarke]

That means unit tests for iter_swap (I assume that's what you meant by iterator swap?)

Maybe you can correct my assumption, cplusplus.com lists swap as a requisite (in their c++11 section) http://www.cplusplus.com/reference/iterator/RandomAccessIterator/
cppreference doesn't mention it...

I'll start experimenting with those iterators and see where (if) they break. partition, sort and remove_if seem like a good starting point. We can add more if safe slot_map iterators can work (yet to be proven).

but they do a wacky protected-data-member thing that we're definitely not going to copy, so, maybe whatever

I agree, lets not do that.

[p-groarke]

There's nothing inherently wrong with making algorithms into member functions when that's the performant or correct thing to do: see list::sort and set::find for examples.

Here I was thinking in terms of standardization. I have no experience in that regard, I just thought this might come up. Good to hear it's not an issue.

[Quuxplusone]

Maybe you can correct my assumption, cplusplus.com lists swap as a requisite (in their c++11 section) http://www.cplusplus.com/reference/iterator/RandomAccessIterator/
cppreference doesn't mention it...

The Cpp17Iterator requirements require that "lvalues of type X are swappable," so cplusplus.com is correct.

However, that's talking about swapping iterators. Swapping iterators themselves doesn't ever * the iterators, just like swapping pointers doesn't * the pointers.

slot_map<int> sm; sm.insert(1); sm.insert(2);
auto a = sm.begin(), b = a+1;
auto it1 = a, it2 = b;
assert(it1 == a && it2 == b);
{
    using std::swap;
    swap(it1, it2);  // "swap"
}
assert(it1 == b && it2 == a);  // the iterators' values have correctly been swapped

---

Based on my intuition, I'd argue that iter_swap does the right thing as-is:

using Monster = std::string;
slot_map<Monster> sm;
auto k1 = sm.insert("orc");
auto k2 = sm.insert("cleric");
auto it1 = sm.begin(), it2 = it1+1;

assert(sm.at(k1) == "orc" && sm.at(k2) == "cleric");
assert(sm.find(k1) == it1 && sm.find(k2) == it2);
std::iter_swap(it1, it2); // Now swap these two Monsters.
assert(sm.at(k1) == "cleric" && sm.at(k2) == "orc");
assert(sm.find(k1) == it1 && sm.find(k2) == it2);  // The physical objects themselves
    // have not moved; we just swapped their attributes.

[p-groarke]

Thanks for the details and example. I was confusing swap with iter_swap 👍

So, to reiterate, the goal would be to specialize iter_swap. It should take into account slot_map keys and "fix them up". If partition and sort use iter_swap, bingo bango bobs your uncle.

cppreference's "possible implementation" of partition uses iter_swap, so I'm going to assume that's standardized. Seems feasible so far.

[Quuxplusone]

So, to reiterate, the goal would be to specialize iter_swap. It should take into account slot_map keys and "fix them up".

But surely you agree that the following is correct?

using Monster = std::string;
slot_map<Monster> sm;
auto k1 = sm.insert("orc");
auto k2 = sm.insert("cleric");
auto it1 = sm.begin(), it2 = it1+1;

Monster& m1 = *it1, m2 = *it2;  // yes?
assert(m1 == "orc" && m2 == "cleric");
assert(m1 == sm.at(k1) && m2 == sm.at(k2));
std::swap(m1, m2);
assert(m2 == "orc" && m1 == "cleric");  // surely?
assert(m1 == sm.at(k1) && m2 == sm.at(k2));  // surely remains true?

So you're asking for iter_swap(it1, it2) to do something fundamentally different from swap(*it1, *it2). I think this is going to lead to a dead end.

But I should be quiet and let you bang your own head against it for a while. I'll try to. :)

[p-groarke]

But surely you agree that the following is correct?

Yes absolutely! swap wouldn't change at all. I was mixed up. swap on references (or elements) should behave like it does everywhere. Swap the value.

What I intend to happen is iter_swap would swap(*it1, *it2), plus some extra steps so it doesn't invalidate keys.

using Monster = std::string;
slot_map<Monster> sm;
auto k1 = sm.insert("orc");
auto k2 = sm.insert("cleric");
auto it1 = sm.begin(), it2 = it1+1;

std::iter_swap(it1, it2);

// stable keys
assert(sm.at(k1) == "orc");
assert(sm.at(k2) == "cleric");

// underlying data has moved though
assert(sm.find(k1) == sm.begin() + 1);
assert(sm.find(k2) == sm.begin());

But I should be quiet and let you bang your own head against it for a while. I'll try to. :)

Haha it's ok, you have much more experience than I do in these areas. I'm not that fluent in iterators. This will be a good experiment to get up to speed. Plus, I have no super complicated c++ to bang my head on these days :)

[p-groarke]

@Quuxplusone You are right it isn't as simple as I thought to "specialize" or overload iter_swap. I still have a few other techniques to try out, but it might be a dead end. It's unfortunate as I think that would have made the container much more safe and "standard".

Here is another point I would like to bring up :
R1 | Are insert_at() and emplace_at() interfaces desired? | No. | SG14

What about serialization/deserialization? Could we offer a (potentially limited) way to insert an object at key key?

[Quuxplusone]

What about serialization/deserialization?

Serialization is an interesting use-case. I could see a use for "serialize this whole slotmap sm; also serialize this key k; then deserialize the slotmap and the key, and assert that sm.at(k) still has the same value." However, that would first depend on having an API for serialization of anything at all. My impression is that there are a lot of incompatible solutions in that area, and "make everything work" is an unrealistically big scope. I suggest that it would be appropriate to open a new issue titled e.g. "Make slot_map work with Boost.Serialization" — but only if that's a feature that your codebase actually needs! We need "exit criteria" — a way of knowing whether a given chunk of code actually solves the problem or not — and for that we need a very well-defined problem.

Could we offer a (potentially limited) way to insert an object at key key?

In the context of serialization, no, I assume we'd serialize/deserialize a whole slotmap at once.

A priori I think the slotmap ought to have control over its keys, so no. If I have a made-up key and a slotmap sm, there are three possibilities:

• sm.container()[key.index] is occupied and key.gen is correct. I can assign-over this object.
• sm.container()[key.index] is empty. I could theoretically insert_at this key.
• sm.container()[key.index] is occupied and key.gen is incorrect. I cannot even theoretically insert_at this key because there's already an object occupying its desired slot.

A priori I think the user really shouldn't crack open key objects to inspect their index and generation fields — users should treat keys as opaque tokens.

[p-groarke]

"Make slot_map work with Boost.Serialization" — but only if that's a feature that your codebase actually needs!

Since I do not use boost (and gaming slot_map users probably wont either), I'd say relying on boost is a bad idea. I'm not against an api for serialization however.

Providing access to the underlying vector data() and key slots.data() may be enough? At that point, you are really offering the shotgun to the user, but I'm afraid the types of users interested in slot_map will want to do advanced things with it. I know I do. I'm open to suggestions however.

Ultimately, we need a way to serialize/deserialize.

A priori I think the user really shouldn't crack open key objects to inspect their index and generation fields — users should treat keys as opaque tokens.

I'm not so sure, but I'm happy with letting this go until I have another use-case than serialization.

[Quuxplusone]

I think all you need for the most naïve serialization is a way to get "for each item in the slotmap, print out the item and its key." You can do all of this today except for "...and its key"; and #141 proposes a sm.key(iter) method. So

os << '{';
for (auto it = sm.begin(); it != sm.end(); ++it) {
    os << sm.key(it) << ": " << *it << ", ";
}
os << '}';

And then for deserialization, you'd need a way to forcibly "insert item at (non-colliding) key." Or, more arcanely, since the keys always come in numerical order by index, "insert item with forced generation number g" would do the trick.

But yeah, I think we'd need to see a use-case before trying to actually design.

[p-groarke]

A working [hackish] implementation of custom iter_swap can be found here : https://github.com/p-groarke/slot_map/blob/master/include/slot_map/slot_map.h

It doesn't work with std::sort or std::remove_if on MSVC as they do not use iter_swap for those :/

It will "fixup" the keys when iter_swap is called on slot_map iterators. I simply copy-pasted your underlying_swap in #133. There are many caveats, but it is a proof-of-concept so I'm fine with that for now.

To make safer iterators work, we need to wrap the adapted container iterators. I used a similar implementation as one would with reverse iterators. The non-const iterator provides a static iter_swap implementation. I don't think it makes sense for const iterators. This means the non-const iterator has an extra member, a reference_wrapper to his owner. This lets you achieve the desired results.

I needed to specialize iter_swap in std namespace by using only 1 template parameter. This means you need to include slot_map before algorithms that use it, which is unacceptable for something production ready.

A seperate proposal to change iter_swap would be required. std::iter_swap now uses is_detected to discover if the passed-in iterator types have a custom implementation of iter_swap. If so, it calls that, if not, it calls std::iter_swap. I doubt this is the best way to achieve the desired result, I am open to ideas here.

Further experimentation is required to find out if std::sort and std::remove_if could work. By "could work", I mean keep the keys stable after running them. There may be hope for the erase remove_if combo. TBD.