Jump to content
  • Advertisement
matt77hias

STL compliant and transparent container of containers

Recommended Posts

Is it possible to implement a STL compliant (e.g., support for std::remove, std::partition, std::sort, etc.) container containing multiple containers? So reordering one container based on some criteria results in the reorganization of other containers as well.

Example 1: unidirectional map where the keys are stored in contiguous memory and the values are stored in contiguous memory with a 1-1 correspondence based on the index (e.g., the key at index n and the value at index n constitute a key-value pair of the mapping)?

std::vector< KeyT > keys;
std::vector< ValueT > values;

Example 2: bidirectional map where the keys are stored in contiguous memory and the values are stored in contiguous memory with a 1-1 correspondence based on the index, and an additional mapping from keys to value indices.

std::vector< KeyT > keys;
std::vector< ValueT > values;
std::unordered_map< KeyT, std::size_t > key_value_mapping;

The above code fragments are just for illustrating a possible data layout satisfying the constraints. The major problem, however, is that reordering (e.g., removing, erasing, partitioning, sorting) values requires reordering keys and key_value_mapping as well. This basically bottles down to the iterators of the containers. I am not sure if one can implement some custom iterators handling the job for operator*, operator-> and operator[] transparently, since the corresponding elements of different containers are stored at different memory locations. Furthermore, it is not very transparent as well (example).

Edited by matt77hias

Share this post


Link to post
Share on other sites
Advertisement
23 minutes ago, Gnollrunner said:

Is there some reason you just don't put KeyT and ValueT together in a structure and then put that in your vector?

Cache coherency and hot paths. The values are packed and aligned in a minimal and optimal way. Furthermore, in most cases the values will be iterated without requiring the corresponding key. The additional boilerplate is for the few cases where the key is required as well or given the key, the corresponding value needs to be obtained.

To make this more concrete: let the values be components and the keys be entities as in an ECS design.

Share this post


Link to post
Share on other sites

Well I don't really use STL much but I've built a LOT of containers. It seems like what you want isn't too hard to implement. You can wrap pair of vectors in a new template and then wrap just the functionality you need such that your member functions do the same manipulation on both vectors. Alternatively you can build your own template from scratch. I'm not sure what you mean by STL compliant.

Share this post


Link to post
Share on other sites
37 minutes ago, Gnollrunner said:

Alternatively you can build your own template from scratch. I'm not sure what you mean by STL compliant.

It is of course pretty easy to write such a container that is not STL compliant; that is not the challenge. What I mean and want is a container and more importantly some associated iterators that are compatible with the functions provided in algorithm (e.g., works with std::remove, std::partition, std::sort, etc.).

Edited by matt77hias

Share this post


Link to post
Share on other sites

Make the iterator an class that stores both n and a reference to the container. As long as you implement the operator functions of that class consistently with the intended iterator semantics, I don't see how it would fail. Likely though the invalidation of other iterators to the same container is a bit different (probably close to a vector).

 

Share this post


Link to post
Share on other sites
14 minutes ago, matt77hias said:

It is of course pretty easy to write such a container that is not STL compliant; that is not the challenge. What I mean and want is a container and more importantly some associated iterators that are compatible with the functions provided in algorithm (e.g., support for std::remove, std::partition, std::sort, etc.).

Ahh yes, now I'm remembering why I hate STL.  Something simple becomes a challenge.

Share this post


Link to post
Share on other sites
3 minutes ago, Gnollrunner said:

Ahh yes, now I'm remembering why I hate STL.  Something simple becomes a challenge.

Indeed. The benefit if possible, however, is reusing the already existing code (instead of reinventing the hot water) which saves some headaches as well 😉

Share this post


Link to post
Share on other sites
1 minute ago, matt77hias said:

Indeed. The benefit if possible, however, is reusing the already existing code (instead of reinventing the hot water) which saves some headaches as well 😉

In my experience the headaches come in when you have to debug a problem with it, or are tying to do something that the designer never thought of. I think most what you want can be done with some wrapping and sub-classing however the sort might be a trick. 

Share this post


Link to post
Share on other sites

Your type, VectorPair<K,V>, should have an iterator which dereferences to a VectorPair<K,V>::Stripe. A Stripe is just a value-type struct which momentarily stands in for a position in each target vector (it ought to get optimized away, don't worry). It will respond to operator<(Stripe, Stripe) by comparing keys between Stripes, and it has an overload of std::swap() which defers to the *Key and *Value target vector iterators separately.

Then, use standard std::sort-family methods to assert ordering upon the VectorPair<> after mutation. You'll also need < to work correctly when comparing K values against a Stripe, if you want std::binary_search to work correctly.

Your call if it's worth extending to OuterTuple<A,...> for arbitrary width stripes between an arbitrary RandomAccessIterable collection type.

Edited by Wyrframe
clarification, spelling

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!