Pointers and iterators problems

[frek]

Hi all,
Please take a look at this program:

#include <iostream>
#include <vector>
#include <numeric>

double accum(double* beg, double* end, double init)
// compute the sum of [beg:end) starting with the initial value init
{
    return std::accumulate(beg, end, init);
}

int main()
{
    std::vector v{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };

    if (v.size() < 10000) // is it worth using concurrency?
        std::cout << accum(v.begin(), v.end(), 0.0) << '\n';

    return 0;
}

I get this error:
'double accum(double *,double *,double)': cannot convert argument 1 from 'std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>' to 'double *'

Apparently it's not possible to use iterators as pointers.
Is there any general rule when using pointers and iterators together? They aren't interchangeable presumably.

[JLBorges]

> Apparently it's not possible to use iterators as pointers.

But pointers are (can be used as) iterators; so write the function in terms of a polymorphic iterator.
template < typename ITERATOR, typename T > T accum( ITERATOR beg, ITERATOR end, T init_val ) ;

Or (C++20) write it in terms of an abstract input range:

#include <iostream>
#include <concepts>
#include <ranges>
#include <numeric>
#include <vector>
#include <list>

template < typename A, typename B > concept accumulatable =
    requires( A a, B b ) { { a += b } -> std::same_as<A&> ; } ;

template < std::ranges::input_range RANGE, typename T >
    requires accumulatable< T, std::ranges::range_value_t<RANGE> >
T accum( const RANGE& range, const T& init_val )
{
    return std::accumulate( std::ranges::begin(range), std::ranges::end(range), init_val ) ;
}

int main()
{
    int a[] { 0, 14, 82, 5, 14 } ;
    std::cout << accum( a, 1.5 ) << '\n' ; // 116.4

    std::vector b { 0, 14, 82, 5, 14 } ;
    std::cout << accum( b, 600L ) << '\n' ; // 715

    std::list<std::string> c { "abc", "defgh", "ijkl", "mnopqr", "stuvwxyz" } ;
    std::cout << accum( c, std::string( "letters: " ) ) << '\n' ; // letters: abcdefghijklmnopqrstuvwxyz
}

http://coliru.stacked-crooked.com/a/9dce494eecd8e568

[EL Jos]

Hi everyone,
Your problem is that the Mr. (compiler) tells you that there is a mismatch between the arguments you give to your accum function and the parameters of your accum function.

I explain: your function accum expects three parameters of which the first two are pointers to the double type (hence the double*) and in the third position a parameter of the simple double type; now look at the call of your function accum at line 16, you give as argument a modifiable iterator of the beginning (which has as type std: :vector<T>::iterator), another off-the-end modifiable iterator (which has as type std::vector<T>::iterator) and finally a constant (literal).

So from this you understand that instead of giving as argument to your accumulated function pointers to double, you give it a vector iterator and this creates an error.

We are aware of the origin of the problem and we have to propose one or more solutions;
To solve this problem we have two solutions:

1) THE SIMPLEST ONE
Change the type of the first two parameters of the function accum to be iterators of a vector.

Ex:
double accum(std::vector<double>::iterator it_begin, std::vector<double>::iterator it_end, double init);

2) THE MOST COMPLICATED
Create two pointers to double, one of which will point to the first element of your std::vector<double> and the other pointer will point to an element after the last element of your std::vector<double> and then we will pass them (the pointers) as the first two arguments when calling the accum function.
Ex:

int main()
{
    std::vector v{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };
    double* ptr_begin = &v[0];
    double* pter_end = &v[v.size()];
    
    if (v.size() < 10000) // is it worth using concurrency?
        std::cout << accum(ptr_begin, pter_end, 0.0) << '\n';

    return 0;
}

Note: And I advise you to write down your std::vector to avoid possible problems

[seeplus]

You can do 'tricks' with de-ref and pointer-of:

#include <iostream>
#include <vector>
#include <numeric>

double accum(const double* beg, const double* end, double init) {
    return std::accumulate(beg, end, init);
}

int main() {
    const std::vector v {1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7};

    std::cout << accum(&*v.cbegin(), &*v.cend(), 0.0) << '\n';
}

30.8

Or with C++20:

#include <iostream>
#include <vector>
#include <numeric>
#include <memory>

