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

This is a discussion on elements in iterator range [__first, __last) are not partitioned within the C++ Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13

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

    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
    Code:
    /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?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Quote Originally Posted by synss View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    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.
    Attached Files Attached Files

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    Quote Originally Posted by CornedBee View Post
    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!

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    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.
    Last edited by iMalc; 07-11-2008 at 09:35 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    Quote Originally Posted by iMalc View Post
    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.

  10. #10
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    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:
    Code:
    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.
    Code:
    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_; 
    }
    Last edited by synss; 07-23-2008 at 12:02 AM.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    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:
    Code:
    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.
    Last edited by iMalc; 07-23-2008 at 02:11 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    Quote Originally Posted by iMalc View Post
    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:
    Code:
    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!

  13. #13
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    I think you have missed parenthesis, I think (hope) it is
    Code:
    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_))); 
    }

  14. #14
    Registered User
    Join Date
    Jun 2008
    Location
    Tokyo, Japan
    Posts
    13
    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!

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. using realloc for a dynamically growing array
    By broli86 in forum C Programming
    Replies: 10
    Last Post: 06-27-2008, 05:37 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21