boostorg / iterator Goto Github PK

Boost.org iterator module

Home Page: http://boost.org/libs/iterator

C++ 99.46% HTML 0.11% CMake 0.43%

iterator's Introduction

Boost.Iterator

Boost.Iterator, part of collection of the Boost C++ Libraries, provides tools for building and working with iterators in C++. The library also provides a number of iterator classes that can be used out of the box.

Directories

doc - Documentation sources
include - Interface headers of Boost.Iterator
test - Boost.Iterator unit tests
example - Boost.Iterator usage examples

More information

Documentation
Report bugs. Be sure to mention Boost version, platform and compiler you're using. A small compilable code sample to reproduce the problem is always good as well.
Submit your patches as pull requests against develop branch. Note that by submitting patches you agree to license your modifications under the Boost Software License, Version 1.0.

Build status

Branch	GitHub Actions	AppVeyor	Test Matrix	Dependencies
`master`
`develop`

License

Distributed under the Boost Software License, Version 1.0.

iterator's People

Contributors

Stargazers

Watchers

iterator's Issues

sgi page linked to by documentation is down

There are links in the doc that now redirect to some unrelated site. For example here the links to Input Iterator and Generator. The boost copy of those docs should probably be used.

[Feature request] Consider adding support of reference proxy

Continuing #47.
Currently, iterator_facade does not allow to have RandomAcess iterator with reference proxy (aka std::vector<bool>::iterator::reference) .

It looks like that the only thing that prevent this - is iterator-category deduction/override rules https://www.boost.org/doc/libs/1_68_0/libs/iterator/doc/iterator_facade.html :

iterator-category(C,R,V) :=
   if (C is convertible to std::input_iterator_tag
       || C is convertible to std::output_iterator_tag
   )
       return C

   else if (C is not convertible to incrementable_traversal_tag)
       the program is ill-formed

   else return a type X satisfying the following two constraints:

      1. X is convertible to X1, and not to any more-derived
         type, where X1 is defined by:

           if (R is a reference type
               && C is convertible to forward_traversal_tag)
           {
               if (C is convertible to random_access_traversal_tag)
                   X1 = random_access_iterator_tag
               else if (C is convertible to bidirectional_traversal_tag)
                   X1 = bidirectional_iterator_tag
               else
                   X1 = forward_iterator_tag
           }
           else
           {
               if (C is convertible to single_pass_traversal_tag
                   && R is convertible to V)
                   X1 = input_iterator_tag
               else
                   X1 = C
           }

      2. category-to-traversal(X) is convertible to the most
         derived traversal tag type to which X is also
         convertible, and not to any more-derived traversal tag
         type.

The simplest solution for now, seems to override manually iterator_category in Derived class.

Maybe add some proxy tag? Like:

class node_iterator
	: public boost::iterator_facade
	  <
		node_iterator
		, std::pair<int, int>
		, boost::bidirectional_traversal_tag
		, boost::iterator_facade::proxy_reference<std::pair<int, int>>
	  >

And do not downgrade iterator-category, if proxy_reference occurs.

Online links to example code are wrong

If you look at e.g. this page and attempt to follow the example code link you get a 404. @glenfe points out the link has an extra "/doc" in the path.

No constexpr support

With recent versions of C++, it is possible to have constexpr iterators, for example for std::array (and in c++20 for vector and string).
The boost iterator functionality, like transform_iterator, filter_iterator ... ain't constexpr and as a result can't be used at constexpr time.

function_output_iterator does not support specialization

I have a vector of std::byte and I want to call boost::unhex for this vector by creating a custom output iterator with my own unary function to convert unsiged char to std::byte. Note that std::byte is not an integral type so I cannot pass it directly to boost::unhex
It is possible to create a function_output_iterator where we can specify the value_type (ex, function_output_iterator<unsigned char>)?
The alternative I have is to create a vector of unsigned char then copy it into a vector of std::byte but this is what I want to avoid.

This is what I tried:

	const std::string hexString = "0A";
	auto outputVector = std::vector<std::byte>{};
	auto unary_func = [&](const unsigned char& c) { outputVector .push_back(std::byte{c}); };
	auto func_out_iterator = boost::make_function_output_iterator(unary_func);
	boost::algorithm::unhex(hexString, func_out_iterator );

