Thread: map: lower_bound, upper_bound, and insert

  1. #1
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401

    map: lower_bound, upper_bound, and insert

    I'm trying to figure out the most efficient way to use map.insert with the iterator parameter. I'm not certain if the iterator should be immediately before the new element or immediately after the new element.

    insert - C++ Reference suggests "if [the iterator is] set to the element that precedes the actual location where the element is inserted, [it] makes for a very efficient insertion operation."
    map<Key, Data, Compare, Alloc> simply says that the iterator is provided as a hint with no indication of which way would be better.
    The first answer provided at std::map insert or std::map find? - Stack Overflow seems to suggest that lower_bound is returning the correct iterator to be used as the parameter to insert. However, lower_bound never returns an iterator to a location that would be before the new element; it's always the same location or after.

    [tangentially-related rant]
    IMO, lower_bound is a terrible name for what it does. upper_bound makes sense; the returned iterator is the first element with a key > the provided key. lower_bound returns almost exactly the same thing, except the keys could be equivalent. Suppose you've got a set of numbers { 1, 4, 8, 12 } and you ask for the lower_bound of 7. Isn't 4 the answer that most of us would expect? I mean, the upper_bound of 7 is 8. Who would expect that the lower_bound == upper_bound for an element that doesn't exist in the collection?! Blah.
    [/rant]

    Is there a standard correct position for the iterator, or is this implementation-dependent?
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,401
    I am still not sure of the real answer to this, but I recall doing some empirical testing on specific implementations as mentioned in this CodeGuru thread: efficient map(/set) insertion.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Thanks laserlight. That answered my question.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by pianorain View Post
    [tangentially-related rant]
    IMO, lower_bound is a terrible name for what it does. upper_bound makes sense; the returned iterator is the first element with a key > the provided key. lower_bound returns almost exactly the same thing, except the keys could be equivalent. Suppose you've got a set of numbers { 1, 4, 8, 12 } and you ask for the lower_bound of 7. Isn't 4 the answer that most of us would expect? I mean, the upper_bound of 7 is 8. Who would expect that the lower_bound == upper_bound for an element that doesn't exist in the collection?! Blah.
    [/rant]
    I agree that they are not the best names in the world, but all you need to remember is that if you insert an element at the position indicated by lower or upper bound, you don't break the ordering.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    lower_bound is the lower bound of equal_range, upper_bound is the upper bound. Therefore, when the element is not present, lower_bound must equal upper_bound so that the equal_range is empty.
    By the way, C++0x clarifies the insertion hint. For a value t and an iterator p, c.insert(p, t) has the following complexity:
    (N3092 Table 99)
    "logarithmic in general, but amortized constant if t is inserted right before p."
    Last edited by CornedBee; 06-11-2010 at 02:28 AM.
    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

Popular pages Recent additions subscribe to a feed

Tags for this Thread