Comments (12)
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.
from sg14.
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).
from sg14.
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.
from sg14.
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.
from sg14.
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.
from sg14.
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. :)
from sg14.
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 :)
from sg14.
@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
?
from sg14.
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 andkey.gen
is correct. I can assign-over this object.sm.container()[key.index]
is empty. I could theoreticallyinsert_at
this key.sm.container()[key.index]
is occupied andkey.gen
is incorrect. I cannot even theoreticallyinsert_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.
from sg14.
"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.
from sg14.
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.
from sg14.
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.
from sg14.
Related Issues (20)
- [slot_map] constructors HOT 1
- [inplace_function] benchmark HOT 4
- [slot_map] Can you get a key using an iterator? HOT 5
- [inplace_function] Ambiguous overloads. HOT 5
- [inplace_function] Should [](){return 42;} be convertible to inplace_function<void()>? HOT 1
- [inplace_function] make it usable without exceptions HOT 2
- inplace_function doesn't handle arguments with rvalue references well HOT 1
- [inplace function] Problems assigning if my starting point is empty/nullptr HOT 4
- [inplace_function] Const-callability means thread-safety HOT 4
- [inplace_function] Giant Sized Buffers Required for Compilation HOT 5
- volatile inplace_function fails to compile HOT 6
- License is missing on some includes HOT 1
- `sg14::ring_span`: clear () member function gone awol HOT 2
- [inplace_function] Opt-in "safe" default constructed inplace_function HOT 7
- Provide CMake & Conan installation support
- slot_map: custom key causing clang to seg fault. HOT 1
- [inplace_function] usage at shared library boundaries HOT 5
- sg14::span_ring: class template argument deduction
- [inplace_function.h] Copyright holder HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. πππ
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google β€οΈ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from sg14.