and I got:

 error C2893: Failed to specialize function template 'boost::enable_if<boost::is_integral<hex_iterator_traits<OutputIterator>::value_type>,OutputIterator>::type boost::algorithm::detail::decode_one(InputIterator &,InputIterator,OutputIterator,EndPred)'

The documentation page for function_output_iterator doesn't answer TQN0

Documentation authors can safely assume that whenever somebody visits a documentation page to see documentation about a particular class, template, function, or any other kind of Thing That Can Be Used In Code, that person will, with absolute certainty, need to know the answer to The Question Number Zero (TQN0).

The Question Number Zero goes like this:

Which header file must I include in order to be able to use this thing in my code?

Please, always answer TQN0 on every documentation page that documents anything that needs an include file in other to be used.

https://www.boost.org/doc/libs/1_78_0/libs/iterator/doc/html/iterator/specialized/function_output.html

Visual Sudio won't compile iterator_traits

I'm using boost with the Visual Studio 2023's compiler (v143) and c++ 20. I haven't touched any of the provided code, I just included <boost/algorithm/string/split.hpp> and <boost/algorithm/string/classification.hpp> to use the metods split and is_any_of in my own code like so:
boost::algorithm::split(strings, payload, boost::algorithm::is_any_of(':'));.

When trying to compile I get these errors:

I'm taking a look at the code to see if I can solve the problem myself

Move headers out of boost/pending

Headers were likely never supposed to live in boost/pending for a long time. At this point boost/pending should be retired and the headers moved into their rightful and normal place. Here are the pending headers for this repository:

iterator/include/boost/pending/detail/int_iterator.hpp
iterator/include/boost/pending/iterator_adaptors.hpp
iterator/include/boost/pending/iterator_tests.hpp

Post-increment operator fails on an rvalue iterator

We have a custom container and a begin function that produces a iterator_facade-derived type:

Container c;

// This fails:
auto i = begin(c)++;

// This succeeds:
auto j = begin(c);
j++;

Could the operator++ in the following code take a universal reference (&&) instead of a standard reference (&)?:

  template <class I, class V, class TC, class R, class D>
  inline typename boost::iterators::detail::postfix_increment_result<I,V,R,TC>::type
  operator++(
      iterator_facade<I,V,TC,R,D>& i 
    , int
  )
  {
      typename boost::iterators::detail::postfix_increment_result<I,V,R,TC>::type
          tmp(*static_cast<I*>(&i));

      ++i;

      return tmp;
  }

Usage of boost/utility/addressof.hpp ?

I think this is now incorrect?

https://github.com/boostorg/iterator/blob/develop/include/boost/iterator/iterator_facade.hpp#L19:

#include <boost/utility/addressof.hpp>

should be

#include <boost/core/addressof.hpp>

boostorg/align#3 (comment)

function_input_iterator can't be used with `boost::join`

/opt/compiler-explorer/libs/boost_1_80_0/boost/range/concepts.hpp:160:26: error: no matching function for call to 'boost::iterators::function_input_iterator<generator, int>::function_input_iterator(boost::iterators::impl::function_input_iterator<generator, int>&)'
  160 |                 Iterator i2(++i);
      |                          ^~

Example: https://godbolt.org/z/o8hTEj5qx

List of non BOOST-prefixed macros

The following macros are missing a BOOST_ prefix, which is against Boost library guidelines:

./boost/shared_container_iterator.hpp:#ifndef SHARED_CONTAINER_ITERATOR_RG08102002_HPP
./boost/shared_container_iterator.hpp:#define SHARED_CONTAINER_ITERATOR_RG08102002_HPP
./boost/shared_container_iterator.hpp:#endif  // SHARED_CONTAINER_ITERATOR_RG08102002_HPP

adaptor_facade_base::operator[] returns value type with iterator of const values

iterator_facade_base::operator[] returns the iterator's value type if the iterated values are const and POD, as determined by boost::iterators::detail::operator_brackets_result. This results in subtle object lifetime errors in places where a reference is expected.

