Container that has iterators to itself in the value_type

[Marcel Mueller]

I have a data structure (for signal processing) where a std::map
contains iterators to it's own elements. I.e.

typedef multimap<key_type, element_type> map_type;
typedef map_type::iterator element_type;

Of course, I can't write this, because the definition is recursive.
However the resulting data structure is not recursive, since the
iterator has finite size. Is it possible to define a type of this kind?

The iterators are required to maintain a second independent sort order,
that only needs a linked list because it only requires the operations
pop_front and push_back.


Marcel

[Victor Bazarov]

What would your container contain if it only had one element? IOW, what
happens when it goes from empty to ??? upon the first insertion?

V
--
I do not respond to top-posted replies, please don't ask

[Öö Tiib]

When there is need to have same elements to be indexed in several
ways then you may want to consider one of:
* Boost.Bimap
* one base container, others containers of iterators to base container.
* one base container, others Boost.Intrusive containers.
* Boost.MultiIndex

One of these choices performs likely close enough to optimal for
your needs.

[Marcel Mueller]

On 28.04.15 22.33, Victor Bazarov wrote:
>> The iterators are required to maintain a second independent sort order,
>> that only needs a linked list because it only requires the operations
>> pop_front and push_back.
>
> What would your container contain if it only had one element? IOW, what
> happens when it goes from empty to ??? upon the first insertion?

The first entry gets end(). When the second entry is inserted the first
one is changed to the iterator returned from the second insert and so
forth. So the linked list keeps the insertion sequence to drop the
oldest elements after a specified size has been reached. I only need to
keep an iterator to the oldest element (head) for removal and one to the
newest element (tail) for replacing end() of the last entry.


Marcel

[Victor Bazarov]

On 4/28/2015 6:44 PM, Marcel Mueller wrote:
> On 28.04.15 22.33, Victor Bazarov wrote:
>>> The iterators are required to maintain a second independent sort order,
>>> that only needs a linked list because it only requires the operations
>>> pop_front and push_back.
>>
>> What would your container contain if it only had one element? IOW, what
>> happens when it goes from empty to ??? upon the first insertion?
>
> The first entry gets end().

OK, so the first entry makes your map non-empty. In other words, the
map contains one element, and therefore its iterators are now end()
(which is kept in the first element) and the one that is not 'end()',
i.e. the iterator to the "first" entry, whose content is 'end()', yes?
And where is that iterator kept? You seem to immediately need to insert
another element into your map which should contain the iterator to the
first non-end() iterator. That is, your map now contains two entries,
the first of which is 'end()', the other is the iterator of the "real"
element... And so on.

> When the second entry is inserted the first
> one is changed to the iterator returned from the second insert and so
> forth.

When? And where is the consistency of the map? It will always contain
one element iterator to which is not kept in the same map? 8-O

> So the linked list keeps the insertion sequence to drop the
> oldest elements after a specified size has been reached. I only need to
> keep an iterator to the oldest element (head) for removal and one to the
> newest element (tail) for replacing end() of the last entry.

What is it you're trying to model with that paradoxical structure? And
why a map? If you need a circular buffer, find and use a circular
buffer. I am sure there are numerous examples of such an adapter.

[Öö Tiib]

It feels like when there is

std::array<Something,SpecifiedSize> insertion_sequence;

whose elements can be same time also in

boost::intrusive::multiset<Something> lookup_set;

So he can O(log SpecifiedSize) find an element by some criteria from
the sequence instead of O(SpecifiedSize).

[K. Frank]

Hello Marcel!

You raise a very interesting question (for which I don't
have a clean answer).

Without going into why you might want to do this or
whether it would be a good idea, I do think you raise
a very interesting general point.

In the "old days" you might do something like:

typedef struct Element { Element* pElement; } element_type;
typedef element_type collection_type[30];

This is a very standard usage, purposely supported
by the language, and used, e.g., by the classic linked
list.

This works because you can use pointers to incomplete
types. (You can also forward-declare incomplete types.)

Now one aspect of iterators is that they are abstractions
or generalizations of pointers. So you raise the very
natural question of how or whether the same thing might
be done with iterators.

As far as I know, you can't, but I would love to be
shown wrong.

Of course, "All problems can be solved by another level
of indirection." So you could do something like:

#include <map>
using std::multimap;

struct iterator_wrapper;

typedef int key_type;
typedef iterator_wrapper* element_type;

typedef multimap<key_type, element_type> map_type;

typedef map_type::iterator iterator_type;

struct iterator_wrapper { iterator_type it; };

