1197. Can unordered containers have bucket_count() == 0?

Section: 23.2.8 [unord.req] Status: C++11 Submitter: Howard Hinnant Opened: 2009-08-24 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++11 status.

Discussion:

Table 97 "Unordered associative container requirements" in 23.2.8 [unord.req] says:

Table 97 — Unordered associative container requirements (in addition to container)

Expression	Return type	Assertion/note pre-/post-condition	Complexity
b.bucket(k)	size_type	Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed. Post: the return value shall be in the range [0, b.bucket_count()).	Constant

What should b.bucket(k) return if b.bucket_count() == 0?

I believe allowing b.bucket_count() == 0 is important. It is a very reasonable post-condition of the default constructor, or of a moved-from container.

I can think of several reasonable results from b.bucket(k) when b.bucket_count() == 0:

1. Return 0.
2. Return numeric_limits<size_type>::max().
3. Throw a domain_error.
4. Requires: b.bucket_count() != 0.

[ 2009-08-26 Daniel adds: ]

A forth choice would be to add the pre-condition "b.bucket_count() != 0" and thus imply undefined behavior if this is violated.

[ Howard: I like this option too, added to the list. ]

Further on here my own favorite solution (rationale see below):

Suggested resolution:

[Rationale: I suggest to follow choice (1). The main reason is that all associative container functions which take a key argument, are basically free of pre-conditions and non-disrupting, therefore excluding choices (3) and (4). Option (2) seems a bit unexpected to me. It would be more natural, if several similar functions would exist which would also justify the existence of a symbolic constant like npos for this situation. The value 0 is both simple and consistent, it has exactly the same role as a past-the-end iterator value. A typical use-case is:

size_type pos = m.bucket(key);
if (pos != m.bucket_count()) {
 ...
} else {
 ...
}

— end Rationale]

- Change Table 97 in 23.2.8 [unord.req] as follows (Row b.bucket(k), Column "Assertion/..."):

Table 97 — Unordered associative container requirements (in addition to container)

Expression	Return type	Assertion/note pre-/post-condition	Complexity
b.bucket(k)	size_type	Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed. Post: if b.bucket_count() != 0, the return value shall be in the range [0, b.bucket_count()), otherwise 0.	Constant

[ 2010-01-25 Choice 4 put into proposed resolution section. ]

[ 2010-01-31 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

Proposed resolution:

Change Table 97 in 23.2.8 [unord.req] as follows (Row b.bucket(k), Column "Assertion/..."):

Table 97 — Unordered associative container requirements (in addition to container)

Expression	Return type	Assertion/note pre-/post-condition	Complexity
b.bucket(k)	size_type	Pre: b.bucket_count() > 0 Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed. Post: the return value shall be in the range [0, b.bucket_count()).	Constant