elements in iterator range [__first, __last) are not partitioned

[synss]

I have written an "associative vector" following Matt Austern, http://lafstern.org/matt/col1.pdf and Scott Meyers, Effective STL, Item 24. I have debugged it by comparing its results with std::map<string, int> and all the methods give expected results. Now, when I want to use it in my program, I get the following error I do not understand and google did not help

/Developer/SDKs/MacOSX10.5.sdk/usr/include/c++/4.0.0/bits/stl_algo.h:2691:
    error: elements in iterator range [__first, __last) are not partitioned     
    by the predicate __comp and value __val.

Objects involved in the operation:
iterator "__first" @ 0x0x7fff5fbfac80 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPKSt4pairIN9Diffusion6Bridge17Energy_Lookup_KeyEdEN10__gnu_norm6vectorIS7_SaIS7_EEEEEN15__gnu_debug_def6vectorIS7_SC_EEEE (constant iterator);
  state = dereferenceable (start-of-sequence);
  references sequence with type `N15__gnu_debug_def6vectorISt4pairIN9Diffusion6Bridge17Energy_Lookup_KeyEdESaIS5_EEE' @ 0x0x7fff5fbfac80
}
iterator "__last" @ 0x0x7fff5fbfac50 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPKSt4pairIN9Diffusion6Bridge17Energy_Lookup_KeyEdEN10__gnu_norm6vectorIS7_SaIS7_EEEEEN15__gnu_debug_def6vectorIS7_SC_EEEE (constant iterator);
  state = past-the-end;
  references sequence with type `N15__gnu_debug_def6vectorISt4pairIN9Diffusion6Bridge17Energy_Lookup_KeyEdESaIS5_EEE' @ 0x0x7fff5fbfac50
}
Program received signal:  “SIGABRT”.

As you can see, I am developing on OS X and the debug version of std::vector::iterator uses checked iterators. The only thing I do is replace the std::map<X, Y> with associative_vector<X, Y>. The error is triggered by a call to std::lower_bound, but I checked the key and it seems OK. The error is shown only about the 32nd time the call is made and I see similar keys passed to lower_bound before that without problem.

Where should I look to find what is wrong?

[iMalc]

Where should I look to find what is wrong?

In your "associative vector" I'm afraid.

I have read that article before and it doesn't seem to bring up the fact that implementing an associative container using a vector will result in different iterator invalidation rules. Perhaps the algorithm you are using relies on some of those iterator invalidation rules? I don't know. Or maybe it is just a plain old bug. Actually re-reading your post, it sounds like the problem is that somehow your container isn't perfectly sorted when you call lower_bound.

Would you by chance like to post your implementation here, or attach it? We might spot an error you have overlooked.

I considered writing one of these myself after having read the article, but I figured someone else would have already done so.

[synss]

Thank you, I also thought somebody would have done it, but I could not find anything I would like to use (I found only one and did not like it, actually) so I went with mine. I do not mean to keep the code secret, so here it is, feel free to use it if it fits your needs and if it works for you! I provide const and non const overloaded methods everywhere, it is up to the user to keep the order while changing the keys. Maybe the non-const versions should be removed. In my program, I fill the associative vector, then I only fetch values into it, so I would think iterator invalidation is not the problem, although if I knew where the problem is... If the bug is solved, I do not mind posting my sorted_vector for everyone to use (replacement for std::set) but now, I would guess it has the same bug.

[CornedBee]

Have you looked at flat_map from Boost's interprocess library? They're in the interprocess library, but there's no reason not to use them outside of it.

There's also AssocVector from Loki.

[synss]

Have you looked at flat_map from Boost's interprocess library? They're in the interprocess library, but there's no reason not to use them outside of it.

There's also AssocVector from Loki.

I could not find these two when I was looking for something like it. Loki's looks very much like what I have done, so I can compare with mine and maybe find my bug --- if I don't, I'll just try using their implementation.

Thank you!

[iMalc]

I've had a bit of a look at associative_vector.h and AssocVector.h from Loki

First, some of the bugs with associate_vector.h
There seemed to be some functions in associative_vector.h that would not compile. For example the insert that takes two iterators calls insert on the vector without passing the _Where iterator.
const_reference was incorrectly defined. It should be: const mapped_type& not const reference.

Some forms of the constructor are missing such as the explicit one taking a predicate.

const versions of rbegin and rend were missing. Being someone who actually uses those, I noticed.

The version of insert that takes an iterator hint wasn't taking advantage of the hint. the Loki one was doing this.

There were some comparison operators missing, the two that are present would be better declared as friends as done in the Loki version.