This, to my mind, has two imperfections: Iterators are
already a form of indirection, so the extra level of
indirection -- element_type is a pointer -- seems
conceptually unnecessary, and could add a little cost.

Also, while adding no run-time cost, the need to wrap
the iterator in iterator_wrapper (I don't see any way
to avoid this.) seems unfortunate.

Your desired use case illustrates a feature of pointers
that iterators do NOT provide. Would it make sense for
the language / standard library to provide such functionality
for iterators? (And would it be possible, given that
standard-library collections are templates?)

> Marcel


Best regards.


K. Frank

[Marcel Mueller]

On 29.04.15 01.49, Victor Bazarov wrote:
> OK, so the first entry makes your map non-empty. In other words, the
> map contains one element, and therefore its iterators are now end()
> (which is kept in the first element) and the one that is not 'end()',
> i.e. the iterator to the "first" entry, whose content is 'end()', yes?

Exactly.

> And where is that iterator kept? You seem to immediately need to insert
> another element into your map which should contain the iterator to the
> first non-end() iterator. That is, your map now contains two entries,
> the first of which is 'end()', the other is the iterator of the "real"
> element... And so on.

The other way around. Inserting the second element changes the first
elements iterator (= value) to the iterator returned by the second
insertion. The lastly inserted element always has the value end().
The iterator to the last insert, named tail, is kept outside to setup
the value to link to the next insertion.

> > When the second entry is inserted the first
>> one is changed to the iterator returned from the second insert and so
>> forth.
>
> When? And where is the consistency of the map?

Changing values does not effect the consistency of the map.

> > So the linked list keeps the insertion sequence to drop the
>> oldest elements after a specified size has been reached. I only need to
>> keep an iterator to the oldest element (head) for removal and one to the
>> newest element (tail) for replacing end() of the last entry.
>
> What is it you're trying to model with that paradoxical structure? And
> why a map? If you need a circular buffer, find and use a circular
> buffer. I am sure there are numerous examples of such an adapter.

It is a moving median filter. Take a floating point value stream and
calculate the median for every N consecutive values.
If I use ordinary median calculations I need to perform a sort of every
consecutive set of N values, ending up with a complexity of O(M N log N)
with M = stream length and N = window size. But when I am able to
transform the sorted set of values[0:N] into values [1:N+1] then it is
significantly faster. All I need to know for this purpose is the oldest
value to remove it. So a linked list fits best. And for the sorted set I
need to have iterators that survive insertions and deletions. That's why
the map. The complexity is now O(M log N) which is quite fast. Using a
custom allocator that always allocates from a pool of exactly N entries
will furthermore remove any memory allocations from the stream
processing code.


Marcel

[Marcel Mueller]

On 29.04.15 20.50, K. Frank wrote:
> Your desired use case illustrates a feature of pointers
> that iterators do NOT provide. Would it make sense for
> the language / standard library to provide such functionality
> for iterators? (And would it be possible, given that
> standard-library collections are templates?)

To make this work it is required that the footprint of the iterator does
not depend on the type arguments of the container. AFAIK there is no
such guarantee.
This concept requires type erasure rather than templates. Of course, one
could build containers that satisfy this need, since it is uncommon that
iterators depend on the element type other than for the purpose of
strongly typed methods and type safety. (I have already seen iterators
that store a copy of the current element - not with C++, of course.)

However, even if it is quite trivial to implement the type erasure from
the container's point of view I have no idea how to get a type safe
syntax for the language. This would require to define iterator types
with incomplete types. And unfortunately nested types do not allow
forward declarations. (An annoying restriction.)

[... some tests later]

At least gcc 4.8 eats this:

#include <map>
#include <stdio.h>
using namespace std;

int main()
{
struct elem;
typedef multimap<int,elem> map_type;
typedef map_type::iterator iter_type;
struct elem : public iter_type
{ elem(const iter_type& i) : iter_type(i) {}
};

map_type my_map;
auto first = my_map.emplace(1,my_map.end());
auto last = first;
last = last->second = my_map.emplace(0,my_map.end());
last = last->second = my_map.emplace(3,my_map.end());

// access by sequence
for (auto cur = first; cur != my_map.end(); cur = cur->second)
printf("%i\t", cur->first);
putchar('\n');

// access by key
for (auto cur : my_map)
printf("%i\t", cur.first);
putchar('\n');

return 0;
}

But I did not succeed without the helper struct since you cannot forward
declare a typedef, isn't it? Although this work around is quite
tolerable since it neither causes runtime overhead nor code bloat.

Furthermore I am unsure whether this is a feature of gcc or it is
covered by the standard.
And, of course, it would be even more pretty w/o the helper struct.


Marcel