double accum(const double* beg, const double* end, double init) {
    return std::accumulate(beg, end, init);
}

int main() {
    const std::vector v {1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7};

    std::cout << accum(std::to_address(v.cbegin()), std::to_address(v.cend()), 0.0) << '\n';
}

[coder777]

Or alternatively you can use the data() member of std::vector:

#include <iostream>
#include <vector>
#include <numeric>

double accum(double* beg, double* end, double init)
// compute the sum of [beg:end) starting with the initial value init
{
    return std::accumulate(beg, end, init);
}

int main()
{
    std::vector<double> v{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };

    if (v.size() < 10000) // is it worth using concurrency?
        std::cout << accum(v.data(), v.data () + v.size(), 0.0) << '\n';

    return 0;
}

[frek]

Thank you all for introducing new features and offering alternative codes. My second question about the general rule on how to use iterators and pointers interchangeably still remains.
Let me clarify that. For instance we have got a right-hand variable and a left-hand one, either in both sides of an assignment operator or when sending arguments to parameters (of a function). I guess iterators are more general and they as left-hand variables are capable of being set by pointers (of the same type) as right-hand variables. But pointers can't be set using iterators, just like the code offered in the first post here, and therefore to work it out we need to pick an alternative like the ones you wrote. Is it right generally, please?

[jonnin]

Its a generalization that is required for things like linked lists. You can't take a pointer to the head of a linked list and expect that incrementing it will get you to head-> next, right? But an iterator does this -- the list iterator knows to hand you ->next instead of the next offset in memory. A pointer can never know that, you must do that logic yourself.

You cannot convert directly to and from pointers and iterators, even for a vector where they are more or less identical, so yes, you do need some sort of bridging code if you need to work with both pointers and iterators in sync.

[MikeyBoy]

I must admit, I'm slightly surprised that the call to std::accumulate() in the OP's code is fine. You certainly can't freely convert a pointer to an iterator - doing something like:

std::vector<int> v{ 1, 2, 3, 4, 5 };
std::vector<int>::iterator iter( &(v[0]) );

doesn't compile.

I assume there's some overload of std::accumulate() for raw pointers?

[keskiverto]

Where do you see iterators in:

template <class InputIterator, class T>
   T accumulate ( InputIterator first, InputIterator last, T init );

[frek]

If I've gotten what you wrote correctly you all mean that pointers must be used for pointers and iterators must be used for iterators generally. Have I figured it out appropriately?

By the way, the code I wrote is what Stroutrup wrote in his tour of C++ book!

[deleted account xyzzy]

https://www.sandordargo.com/blog/2022/03/16/iterators-vs-pointers

Scroll down and read the "How an iterator differs from a pointer" & "When to use one and when the other?"sections.

Well, read the entire page, the sections I highlight give "in a nutshell" view of iterators vs. pointers.

[frek]

@George: I read it, and thanks for providing me with that resource. They look as general rules, e.g., use pointers for pointer and iterators for iterators (only) but in real life applications we may need to use one for the other for some reason. They code posted at the beginning was one similar to one of Bjarne's books' algorithms so it's worth learning how to deal with such situations seemingly.

@jonnin

You cannot convert directly to and from pointers and iterators

Does it mean we cannot use pointers for iterators? I mean when an algorithm works based on iterators but we give it pointers.
It works: https://coliru.stacked-crooked.com/a/b67a813f067e3f19 @MikeyBoy
But iterators to pointer doesn't work.

[JLBorges]

> Does it mean we cannot use pointers for iterators?

A pointer to an element of an array is a random access iterator; it meets all requirements of LegacyContiguousIterator / concept std::contiguous_iterator
(it is a random access iterator referring to elements that are contiguous in memory).

#include <iostream>
#include <iterator>
#include <typeinfo>
#include <vector>
#include <deque>
#include <list>

template < std::forward_iterator ITER > void dump_iter_category( ITER )
{
    std::cout << typeid(ITER).name() << " - "
              << typeid( typename std::iterator_traits<ITER>::iterator_category ).name() ;
    std::cout << ( std::contiguous_iterator<ITER> ? "  (contiguous)\n" : "\n" ) ;
}

#define DUMP_ITER_CATEGORY(x) ( ( std::cout << #x << " - " ), dump_iter_category(x) )