For example, if you use such an iterator with iterator_range, iterator_range::operator[] becomes UB, as it attempts to return the reference type:

std::vector<double> data{1.0, 3.14, 42.7, 2.618, 9.8};
std::vector<std::size_t> indices{1, 0, 2, 1, 3, 2, 4, 3};

auto const begin = boost::make_permutation_iterator(data.cbegin(), indices.cbegin());
auto const end = boost::make_permutation_iterator(data.cbegin(), indices.cend());

auto const range = boost::make_iterator_range(begin, end);
auto const& e = range[0];   // Returns reference to temporary, UB

Is there any reason why in this case iterator_facade_base::operator[] cannot return the reference type, or even a proxy object, instead?

CMakeLists.txt has false dependency on Boost::conversion

Needs to be regenerated with boostdep --cmake iterator.

Also, there's no CMake CI.

Let me know if you want a PR for either of these two.

transform_iterator end iterator with non-default-constructible unary function

Currently one have to construct/copy a second copy of transformation function for an end iterator what is unwanted and seems to be omission of the library design. For example, Boost.Range solves it via wrapping user functor with optional, unfortunately.

Past The End iterator dereference in filter_iterator

This simple test program segfaults on my GCC box with Boost 1.78

#include <boost/iterator/filter_iterator.hpp>
#include <iostream>
#include <array>

int main() {
    struct False { bool operator()(unsigned char) const { return false; } };

    std::array<char, 3> const s{'A','B','C'};
    using FIt = boost::iterators::filter_iterator<False, const char*>;

    for (FIt it(False{}, s.begin(), s.end()), end(s.end()); it != end; ++it) {
        std::cout << static_cast<int>(*it) << " ";
    };
}

See it live with ASAN: https://godbolt.org/z/8c9f1drGn

=================================================================
==1==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffc00329dc3 at pc 0x0000004fc947 bp 0x7ffc00329d90 sp 0x7ffc00329d88
READ of size 1 at 0x7ffc00329dc3 thread T0
    #0 0x4fc946 in main /app/example.cpp:12:39
    #1 0x7f90b8b920b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x240b2)
    #2 0x41f34d in _start (/app/output.s+0x41f34d)

Address 0x7ffc00329dc3 is located in stack of thread T0 at offset 35 in frame
    #0 0x4fc853 in main /app/example.cpp:5

  This frame has 1 object(s):
    [32, 35) 's' (line 8) <== Memory access at offset 35 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /app/example.cpp:12:39 in main
Shadow bytes around the buggy address:
  0x10000005d360: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d370: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d380: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d390: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d3a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10000005d3b0: 00 00 00 00 f1 f1 f1 f1[03]f3 f3 f3 00 00 00 00
  0x10000005d3c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d3d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d3e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d3f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10000005d400: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==1==ABORTING

bidirectional_traversal_tag not work with std::prev

In the following code bidirectional_traversal_tag does not work with std::prev. Iterator does not recognized as bidirirectional.

#include <iostream>
#include <boost/iterator/iterator_facade.hpp>

class node_iterator
	: public boost::iterator_facade
	  <
		node_iterator
		, std::pair<int, int>
		, boost::bidirectional_traversal_tag
		, std::pair<int, int>
	  >
{
public:
	node_iterator()
		: m_i(0) {}

	explicit node_iterator(int i)
		: m_i(i) {}

private:
	friend class boost::iterator_core_access;

	void increment() { m_i++; }
        void decrement() { m_i--; }

	bool equal(node_iterator const& other) const
	{
		return this->m_i == other.m_i;
	}

	std::pair<int, int> dereference() const { return { m_i, m_i}; }
public:
	int m_i;
};


int main()
{
	auto i1  = node_iterator(1);
	auto i10 = node_iterator(10);

       std::next(i1);
       std::prev(i1);
	
	std::cout <<"aaa";
}

Online : https://wandbox.org/permlink/T51UwajOX4Lf8aif

`shared_iterator_test.cpp` from Utility needs to be moved here

It looks like we've moved boost/shared_container_iterator.hpp here, but forgot the test.

