[C++] Explaining std::set<>::insert with hints...

Discussion in 'OT Technology' started by GunboatDiplomat, Jun 17, 2006.

  1. GunboatDiplomat

    GunboatDiplomat New Member

    Joined:
    Jun 9, 2006
    Messages:
    214
    Likes Received:
    0
    There is a method, insert(), defined for std::set that takes a std::set::iterator as a hint to where to insert a value, as well as the value, itself. My question is two-fold:

    First, what if my hint is not particularly good? Will it still be able to properly insert the value? With what efficiency will it do this?

    Secondly, very peculiarly, this version of std::set::insert, unlike it's ordinary counter-part, doesn't return a std::pair<>. Instead, it returns a single iterator to where the element was inserted. Why is that? What does that mean? Inserting can't fail? How am I supposed to know whether the value was inserted or if the value already existed? Why does the standard believe that I wouldn't want to know this?

    If you can answer these questions (particularly the latter one), I'll be very impressed!
    Thank you...
     
  2. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    Open your textbook and read it.
     
  3. P07r0457

    P07r0457 New Member

    Joined:
    Sep 20, 2004
    Messages:
    28,491
    Likes Received:
    0
    Location:
    Southern Oregon
    I'm not particularly familiar with that, but I'll take a look.

    Code:
    00351       /**
    00352        *  @brief A template function that attemps to insert a range of elements.
    00353        *  @param  first  Iterator pointing to the start of the range to be
    00354        *                 inserted.
    00355        *  @param  last  Iterator pointing to the end of the range.
    00356        *
    00357        *  Complexity similar to that of the range constructor.
    00358        */
    00359       template<class _InputIterator>
    00360       void
    00361       insert(_InputIterator __first, _InputIterator __last)
    00362       { _M_t.insert_unique(__first, __last); }
    From what I gather, it's a void function, and does not return anything at all.
     
  4. GunboatDiplomat

    GunboatDiplomat New Member

    Joined:
    Jun 9, 2006
    Messages:
    214
    Likes Received:
    0
    Well, that's funny. Are you sure you're not looking at std::map<>?
     
  5. P07r0457

    P07r0457 New Member

    Joined:
    Sep 20, 2004
    Messages:
    28,491
    Likes Received:
    0
    Location:
    Southern Oregon
    nope, I pulled that from the GNU GCC documentation for "class std::set< _Key, _Compare, _Alloc >"

    however, I just checked some doc I have from SGI compilers, and it mentions that it's not supported by all compilers, yet... What are you using? It appears behavior may be different.
     
  6. GunboatDiplomat

    GunboatDiplomat New Member

    Joined:
    Jun 9, 2006
    Messages:
    214
    Likes Received:
    0
    "Textbook?" Are you still in school?

    I've checked the MSDN, the documentation that came with my compiler, and it fails to answer my questions. It just so happens that I also have a copy of Stroustrup's book and it doesn't say anything about the particulars of std::set<>::insert() either. Hence, my post on this forum...

    Honestly, I can't figure out your recalcitrant attitude. If you weren't going to help, why would you even bother posting at all?
     
  7. GunboatDiplomat

    GunboatDiplomat New Member

    Joined:
    Jun 9, 2006
    Messages:
    214
    Likes Received:
    0
    Oh, I see the confusion. There are three overrides to std::set<>::insert() and I'm talking about the one that takes only one iterator and that iterator is a hint as to where the new element goes. I suspect it's for building a set from elements that are already sorted, so that the set can be built in amortized constant time, O(k), rather than log time, O(log).

    I'm using Microsoft's C++ compiler that came with MS Visual Studio 2005...
     
  8. P07r0457

    P07r0457 New Member

    Joined:
    Sep 20, 2004
    Messages:
    28,491
    Likes Received:
    0
    Location:
    Southern Oregon
    This is what I show as listings in my GNU GCC doc, none of which matches your description:

    Code:
    set()
    set(const _Compare &__comp, const allocator_type &__a=allocator_type())
    set(_InputIterator __first, _InputIterator __last)
    set(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
    set(const set< _Key, _Compare, _Alloc > &__x)
    Let me see if I have anything more specific to the MS compiler...
     
  9. GunboatDiplomat

    GunboatDiplomat New Member

    Joined:
    Jun 9, 2006
    Messages:
    214
    Likes Received:
    0
    Thanks for your help!

    May I kindly point out that your quoted code looks like docs for the constructor of std::set<>?
     
  10. P07r0457

    P07r0457 New Member

    Joined:
    Sep 20, 2004
    Messages:
    28,491
    Likes Received:
    0
    Location:
    Southern Oregon
    Well I found one that meets your recent explination, but not your first:
    Code:
    00303       // insert/erase
    00304       /**
    00305        *  @brief Attempts to insert an element into the %set.
    00306        *  @param  x  Element to be inserted.
    00307        *  @return  A pair, of which the first element is an iterator that points
    00308        *           to the possibly inserted element, and the second is a bool
    00309        *           that is true if the element was actually inserted.
    00310        *
    00311        *  This function attempts to insert an element into the %set.  A %set
    00312        *  relies on unique keys and thus an element is only inserted if it is
    00313        *  not already present in the %set.
    00314        *
    00315        *  Insertion requires logarithmic time.
    00316        */
    00317       std::pair<iterator,bool>
    00318       insert(const value_type& __x)
    00319       {
    00320     std::pair<typename _Rep_type::iterator, bool> __p =
    00321       _M_t.insert_unique(__x);
    00322     return std::pair<iterator, bool>(__p.first, __p.second);
    00323       }
    according to that doc, it would return pair, of which a boolean states whether it was inserted or not.

    so is that also not what you need? (I see std::pair, not std::set)
     
  11. GunboatDiplomat

    GunboatDiplomat New Member

    Joined:
    Jun 9, 2006
    Messages:
    214
    Likes Received:
    0
    It looks like you simply found the simplest std::set<>::insert() override method, which takes the std::set::value_type as a parameter. That does return a pair, which is expected.

    Also, I'm not sure what you mean by "meets your recent explanation, but not your first." I have more than one explanation? ...and they don't match?

    What I'm looking for is an explanation for this function:
    Code:
    iterator insert(iterator _Where,
        const value_type& _Val)
        {    // try to insert node with value _Val using _Where as a hint
        // implementation removed for brevity...
        }
    ...which comes straight out of the Microsoft header file, completely unaltered, except for the removal of the implementation, of course!

    Notice how it only returns an iterator and takes only one iterator as a parameter. This is the method call I would like explained to me. For a complete list of interesting questions regarding this method, please refer back to my original post...

    Thank you...
     
  12. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    It's nothing personal. We get college kids submitting questions like this from time to time, and we have to remind them that we're not here to help them cheat or steal. That's all. Reprimand withdrawn.
     
  13. samm

    samm Next in Line

    Joined:
    Dec 22, 2000
    Messages:
    2,630
    Likes Received:
    0
    Location:
    San Jose, CA
    Inserting operations for sets multisets will either succeed, or leave the container as-is since their underlying structure is typically a node-based container. Therefore, if you try to insert a value that already exists, it will fail, regardless if you provide a poor hint of its potential position in the container. If you try to insert a value that does not exist, AND provide a poor position hint, my guess is the inserting operating will have logarithmic complexity rather than a constant complexity. However, it will be highly dependent on your compiler vendor's STL.

    If you try to use the two-argument insert method, it should return an iterator as you mentioned. If the value you are attempting to insert already exists in the set, its position is returned. Otherwise, the inserted element's position is returned. What would be the advantage of knowing whether or not this value was inserted? In either case (value is already in the container, or it isn't) the two-argument insert method will return an iterator to an element with that value.
     
  14. GunboatDiplomat

    GunboatDiplomat New Member

    Joined:
    Jun 9, 2006
    Messages:
    214
    Likes Received:
    0
    First off, when replying to code, you might want to consider turning off smilies. Otherwise, you'll have some unexpected happy faces in your post...

    I'm only guessing that the hint is used to insert with constant complexity. Inserting is usually done with logarithmic complexity. Are you suggesting that passing a bad hint won't harm your insertion time?

    By this very logic, we should ask why the standard insert method returns a pair. It seemed pertinent for that insert so why not the other? What makes it so different? That was my question and this doesn't address that, whatsoever.

    The fact of the matter is that the ordering criteria is farily indepenedant of the actual state of the class. For instance, consider this code:
    Code:
    struct Anomaly {
        int rank;
        int id;
    
        Anomaly(int r, int i) : rank(r), id(i) {}
        bool operator < (Anomaly const & right) const { return rank < right.rank; }
    };
    
    std::set<Anomaly> anomalousSet;
    anomalousSet.insert(Anomaly(2, 2));
    anamalousSet.insert(Anomaly(2, 3));  // this insert will fail even though the objects are distinguishable...
    Thus, it's useful to know if the insertion actually happened. Again, one insert method does this, so why doesn't the other? What's the purpose of this inconsistency?
     
  15. samm

    samm Next in Line

    Joined:
    Dec 22, 2000
    Messages:
    2,630
    Likes Received:
    0
    Location:
    San Jose, CA
    I am suggesting the insertion time is at worst, logarithmic.

    see my comment below

    Yes, it is certainly possible to have insertions fail when the inserted element does not already exist in the set. In those cases, I see two possible actions you could take:

    1. If you must use the two argument insert method, maybe try to compare the value of the iterator result with the element you just inserted to see if it was actually inserted.

    2. Use the single argument insert method

    If you are supplying a positional hint I am assuming you have a reasonable idea of where the to-be inserted element should reside in the container. If that is the case, the standardization committee probably make the decision to omit the return value indicating if the insertion succeeded or not.
     
  16. kingtoad

    kingtoad OT Supporter

    Joined:
    Sep 2, 2003
    Messages:
    55,924
    Likes Received:
    11
    Location:
    Los Angeles
    I think you're cool, I remember you particuarly from OT, but the more and more you post here the more I feel I'm becoming annoyed by you.
     
  17. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    :run: :noes:

    :squint:
     

Share This Page