/* Introducing "indexitor", a new C++ container... */

[Mr Flibble]

int main(int argc, char* argv[])
{
/* Introducing "indexitor", a new C++ container... */

std::vector<int> v;
for (int i = 0; i < 15; ++i)
v.push_back(i + 700);

neolib::indexitor<std::string, std::size_t> idx;

idx.push_back(std::make_pair("first", 5));
idx.push_back(std::make_pair("second", 5));
idx.push_back(std::make_pair("third", 5));

/* idx is holding three elements which map to first 5,
second 5 and third 5 elements respectively of a foreign container. */

/* Now for primary use-case: modify foreign container: */
v.erase(v.begin() + 2); // remove third element
auto ii = idx.begin();
idx.update_foreign_index(idx.begin(), 5 - 1); // update indexitor

for (std::size_t i = 0; i < v.size(); ++i)
std::cout << i << ": " << idx.find_by_foreign_index(i)->first << " ->
" << v[i] << std::endl;

/* All indexitor index/update operations are worst-case O(lg N)
complexity. */
}

Output:

0: first -> 700
1: first -> 701
2: first -> 703
3: first -> 704
4: second -> 705
5: second -> 706
6: second -> 707
7: second -> 708
8: second -> 709
9: third -> 710
10: third -> 711
11: third -> 712
12: third -> 713
13: third -> 714

Download (at own risk as not yet fully tested) from:

https://github.com/FlibbleMr/neolib

[Rick C. Hodgin]

What do you gain by this?

Best regards,
Rick C. Hodgin

[Mr Flibble]

If you have to ask that question then you probably don't need it.

/Flibble

[Rick C. Hodgin]

Mr Flibble wrote:
> If you have to ask that question then you probably don't need it.

I haven't seen the flood of, "Awesome, Leigh!" "What I've been
looking for!" "Where's the donate button? This is worth its weight
in gold!" "Wow this is so handy and feature rich! Awesome!" posts.

Perhaps I haven't given your indexitor contribution to mankind
enough time yet. I'll wait a bit longer for the flood of attaboys,
and I'll deduce from the chatter what I'm missing today.

My apologies for responding too quickly.

[Mr Flibble]

At some point I will write a page about indexitor, it's rationale and
how to use it but briefly:

you want a sequence container of items that include a reference to an
element in another (foreign) container, so you could use:

std::vector<std::pair<foo, foreign_iterator>>

but this is no good if the foreign container iterators can be
invalidated if changes (insert/erase element) are made to the foreign
container however if the foreign container can be indexed numerically
(for e.g. by vector::operator[] or std::deque::operator[]) then you
could use:

std::vector<std::pair<foo, std::size_t>>

where the second item is the index to the foreign container element
HOWEVER if you change the foreign container (insert/erase element) you
will have to update all indexes after the change which is O(n)
complexity but with:

indexitor<foo, std::size_t>

the same can be achieved with O(lg N) complexity. How does this work?
Well instead of storing indexes we store intervals and we use a tree to
allow O(lg N) complexity indexing.

A common mistake might be to think that I am reimplementing std::map but
indexitor is not an associative container: it is a sequence container
with random access like vector or deque. Also std::map is a single
container whilst this is a solution that allows us to have multiple
foreign containers.

/Flibble

[Öö Tiib]

Logic of the idexitor feels like that of somewhat constrained multimap
to references or map to pairs of references. IOW it can hold one-to-many
relations under certain constraints. Does indexitor achieve that it is
cheaper to update the innuendoes to other container when needed? Are there
other positive effects?

When I need to reduce the cost of updating references or iterators in
"indexing containers" of elements of "other container" then I typically
use containers with stable references (huge variety std:: [forward_]list
/ [multi]set / [multi]map, boost::intrusive:: [s]list / [multi]set)
as that "other container" or use boost::multiindex::multi_index_container
for the whole problem. What is indexitor's benefit compared to those
approaches?

[Mr Flibble]

The benefit is that you don't have to use containers with stable
references.

/Flibble

[Öö Tiib]

Yes, I understood, but what is that benefit?

When inserts and erases from middle of sequence are frequent enough to
cause performance issues with vector (or deque) then first suggestion is
to consider containers with cheaper inserts and erases.

Now, there must be something that talks strongly against those other
containers (despite inserts and erases in middle of sequence are
frequent) and so makes us to desire that indexitor instead.

What it is?

[Mr Flibble]

I use indexitor with my segmented_array container which does have fast
inserts/erases in the middle but does not have stable references. There
exists other similar containers too. indexitor itself also has fast
inserts/erases in the middle and fast (O(lg N)) random access.

/Flibble