counting_iterator used as a forward iterator in <algorithm> generates warning in C++17

Following results in iterator_adaptor.hpp(318,1): warning C4244: '+=': conversion from '__int64' to 'Base', possible loss of data

std::for_each(std::execution::par, boost::counting_iterator<int>(0), boost::counting_iterator<int>(10), [&](int) {});

iterator_adaptor and std::prev

Hi,

I have some troubles with iterator_adaptor with the default CategoryOrTraversal and std::prev. Indeed, in order to have it work I need to manually pass std::bidirectional_iterator_tag. With g++ on linux I have an infinite loop with the default tag and MSVC gives the following error:

1>C:\Program Files\Microsoft Visual Studio\2022\Professional\VC\Tools\MSVC\14.35.32215\include\xutility(1241,19): error C2338: static_assert failed: 'prev requires bidirectional iterator'

Minimal code:

#include <list>
#include <iostream>
#include <boost/iterator/iterator_adaptor.hpp>

// infinite loop or compilation error with the following
#define Base boost::iterator_adaptor<Adapted, std::list<int>::iterator, int, boost::use_default, int>
// no error with the following
//#define Base boost::iterator_adaptor<Adapted, std::list<int>::iterator, int, std::bidirectional_iterator_tag, int>

struct Adapted
  : public Base
{
  Adapted() {}

  Adapted(std::list<int>::iterator it)
    : Base(it)
  {}

private:
  friend class boost::iterator_core_access;
  int dereference() const { return *this->base(); }
};

int main()
{

  std::list<int> l;
  l.push_back(0);
  l.push_back(1);
  l.push_back(2);

  Adapted ai(std::next(l.begin()));

  std::cout << typeid(std::iterator_traits<Adapted>::iterator_category).name() << "\n";

  std::cout << *ai << "\n";
  std::cout << *std::next(ai) << "\n";
  std::cout << *std::prev(ai) << "\n"; // infinite loop with g++ and compilation error with MSVC

  return 0;
}

C++ - what is the error with this code please

call to advance is ambiguous for a (every?) type in the boost namespace?

This code

#include <boost/iterator/advance.hpp>
#include <vector>

namespace boost {
        class test {};
}

void f(std::vector<boost::test>& c) {
        using std::advance;
        auto it = c.begin();
        advance(it, 1);
}

fails to compile since boost 1.65 on both GCC and Clang with the same error, the call to advance is ambiguous:

: In function 'void f(std::vector >&)': :8:18: error: call of overloaded 'advance(__gnu_cxx::__normal_iterator*, std::vector > >&, int)' is ambiguous
/opt/compiler-explorer/gcc-8.2.0/include/c++/8.2.0/bits/stl_iterator_base_funcs.h:202:5: note: candidate: 'constexpr void std::advance(_InputIterator&, _Distance) [with _InputIterator = __gnu_cxx::__normal_iterator<boost::shared_ptr*, std::vector<boost::shared_ptr > >; _Distance = int]'

/opt/compiler-explorer/libs/boost_1_65_0/boost/iterator/advance.hpp:68:9: note: candidate: 'constexpr void boost::iterators::advance_adl_barrier::advance(InputIterator&, Distance) [with InputIterator = __gnu_cxx::__normal_iterator<boost::shared_ptr*, std::vector<boost::shared_ptr > >; Distance = int]'

The include <boost/iterator/advance.hpp> was introduced with boost 1.65 among some tests that, unluckily, never tests an unqualified call to advance.

call to 'advance' is ambiguous

I upgraded my boost library from 1.62 to 1.67 (issue remains with 1.68) and now I'm getting "call to 'advance' is ambiguous". After some investigation it looks like a using statment in boost/iterator/advance.hpp:80 is causing the issue. The problem arises if advance is called unqualified, so that ADL triggers. boost 1.65 seems to be the first release with this issue.

In my case this means that I cannot use range-v3 (this lib is making the unqualified call to advance) together with boost geometry (this uses boost-iterator's advance function and therefor includes boost/iterator/advance.hpp).

Here is a minimal code example, which causes this issue:
https://godbolt.org/z/rSfeVi