int main()
{
    const int c_array[100] {} ;
    DUMP_ITER_CATEGORY(c_array+5) ; // contiguous_iterator

    std::vector<int> vec ;
    DUMP_ITER_CATEGORY( vec.begin() ) ; // contiguous_iterator

    std::deque<const char*> deq ;
    DUMP_ITER_CATEGORY( deq.begin() ) ; // random access, but not contiguous

    std::list<double> lst ;
    DUMP_ITER_CATEGORY( lst.end() ) ; // bidirectional_iterator
}

http://coliru.stacked-crooked.com/a/4c6989f45018ac6e

[seeplus]

template <class InputIterator, class T>
   T accumulate ( InputIterator first, InputIterator last, T init );

Despite the names and the function description, InputIterator need not be an iterator. It can be of any type that meets the needs of accumulate. accumulate() needs to compare 2 items of the type for equality (==), de-reference the type (*) and pre-increment the type (++). These are met with an Input iterator - but also by a memory pointer. Hence a memory pointer can be passed for both first and last. This is basis of creating your own type/class that can be used with the std::algorithm library.

[JLBorges]

> Despite the names and the function description, InputIterator need not be an iterator.
> It can be of any type that meets the needs of accumulate. accumulate() needs ....
> These are met with an Input iterator - but also by a memory pointer.

Repeat: InputIterator must be an iterator that iterates over an input range.

Though the syntactic requirements are met by a pair of pointers, and the code compiles cleanly,

the semantics are violated if the pointers are not iterators that define an input range; this leads to general insanity.

For example:

#include <iostream>
#include <numeric>

int main()
{
    const double arr[] { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };

    // this is fine: std::begin(arr), std::end(arr) are iterators that define an input range
    std::cout << std::accumulate( std::begin(arr), std::end(arr), 0.0 ) << '\n' ; // fine: 1+1+2.2+3.3+4.4+5.5+6.6


    const double arr2[] { 8.8, 9.9 };

    // this will (unfortunately) compile cleanly: but engenders undefined behaviour
    // std::begin(arr), std::end(arr2) are pointers, but they are not iterators that define an input range
    std::cout << std::accumulate( std::begin(arr), std::end(arr2), 0.0 ) << '\n' ; // *** UB ***
}

[seeplus]

Same issue when using iterators:

int main() {
    const std::vector<double> arr {1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7};

    // this is fine: std::begin(arr), std::end(arr) are iterators that define an input range
    std::cout << std::accumulate(std::begin(arr), std::end(arr), 0.0) << '\n'; // fine: 1+1+2.2+3.3+4.4+5.5+6.6


    const std::vector<double> arr2 {8.8, 9.9};

    // this will (unfortunately) compile cleanly: but engenders undefined behaviour
    std::cout << std::accumulate(std::begin(arr), std::end(arr2), 0.0) << '\n'; // *** UB ***
    std::cout << std::accumulate(arr.begin(), arr2.end(), 0.0) << '\n'; // *** UB ***
}

arr.begin() and arr2.end() are both iterators of the same type. The code compiles OK but the iterators are part of different input ranges - so the same run-time issue!

[JLBorges]

> Same issue when using iterators ...

Yes. Whether the iterators are pointers or not, the semantic requirements of iterators to the beginning and end of a range must be met. This is the case for all algorithms that operate on ranges.

[frek]

So I hope you also express your opinion about my thought to see if you agree or not, please.

I assume we can use pointers for iterators (just like the code written in the first post) but not the other way around.

[JLBorges]

> I assume we can use pointers for iterators (just like the code written in the first post) but not the other way around.

Yes.

To repeat:

A pointer to an element of an array is a random access iterator; it meets all requirements of LegacyContiguousIterator / concept std::contiguous_iterator
(it is a random access iterator referring to elements that are contiguous in memory).

However, a generic iterator need not necessarily be a pointer. We can pass pointers to a generic function written in terms of iterators; but only pointers can be passed to a function written in terms of pointers.

An iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (with at least the increment (++) and dereference (*) operators).

The most obvious form of iterator is a pointer: A pointer can point to elements in an array, and can iterate through them using the increment operator (++). But other kinds of iterators are possible. For example, each container type (such as a list) has a specific iterator type designed to iterate through its elements.
https://www.cplusplus.com/reference/iterator/

[frek]

Thank you very much JL. :)