[jira] Commented: (STDCXX-216) std::map::insert (iterator, pair) doesn't use hint properly

["Travis Vitek (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/STDCXX-216?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12563886#action_12563886 ] 

Travis Vitek commented on STDCXX-216:
-------------------------------------

Testcase to compare each insert overload...


{noformat}
#include <map>
#include <vector>

#include <stdlib.h> // for strtoul

typedef unsigned K;
typedef unsigned V;

typedef std::map <K, V> map_type;
typedef std::pair<K, V> value_type;
typedef std::vector<value_type> vector_type;

void test_fill_map_1 (map_type& m, const vector_type& v)
{
    vector_type::const_iterator b = v.begin ();
    vector_type::const_iterator e = v.end   ();

    map_type::iterator p = m.begin ();
    for (/**/; b != e; ++b) {
        p = m.insert (p, *b);
    }
}

void test_fill_map_2 (map_type& m, const vector_type& v)
{
    vector_type::const_iterator b = v.begin ();
    vector_type::const_iterator e = v.end   ();
    for (/**/; b != e; ++b) {
        m.insert (*b);
    }
}

void test_fill_map_3 (map_type& m, const vector_type& v)
{
    m.insert (v.begin (), v.end ());
}

typedef void (*fill_fn_type)(map_type&, const vector_type& v);

int main (int argc, char* argv[])
{
    size_t fn = 0;
    if (1 < argc)
        fn = strtoul (argv [1], 0, 0);

    if (2 < fn)
        return 1;

    size_t nloops = 100;
    if (2 < argc)
        nloops = strtoul (argv[2], 0, 0);

    const fill_fn_type fillers[] = {
        test_fill_map_1,
        test_fill_map_2,
        test_fill_map_3
    };

    vector_type v;
    v.reserve (5000);

    for (unsigned nn = 0; nn < v.capacity (); ++nn) {
        v.push_back (value_type(nn, nn));
    }

    std::map<K,V> m;
    for (unsigned nn = 0; nn < nloops; ++nn) {
        m.clear ();
        fillers [fn] (m, v);
    }

    return 0;
}
{noformat}

Before fix...

{noformat}
$ time ./u 0 1000

real    0m1.122s
user    0m1.086s
sys     0m0.000s
$ time ./u 1 1000

real    0m1.071s
user    0m1.028s
sys     0m0.002s
$ time ./u 2 1000

real    0m1.076s
user    0m1.032s
sys     0m0.002s
{noformat}

After the fix...

{noformat}
$ time ./u 0 1000

real    0m0.323s
user    0m0.311s
sys     0m0.000s
$ time ./u 1 1000

real    0m1.072s
user    0m1.025s
sys     0m0.003s
$ time ./u 2 1000

real    0m1.072s
user    0m1.030s
sys     0m0.004s
{noformat}


> std::map::insert (iterator, pair) doesn't use hint properly
> -----------------------------------------------------------
>
>                 Key: STDCXX-216
>                 URL: https://issues.apache.org/jira/browse/STDCXX-216
>             Project: C++ Standard Library
>          Issue Type: Bug
>          Components: 23. Containers
>    Affects Versions: 4.1.2, 4.1.3, 4.1.4
>         Environment: all
>            Reporter: Martin Sebor
>            Assignee: Travis Vitek
>             Fix For: 4.2.1
>
>   Original Estimate: 8h
>  Remaining Estimate: 8h
>
> Moved from the Rogue Wave bug tracking database:
> ****Created By: sebor @ Mar 23, 2004 04:17:39 PM****
> http://www.roguewave.com/developer/forum/OpenForumThread.cfm?forum=100&thread=542
> ----------------------------------------------------------------------
> Topic:Error in map::insert
> ----------------------------------------------------------------------
> map::insert( iterator, pair) does not work    (11/06/2003 02:13 AM)
> ----------------------------------------------------------------------
> I wanted to use the map::insert( iterator, pair) method to speed up things, but
> my tests
> showed that it was slower than the simple insert.
> Debugging showed that the test for usability of the position iterator always fails:
> iterator before = --position;
> if (_key_compare( before.first, (key) v) && _key_compare( (key) v,
> position.first)) ..
> Reason: 'before' and 'position' are equal, and (more simple term)
> a < b && b < a
> is always false.
> I guess it should read
> iterator before = position;
> --before;
> I found the same problem in STL library with CPP Builder 5 as well as on Sun
> Solaris 8,
> Sun Workshop 6 update 1 C++ 5.2 Patch 109508-09.
> Has anybody found this error too? Or, can anyone tell me in which version is it
> fixed?
> Another point is: Accoring to the manual the iterator should point to the last
> element smaller than the element to insert. If the code would be changed as
> suggested above, it would work if the iterator pointed to the next-greater
> element in the map ...
> To make it work as described, the code would have to be
> iterator after = position;
> ++after;
> if (_key_compare( position.first, (key) v) && _key_compare( (key) v,
> after.first)) ..
> But I did not check the following insert methode if a pointer to the element
> before or after the new one is required, so it may need even more code changes
> or a change of the description...
> Hth anybody else too, and maybe sbd can tell me in versions this problem is fixed?
> Thx in advance!
> René
> 										
> ----------------------------------------------------------------------
> Re: map::insert( iterator, pair) does not work    (11/17/2003 04:49 PM)
> ----------------------------------------------------------------------
> We are not aware of this problem. The use of the hint argument by insert() isn't clearly specified in the C++ standard (in fact, there is an open issue on it -- see
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#233). We'll look into it.
> Thanks
> Martin

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.