CODEWITHSUNDEEP
c++boostboost-multi-index
Niko
Niko

Reputation: 257

Filter and modify elements in boost::multi_index from an equal_range query

I have a boost::multi_index with a hashed_non_unique view. What I would like to accomplish is, given a key in that view, use

pair<myIter, myIter> iterRange = myView.equal_range(key);
for (myIter iter = iterRange.first; iter != iterRange.second; ++iter) {
    // ...
}

to find all elements associated with that key. Then, run these elements through a filter

bool filter(Element e) { /* some filtering logic*/ }

and modify the filtered results with a modifier

void modifier(Element e) { /* modify the elements with e.g. myView.modify() */ }

However, simply putting these pieces together doesn't work since modifying the elements results in reordering of the multi_index, which renders my iterRange invalid.

What would be the correct way to do this? Thanks!

Upvotes: 1

Views: 657

Answers (2)

Joaqu&#237;n M L&#243;pez Mu&#241;oz
Joaqu&#237;n M L&#243;pez Mu&#241;oz

Reputation: 5658

Some comments to your proposed solution:

  • BMIter is not special as you seem to imply, but merely the iterator associated to the first index of the container. Note that this will be the same as myIter when myView happens to be this first index.
  • Nevertheless, iterators of hashed indices are not invalidated by insertions or modifications, so you're safe. In fact, you could have defined iters as a vector<myIter> and store the iterators directly without any further conversion --you're still achieving the intended effect of not being affected by potential reorderings after modification.
  • Even though what you're doing is perfectly fine, if you're into squeezing some additional performance note that modification of elements in a hashed index does not change the underlying ordering when the key remains equivalent, so the only way a reordering can possibly affect you when traversing a range of equivalent keys is when a modified element jumps directly after the range (i.e, just before iterRange.second). With this mind, you can spare the iters trick as follows:

 

for (myIter iter = iterRange.first; iter != iterRange.second; ) {
    auto nextIter = std::next(iter);
    if (filter(*iter)) {
        myView.modify(iter, modifier);
        if (nextIter != iterRange.second && std::next(iter) == iterRange.second)
            iterRange.second = iter;
    }
    iter = nextIter;
}

Upvotes: 2

Niko
Niko

Reputation: 257

I think I've found the answer myself. Instead of simply modifying the elements inside the for loop, we need to cache the elements first and modify them later to avoid altering the ordering. The trick here is, instead of caching the iterators to this specific view, cache instead iterators to the elements themselves, i.e.

vector<BMIIter> iters;
for (myIter iter = iterRange.first; iter != iterRange.second; ++iter) {
    if (filter(*iter)) {
        iters.push_back(myBMI.iterator_to(*iter));
    }
}
for (auto iter : iters) {
    myBMI.modify(iter, modifier);
}

Note that BMIIter and myIter are different iterator types - the former is an iterator to the element itself, while the latter is iterator specific to myView. Modifying elements in the multi_index invalidates the latter, but the former still holds valid even after reordering happened.

Upvotes: 0

Related Questions