The Loki implementation of the two iterator version of insert was rather unimpresive though - O(n*n) for inserting n items! I would insert the new items onto the end of the vector, then sort only these newly added items only, and then use inplace_merge to merge the current items and the new items. Then it's O(n*log(n)) instead. This would also usually be somewhat faster than simply inserting the new items and sorting the entire vector.

[CornedBee]

By all means, send those bug reports to the Boost issue tracker:
http://svn.boost.org/trac/boost/newticket

And to the Loki bug tracker:
http://sourceforge.net/tracker/?grou...57&atid=396644

[iMalc]

Sorry, when I referred to "associative_vector.h" I meant the one posted by synss above. I'll check out the boost one also though.

[synss]

Sorry, when I referred to "associative_vector.h" I meant the one posted by synss above. I'll check out the boost one also though.

Thank you for taking a look, I noticed these bugs while comparing with Loki's implementation. Loki's fails in the same way in my program, though. I guess sorted vectors just cannot be used without bigger changes I am not going to do so I'll just give the unsorted containers a try a leave it.

[synss]

I am back! (sorry) I tried to make a release build and run it to defeat the checked iterators and see the results,
1. clearly, the order is not correct in the associative vector (either mine or Loki's, they give similar results), std::map works as expected
2. profiling shows a huge difference between using a std::map and an sorted vector...

My program is for running scientific calculations, so I am annoyed with the performance issue...

I use a custom key like so:

inline bool 
Link::Energy_Lookup_Key::operator<(const Link::Energy_Lookup_Key& rhs) const
{ 
	return origin_species_ < rhs.origin_species_
	|| site_name_ < rhs.site_name_ 
	|| neighbor_species_ < rhs.neighbor_species_; 
}

where I simply compare all of the data members using operator< could the problem be here? due to C++ shortcutting the || for example? Or I should better use &&? I am now thinking this could be the problem.


As a side note, if anyone is interested I just found a Dr. Dobb's article about "Maps with Extensive Keys" this is relevant to my problem so I give the link: http://www.ddj.com/cpp/184402065



EDIT: I'll answer my own question, yes operator|| was not correct, operator&& in the key gives correct results.

inline bool 
Link::Energy_Lookup_Key::operator<(const Link::Energy_Lookup_Key& rhs) const
{ 
	return origin_species_ < rhs.origin_species_
	&& site_name_ < rhs.site_name_ 
	&& neighbor_species_ < rhs.neighbor_species_; 
}

[iMalc]

Well that post shows exactly what the problem is, neither the first nor the later < operator you posted is valid. This explains why you've been having the problems you were having all along!

Here's how your < operator could be written correctly:

bool 
Link::Energy_Lookup_Key::operator<(const Link::Energy_Lookup_Key& rhs) const
{ 
	return origin_species_ < rhs.origin_species_
	|| !(rhs.origin_species_ < origin_species_) && (site_name_ < rhs.site_name_ 
	|| !(rhs.site_name < site_name_) && neighbor_species_ < rhs.neighbor_species_); 
}

The < operator for std::pair shows how to do it if you want to read your compiler's standard library implementation.

[synss]

Well that post shows exactly what the problem is, neither the first nor the later < operator you posted is valid. This explains why you've been having the problems you were having all along!

Here's how your < operator could be written correctly:

bool 
Link::Energy_Lookup_Key::operator<(const Link::Energy_Lookup_Key& rhs) const
{ 
	return origin_species_ < rhs.origin_species_
	|| !(rhs.origin_species_ < origin_species_) && (site_name_ < rhs.site_name_ 
	|| !(rhs.site_name < site_name_) && neighbor_species_ < rhs.neighbor_species_); 
}

The < operator for std::pair shows how to do it if you want to read your compiler's standard library implementation.

I would never have thought about it, although now that I see it, it makes sense. Thank you very much!

[synss]

I think you have missed parenthesis, I think (hope) it is

bool 
Link::Energy_Lookup_Key::operator<(const Link::Energy_Lookup_Key& rhs) const
{ 
	return origin_species_ < rhs.origin_species_
	|| (!(rhs.origin_species_ < origin_species_) && (site_name_ < rhs.site_name_ 
	|| (!(rhs.site_name < site_name_) && neighbor_species_ < rhs.neighbor_species_))); 
}

[synss]

Whatever... I'll use a boost::tuple to hold my key and let the boost people figure out the correct boolean arithmetic.

Thank all for your help!

[iMalc]

It should have been okay as I posted it. And has higher precedence than Or. Not also has higher precedence than And.

boost::tuple is certainly a good idea if you're happy to go with that.

I take it this means that the associative vectors now work fine for you?