Title
Can unordered containers have bucket_count() == 0?
Status
c++11
Section
[unord.req]
Submitter
Howard Hinnant

Created on 2009-08-24.00:00:00 last changed 162 months ago

Messages

Date: 2010-10-21.18:28:33

Proposed resolution:

Change Table 97 in [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
Date: 2010-01-31.00:00:00

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

Date: 2010-01-25.00:00:00

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

Date: 2009-08-26.00:00:00

[ 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 [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
Date: 2009-08-24.00:00:00

Table 97 "Unordered associative container requirements" in [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.
History
Date User Action Args
2011-08-23 20:07:26adminsetstatus: wp -> c++11
2010-10-21 18:28:33adminsetmessages: + msg1110
2010-10-21 18:28:33adminsetmessages: + msg1109
2010-10-21 18:28:33adminsetmessages: + msg1108
2010-10-21 18:28:33adminsetmessages: + msg1107
2009-08-24 00:00:00admincreate