Joaqu=EDn M L=F3pez Mu=F1oz wrote:
> I'm reading the TR1 proposal of hashed containers as
> described in
>=20
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
>=20
> (are there corrections to this text?) and I've found
> two issues I have doubts about:
>=20

The original proposals for library extensions are of historical interest=20
only. Instead, look at=20
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1687.pdf.

--=20

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <1106320948.423755.296740@c13g2000cwb.googlegroups.com>,
 "Joaqu   n M L   pez Mu   oz" <joaquin@tid.es> wrote:

> I'm reading the TR1 proposal of hashed containers as
> described in
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
>
> (are there corrections to this text?) and I've found
> two issues I have doubts about:
>
> 1. count() is required to perform in O(1) in average.
> Shouldn't this be O(count(k)), taking into account that
> some unordered associative containers support equivalent
> keys?

Agreed, although the standardeze to say this escapes me at the moment.

> 2. The load factor is defined in the requirements table
> as size()/bucket_count(). Later on, on the notes for
> max_load_factor, it is stated that the container
> automatically keeps the load factor under max_load_factor()
> by increasing the number of buckets. Now, consider:
>
> std::tr1::unordered_multiset<int> ums;
> for(;;)
> {
> ums.insert(0);
> }
>
> As ums grows, the requirement table seems to indicate
> that the number of buckets must also be made to grow
> to keep the load factor bounded. Yet, all elements
> of ums will be held in the same bucket no matter how many
> other buckets there are!! Unless I'm missing something,
> seems to me that this cannot be the intention of the
> proposal. Shouldn't the load factor be defined then
> as the average number of *unique* elements per bucket?

Is there a way to implement this that isn't extravagant in cost?  The
whole motivation for the unordered containers is to serve as an
optimization with respect to the tree-based containers.  If we
standardize away the ability of the unordered containers to be
significantly (and only potentially) smaller and faster than their
tree-based cousins, then they have no reason for existing.

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Pete Becker wrote:
> Joaqu   n M L   pez Mu   oz wrote:
> > I'm reading the TR1 proposal of hashed containers as
> > described in
> >
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
> >
> > (are there corrections to this text?) and I've found
> > two issues I have doubts about:
> >
>
> The original proposals for library extensions are of historical
interest
> only. Instead, look at
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1687.pdf.
>

Thanks for the pointer. Anyway, seems like the two issues
I'm talking about remain the same in the TR1 official doc.
--
Joaqu   n M L   pez Mu   oz
Telef   nica, Investigaci   n y Desarrollo


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

I'm reading the TR1 proposal of hashed containers as
described in

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html

(are there corrections to this text?) and I've found
two issues I have doubts about:

1. count() is required to perform in O(1) in average.
Shouldn't this be O(count(k)), taking into account that
some unordered associative containers support equivalent
keys?

2. The load factor is defined in the requirements table
as size()/bucket_count(). Later on, on the notes for
max_load_factor, it is stated that the container
automatically keeps the load factor under max_load_factor()
by increasing the number of buckets. Now, consider:

std::tr1::unordered_multiset<int> ums;
for(;;)
{
ums.insert(0);
}

As ums grows, the requirement table seems to indicate
that the number of buckets must also be made to grow
to keep the load factor bounded. Yet, all elements
of ums will be held in the same bucket no matter how many
other buckets there are!! Unless I'm missing something,
seems to me that this cannot be the intention of the
proposal. Shouldn't the load factor be defined then
as the average number of *unique* elements per bucket?

Thank you,
--
Joaqu   n M L   pez Mu   oz
Telef   nica, Investigaci   n y Desarrollo


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]