Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++11 status.

539.partial_sum andadjacent_difference should mention requirements

Section: 26.10.7[partial.sum]Status:C++11Submitter: Marc SchooldermanOpened: 2006-02-06Last modified: 2016-01-28

Priority:Not Prioritized

View all issues withC++11 status.

Discussion:

There are some problems in the definition ofpartial_sum andadjacent_difference in 26.4 [lib.numeric.ops]

Unlikeaccumulate andinner_product, these functions are notparametrized on a "type T", instead, 26.4.3 [lib.partial.sum] simplyspecifies the effects clause as;

Assigns to every element referred to by iteratori in the range[result,result + (last - first)) a value correspondingly equal to

((...(* first + *( first + 1)) + ...) + *( first + ( i - result )))

And similarly for BinaryOperation. Using just this definition, it seemslogical to expect that:

char i_array[4] = { 100, 100, 100, 100 };int  o_array[4];std::partial_sum(i_array, i_array+4, o_array);

Is equivalent to

int o_array[4] = { 100, 100+100, 100+100+100, 100+100+100+100 };

i.e. 100, 200, 300, 400, with addition happening in theresult type,int.

Yet all implementations I have tested produce 100, -56, 44, -112,because they are using an accumulator of theInputIterator'svalue_type, which in this case ischar, notint.

The issue becomes more noticeable when the result of the expression*i +*(i+1) orbinary_op(*i, *i-1) can't be converted to thevalue_type. In a contrived example:

enum not_int { x = 1, y = 2 };...not_int e_array[4] = { x, x, y, y };std::partial_sum(e_array, e_array+4, o_array);

Is it the intent that the operations happen in theinput type, or intheresult type?

If the intent is that operations happen in theresult type, somethinglike this should be added to the "Requires" clause of 26.4.3/4[lib.partial.sum]:

The type of*i + *(i+1) orbinary_op(*i, *(i+1)) shall meet therequirements ofCopyConstructible (20.1.3) andAssignable(23.1) types.

(As also required forT in 26.4.1 [lib.accumulate] and 26.4.2[lib.inner.product].)

The "auto initializer" feature proposed inN1894is not required toimplementpartial_sum this way. The 'narrowing' behaviour can still beobtained by using thestd::plus<> function object.

If the intent is that operations happen in theinput type, thensomething like this should be added instead;

The type of *first shall meet the requirements ofCopyConstructible (20.1.3) andAssignable (23.1) types.The result of*i + *(i+1) orbinary_op(*i, *(i+1)) shall beconvertible to this type.

The 'widening' behaviour can then be obtained by writing a custom proxyiterator, which is somewhat involved.

In both cases, the semantics should probably be clarified.

26.4.4 [lib.adjacent.difference] is similarly underspecified, althoughall implementations seem to perform operations in the 'result' type:

unsigned char i_array[4] = { 4, 3, 2, 1 };int o_array[4];std::adjacent_difference(i_array, i_array+4, o_array);

o_array is 4, -1, -1, -1 as expected, not 4, 255, 255, 255.

In any case,adjacent_difference doesn't mention the requirements on thevalue_type; it can be brought in line with the rest of 26.4[lib.numeric.ops] by adding the following to 26.4.4/2[lib.adjacent.difference]:

The type of*first shall meet the requirements ofCopyConstructible (20.1.3) andAssignable (23.1) types."

[Berlin: Giving output iterator's value_types very controversial. Suggestion ofadding signatures to allow user to specify "accumulator".]

[Bellevue:]

The intent of the algorithms is to perform their calculations using the type of the input iterator.Proposed wording provided.

[Sophia Antipolis:]

We did not agree that the proposed resolution was correct. For example,when the arguments are types(float*, float*, double*), thehighest-quality solution would use double as the type of theaccumulator. If the intent of the wording is to require that the type ofthe accumulator must be theinput_iterator'svalue_type, the wordingshould specify it.

[2009-05-09 Alisdair adds:]

Now that we have the facility, the 'best' accumulator type could probably bededuced as:

std::common_type<InIter::value_type, OutIter::reference>::type

This type would then have additional requirements of constructability andincrementability/assignability.

If this extracting an accumulator type from a pair/set of iterators (withadditional requirements on that type) is a problem for multiple functions,it might be worth extracting into a SharedAccumulator concept or similar.

I'll go no further in writing up wording now, until the group gives aclearer indication of preferred direction.

[2009-07 Frankfurt]

The proposed resolution isn't quite right. For example, "the type of*first" should be changed to "iterator::value_type" or similar. Danielvolunteered to correct the wording.

[2009-07-29 Daniel corrected wording.]

[2009-10 Santa Cruz:]

Move to Ready.

Proposed resolution:

1. Change 26.10.7[partial.sum]/1 as indicated:

   Effects:LetVT beInputIterator's value type. For a nonempty range,initializes an accumulatoracc of typeVT with*first and performs*result = acc. For every iteratori in[first + 1, last) in order,acc is thenmodified byacc = acc + *i oracc = binary_op(acc, *i) and is assignedto*(result + (i - first)).Assigns to every element referred to byiteratori in the range[result,result + (last - first)) a valuecorrespondinglyequal to

   ((...(*first + *(first + 1)) + ...) + *(first + (i - result)))

   or

   binary_op(binary_op(...,   binary_op(*first, *(first + 1)),...), *(first + (i - result)))

2. Change 26.10.7[partial.sum]/3 as indicated:

   Complexity: Exactlymax((last - first) - 1, 0)applicationsofbinary_opthe binary operation.

3. Change 26.10.7[partial.sum]/4 as indicated:

   Requires:VT shall be constructible from the type of*first, the result ofacc + *i orbinary_op(acc, *i) shall be implicitly convertible toVT, andthe result of the expressionacc shall be writable to theresultoutput iterator. In the ranges[first,last] and[result,result + (last - first)] [..]

4. Change 26.10.12[adjacent.difference]/1 as indicated:

   Effects:LetVT beInputIterator's value type. For a nonempty range,initializes an accumulatoracc of typeVT with*first and performs*result = acc. For every iteratori in[first + 1, last) in order,initializes avalueval of typeVT with*i, assigns the result ofval - acc orbinary_op(val, acc)to*(result + (i - first)) and modifiesacc = std::move(val).Assigns to every element referred to by iteratori in the range[result + 1,result + (last - first)) a value correspondingly equal to

   *(first + (i - result)) - *(first + (i - result) - 1)

   or

   binary_op(*(first + (i - result)), *(first + (i - result) - 1)).

   result gets the value of *first.

5. Change 26.10.12[adjacent.difference]/2 as indicated:

   Requires:VT shall beMoveAssignable ([moveassignable])and shall beconstructible from the type of*first. The resultof the expressionacc and the result of the expressionval - acc orbinary_op(val, acc)shall be writable to theresult output iterator. In the ranges[first,last] [..]

6. Change 26.10.12[adjacent.difference]/5 as indicated:

   Complexity: Exactlymax((last - first) - 1, 0)applicationsofbinary_opthe binary operation.