iterator container::access(const_iterator); member function for containers.

[Maurice Bos]

Hello,

Since C++11, a lot of member functions of containers that used to take (non-const) iterators, now take const_iterators (such as insert, erase, etc.), since those member functions can only be called on non-const containers anyway and can thus modify it.

However, what seems to be missing is to get a (non-const) iterator, given a non-const (reference to) a constainer and a const_iterator in it. For example:

vector<int> a;

vector<int>::const_iterator ci = a.cbegin();
vector<int>::iterator i = a.access(ci); // turn it into a non-const iterator.

Although this is already possible, there is currently no cross-container way do this in O(1):

For a vector: auto i = a.begin() + (ci - a.begin());
For a list: auto i = a.erase(ci, ci); // This is only guaranteed to be O(n) for a std::vector, although in most implementations this will be O(1)

I needed this when i was making a class template called 'vectorset', which has the interface of a std set, but keeps its contents in a vector (or list, or deque, or anything else with a vector-like interface, depending on a template parameter). (It has less efficient inserting and erasing obviously, but it's more memory efficient and probably a better choice for, for example, a (mostly) constant set of just a few integers.) To make the insert member function take a const_iterator as hint, i needed to convert it to a non-const iterator, which can currently not be done in one way that's O(1) for all containers.

Has anybody else encountered such a situation? Any arguments against adding this funcitonality?

Kind regards,
Maurice Bos

[Nicol Bolas]

On Saturday, August 24, 2013 4:39:57 AM UTC-7, Maurice Bos wrote:

Hello,

Since C++11, a lot of member functions of containers that used to take (non-const) iterators, now take const_iterators (such as insert, erase, etc.), since those member functions can only be called on non-const containers anyway and can thus modify it.

However, what seems to be missing is to get a (non-const) iterator, given a non-const (reference to) a constainer and a const_iterator in it. For example:

vector<int> a;

vector<int>::const_iterator ci = a.cbegin();
vector<int>::iterator i = a.access(ci); // turn it into a non-const iterator.

Um, no. That's like saying you have a `const &` to something and you want a non-`const` reference to it. Yes, there's a way to do it, but you should pretty much never employ it. If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with.

Although this is already possible, there is currently no cross-container way do this in O(1):

For a vector: auto i = a.begin() + (ci - a.begin());
For a list: auto i = a.erase(ci, ci); // This is only guaranteed to be O(n) for a std::vector, although in most implementations this will be O(1)

I needed this when i was making a class template called 'vectorset', which has the interface of a std set, but keeps its contents in a vector (or list, or deque, or anything else with a vector-like interface, depending on a template parameter). (It has less efficient inserting and erasing obviously, but it's more memory efficient and probably a better choice for, for example, a (mostly) constant set of just a few integers.) To make the insert member function take a const_iterator as hint, i needed to convert it to a non-const iterator, which can currently not be done in one way that's O(1) for all containers.

Why do you need to convert it to a non-const iterator? std::set::insert only takes an iterator as a hint. If you're implementing a flat_set (which BTW, Boost has already done for you), you should use it to tell you the position in the array for where to start looking. You don't need this position to be modifiable. You can convert it into an array index easily enough, for example.

Or better yet, you can do whatever you want. It is, after all, your iterator; you can convert it into a non-const pointer to the array element if you like. It can have whatever private interface on it you like. You are not restricted to the same interface that you permit others to have.

You do not need to expose to others a public interface to do a const_cast on your iterator. You just need to do that cast yourself.

[Ville Voutilainen]

On 24 August 2013 14:39, Maurice Bos <m-o...@m-ou.se> wrote:

Hello,

Since C++11, a lot of member functions of containers that used to take (non-const) iterators, now take const_iterators (such as insert, erase, etc.), since those member functions can only be called on non-const containers anyway and can thus modify it.

However, what seems to be missing is to get a (non-const) iterator, given a non-const (reference to) a constainer and a const_iterator in it. For example:

vector<int> a;

vector<int>::const_iterator ci = a.cbegin();
vector<int>::iterator i = a.access(ci); // turn it into a non-const iterator.

Although this is already possible, there is currently no cross-container way do this in O(1):

For a vector: auto i = a.begin() + (ci - a.begin());
For a list: auto i = a.erase(ci, ci); // This is only guaranteed to be O(n) for a std::vector, although in most implementations this will be O(1)

Isn't N==1 in the latter? Seems to me that erase(ci, ci) does what you want on every container I can find.

[Ville Voutilainen]

Well, actually, erase(ci, ci) will return an iterator that'll point to ci+1, so an additional operator-- is needed.

[Daniel Krügler]

2013/8/24 Ville Voutilainen <ville.vo...@gmail.com>:

IMO, we shouldn't teach people to use tricky combinations of library
functionality to realize a well-defined coding pattern. C++11
respected that many iterator arguments that are part of some API
function are pure position specifiers. The access function suggested
above allows more than that, but it is still const-correct in all
respects, so I do disagree with Nicol that this is similar to a
const_cast. The presented workarounds (which look ugly to me and I
don't consider them as acceptable ones), just demonstrate that if I
have a non-const container I do have full access to what the interface
allows me to do - including "computing" the non-const iterator of a
given const_iterator. The access function would still be right for
sets, which are basically immutable, albeit of little advantage, but
IMO reasonable for symmetry reasons.

My personal recommendation would be to change the name, though,
because "access" sounds too generic to me. I remember that during some
committee meeting someone suggested a name along the side of
"to_iterator". I might even make sense to make this a free function
and allow ADL to find the right one, so we can use the same code
pattern for built-in arrays as well.

- Daniel

[Ville Voutilainen]

200% agreed. to_iterator() sounds fine to me. Let the bike-shedding begin. :)

Want to co-author an LEWG paper? The target would likely be a library TS
and c++17 after that, I have no interest in pushing this into c++14.

[Daniel Krügler]

> 200% agreed. to_iterator() sounds fine to me. Let the bike-shedding begin.
> :)
> Want to co-author an LEWG paper?

Sure.

> The target would likely be a library TS
> and c++17 after that, I have no interest in pushing this into c++14.

I agree.

- Daniel

[Maurice Bos]

2013/8/24 Nicol Bolas <jmck...@gmail.com>

Um, no. That's like saying you have a `const &` to something and you want a non-`const` reference to it. Yes, there's a way to do it, but you should pretty much never employ it. If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with.

No, modifying functions like insert and erase take a const_iterator. So "If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with." is invalid.

Why do you need to convert it to a non-const iterator? std::set::insert only takes an iterator as a hint. If you're implementing a flat_set (which BTW, Boost has already done for you), you should use it to tell you the position in the array for where to start looking. You don't need this position to be modifiable. You can convert it into an array index easily enough, for example.

"You can convert it into an array index easily enough"... Well, no, that's my point. For arrays/vectors, yes, but you can't get do it in O(1) in a way that works for all containers...
 

Or better yet, you can do whatever you want. It is, after all, your iterator; you can convert it into a non-const pointer to the array element if you like. It can have whatever private interface on it you like. You are not restricted to the same interface that you permit others to have.

No, it isn't *my* iterator. The vectorset/flat_set/whatever just can just use the iterators of the underlying container. It are vector/list/deque's iterators, not 'my' iterators.

[Maurice Bos]

2013/8/24 Ville Voutilainen <ville.vo...@gmail.com>

For a vector: auto i = a.begin() + (ci - a.begin());
For a list: auto i = a.erase(ci, ci); // This is only guaranteed to be O(n) for a std::vector, although in most implementations this will be O(1)

Isn't N==1 in the latter? Seems to me that erase(ci, ci) does what you want on every container I can find.

In all implementations, probably. But according to the standard the move constructor will be called std::distance(ci, a.end()) times, making it O(distance(ci, a.end()). It doesn't describe a special case for when the given range is empty.

[Maurice Bos]

2013/8/24 Ville Voutilainen <ville.vo...@gmail.com>

Well, actually, erase(ci, ci) will return an iterator that'll point to ci+1, so an additional operator-- is needed.

Nope, that's not true. It gives the right iterator right away: [sequence.reqmts]: "The iterator returned by a.erase(q1,q2) points to the element pointed to by q2 prior to any elements being erased."

[Maurice Bos]

to_iterator indeed sounds a lot better. :)

I'm sorry, but what does TS mean in 'library TS'? I don't recognize the acronym. (I'm quite new to C++ standardization.)

2013/8/24 Ville Voutilainen <ville.vo...@gmail.com>

--
 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Bengt Gustafsson]

How about unconst(). to_iterator is still somewhat vague, when it comes to what it is useful for.

I would have guessed that to_iterator woudl take an index and return "begin() + index".

[Christof Meerwald]

On Sat, Aug 24, 2013 at 07:20:41PM +0200, Maurice Bos wrote:
> I'm sorry, but what does TS mean in 'library TS'? I don't recognize the
> acronym. (I'm quite new to C++ standardization.)

Technical Specification, see
http://isocpp.org/std/iso-iec-jtc1-procedures


Christof

--

http://cmeerw.org sip:cmeerw at cmeerw.org
mailto:cmeerw at cmeerw.org xmpp:cmeerw at cmeerw.org

[Nicol Bolas]

On Saturday, August 24, 2013 10:08:17 AM UTC-7, Maurice Bos wrote:

2013/8/24 Nicol Bolas <jmck...@gmail.com>

Um, no. That's like saying you have a `const &` to something and you want a non-`const` reference to it. Yes, there's a way to do it, but you should pretty much never employ it. If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with.

No, modifying functions like insert and erase take a const_iterator. So "If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with." is invalid.

But you're not modifying the item referenced by the iterator. You're modifying the container; the iterator is just a hint about where the data should go. That's why set::insert is not const.

Why do you need to convert it to a non-const iterator? std::set::insert only takes an iterator as a hint. If you're implementing a flat_set (which BTW, Boost has already done for you), you should use it to tell you the position in the array for where to start looking. You don't need this position to be modifiable. You can convert it into an array index easily enough, for example.

"You can convert it into an array index easily enough"... Well, no, that's my point. For arrays/vectors, yes, but you can't get do it in O(1) in a way that works for all containers...

But that's irrelevant for your case, since your flat_set is using a std::vector for the array. Which is rather the point.

Unless you want to allow people to use std::list (which would be utterly idiotic. They should just use std::set) or arbitrary other containers. And if you do, see below.

Or better yet, you can do whatever you want. It is, after all, your iterator; you can convert it into a non-const pointer to the array element if you like. It can have whatever private interface on it you like. You are not restricted to the same interface that you permit others to have.

No, it isn't *my* iterator. The vectorset/flat_set/whatever just can just use the iterators of the underlying container. It are vector/list/deque's iterators, not 'my' iterators.

Every programming problem can be solved by adding an additional layer of indirection. And this is no exception. So if, for whatever reason, you don't know that you're using a vector, you can simply create a wrapper iterator class that contains the underlying iterator. Your const_iterator could contain a non-const internal iterator.

Most people don't need to perform a const_cast on iterators, and I would go so far as to say that if you have written code where you need to, you're doing it wrong.

[Maurice Bos]

2013/8/25 Nicol Bolas <jmck...@gmail.com>

On Saturday, August 24, 2013 10:08:17 AM UTC-7, Maurice Bos wrote:

2013/8/24 Nicol Bolas <jmck...@gmail.com>

Um, no. That's like saying you have a `const &` to something and you want a non-`const` reference to it. Yes, there's a way to do it, but you should pretty much never employ it. If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with.

No, modifying functions like insert and erase take a const_iterator. So "If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with." is invalid.

But you're not modifying the item referenced by the iterator. You're modifying the container; the iterator is just a hint about where the data should go. That's why set::insert is not const.

Sure, but I can't modify the container at the point the hint points to, without a dirty trick as erasing an empty range at the hint, or iterating distance(begin, hint) from begin. Depending on how you implement the flat_set, it might not be needed since you can pass the problem on to the insert/erase functions of the underlying container. However, imagine another container wrapper that only gives the user const access to the elements (simply through const_iterators of the underlying container), and only allows modification through member functions. Those member functions should take a const_iterator to point to which element needs to be changed. Those member functions somehow need to modify the element the const_iterator pointed to. (Which is still const-correct, because the member functions have non-const access to the container.) (This to make sure that only the 'wrapper' class, and not anybody else, can modify the underlying container.)

Or think of a function 'foobar' that, like std::upper_bound, looks up a position inside a range. Since the function does not modify the container, but only gives you a position depending on the values in the range, it should just take const_iterators and return a const_iterator. However, if const_iterators aren't convertible to iterators when you have non-const access to the container, a function having the (non-const) container can't use foobar to look up an element in the container and then change that element. For that, another overload of 'foobar' needs to be made that works on non-const iterators, which would suggest 'foobar' modifies the elements the iterators point to, which is not the case. (So adding this to_iterator functionality will actually improve const-correctness in this case.)
 

Why do you need to convert it to a non-const iterator? std::set::insert only takes an iterator as a hint. If you're implementing a flat_set (which BTW, Boost has already done for you), you should use it to tell you the position in the array for where to start looking. You don't need this position to be modifiable. You can convert it into an array index easily enough, for example.

"You can convert it into an array index easily enough"... Well, no, that's my point. For arrays/vectors, yes, but you can't get do it in O(1) in a way that works for all containers...

But that's irrelevant for your case, since your flat_set is using a std::vector for the array. Which is rather the point.

Eh, no. It could use any sequence container. I agree that std::list would not be useful in this case, but std::deque might. Also, any other container anybody implemented outside std::, or any containers that will be added later to the standard, might also have useful properties for this purpose. (Such as boost::static_vector.)

 

Unless you want to allow people to use std::list (which would be utterly idiotic. They should just use std::set) or arbitrary other containers. And if you do, see below.

Or better yet, you can do whatever you want. It is, after all, your iterator; you can convert it into a non-const pointer to the array element if you like. It can have whatever private interface on it you like. You are not restricted to the same interface that you permit others to have.

No, it isn't *my* iterator. The vectorset/flat_set/whatever just can just use the iterators of the underlying container. It are vector/list/deque's iterators, not 'my' iterators.

Every programming problem can be solved by adding an additional layer of indirection. And this is no exception. So if, for whatever reason, you don't know that you're using a vector, you can simply create a wrapper iterator class that contains the underlying iterator. Your const_iterator could contain a non-const internal iterator.

So you prefer adding a whole other layer of indirection over just giving functionality that is already there (.erase(i,i)) a proper name (and making it O(1))?
 

Most people don't need to perform a const_cast on iterators, and I would go so far as to say that if you have written code where you need to, you're doing it wrong.

Like Daniel already said, it is perfectly const-correct. It is nothing like a const_cast. If it weren't const-correct, erase wouldn't turn its second parameter (a const_iterator) into an iterator.

[Nicol Bolas]

On Sunday, August 25, 2013 2:53:19 AM UTC-7, Maurice Bos wrote:

2013/8/25 Nicol Bolas <jmck...@gmail.com>

On Saturday, August 24, 2013 10:08:17 AM UTC-7, Maurice Bos wrote:

2013/8/24 Nicol Bolas <jmck...@gmail.com>

Um, no. That's like saying you have a `const &` to something and you want a non-`const` reference to it. Yes, there's a way to do it, but you should pretty much never employ it. If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with.

No, modifying functions like insert and erase take a const_iterator. So "If you were meant to have modifiable access to the container, you wouldn't have been given a const_iterator to begin with." is invalid.

But you're not modifying the item referenced by the iterator. You're modifying the container; the iterator is just a hint about where the data should go. That's why set::insert is not const.

Sure, but I can't modify the container at the point the hint points to, without a dirty trick as erasing an empty range at the hint, or iterating distance(begin, hint) from begin. Depending on how you implement the flat_set, it might not be needed since you can pass the problem on to the insert/erase functions of the underlying container. However, imagine another container wrapper that only gives the user const access to the elements (simply through const_iterators of the underlying container), and only allows modification through member functions. Those member functions should take a const_iterator to point to which element needs to be changed. Those member functions somehow need to modify the element the const_iterator pointed to. (Which is still const-correct, because the member functions have non-const access to the container.) (This to make sure that only the 'wrapper' class, and not anybody else, can modify the underlying container.)

Or think of a function 'foobar' that, like std::upper_bound, looks up a position inside a range. Since the function does not modify the container, but only gives you a position depending on the values in the range, it should just take const_iterators and return a const_iterator. However, if const_iterators aren't convertible to iterators when you have non-const access to the container, a function having the (non-const) container can't use foobar to look up an element in the container and then change that element.

That doesn't make sense. If you give a function a const_iterator, the whole point of doing that is so that it can't modify the data referenced through that iterator. So if the calling function needs to modify an element, then the calling function will not be using const_iterators. It's really that simple.

There's a reason std::upper_bound is templated on the iterator type.

If you want to modify what comes out of std::upper_bound, then you don't pass it const_iterators. Just like you wouldn't pass it const pointers if you want to modify the data pointed to by the return value.

For that, another overload of 'foobar' needs to be made that works on non-const iterators, which would suggest 'foobar' modifies the elements the iterators point to, which is not the case. (So adding this to_iterator functionality will actually improve const-correctness in this case.)

Or you have a template `foobar` that works with what you give it. Just like std::upper_bound. There's no reason someone should be restricted from passing pointers or other iterator-like things.

Why do you need to convert it to a non-const iterator? std::set::insert only takes an iterator as a hint. If you're implementing a flat_set (which BTW, Boost has already done for you), you should use it to tell you the position in the array for where to start looking. You don't need this position to be modifiable. You can convert it into an array index easily enough, for example.

"You can convert it into an array index easily enough"... Well, no, that's my point. For arrays/vectors, yes, but you can't get do it in O(1) in a way that works for all containers...

But that's irrelevant for your case, since your flat_set is using a std::vector for the array. Which is rather the point.

Eh, no. It could use any sequence container. I agree that std::list would not be useful in this case, but std::deque might. Also, any other container anybody implemented outside std::, or any containers that will be added later to the standard, might also have useful properties for this purpose. (Such as boost::static_vector.)

Are you making a container, or a container adapter like std::stack and std::queue? Because those are completely different things with very different expectations.

There's a reason std::flat_set doesn't have a parameter for the internal container. That's because, if it uses an internal container at all, it's just an implementation detail.

Or better yet, you can do whatever you want. It is, after all, your iterator; you can convert it into a non-const pointer to the array element if you like. It can have whatever private interface on it you like. You are not restricted to the same interface that you permit others to have.

No, it isn't *my* iterator. The vectorset/flat_set/whatever just can just use the iterators of the underlying container. It are vector/list/deque's iterators, not 'my' iterators.

Every programming problem can be solved by adding an additional layer of indirection. And this is no exception. So if, for whatever reason, you don't know that you're using a vector, you can simply create a wrapper iterator class that contains the underlying iterator. Your const_iterator could contain a non-const internal iterator.

So you prefer adding a whole other layer of indirection over just giving functionality that is already there (.erase(i,i)) a proper name (and making it O(1))?

vector::erase only does that as a side effect, not its intended purpose. Indeed, I'd rather that this was fixed in vector::erase, so that passing the same iterator will fail or something.

Most people don't need to perform a const_cast on iterators, and I would go so far as to say that if you have written code where you need to, you're doing it wrong.

Like Daniel already said, it is perfectly const-correct. It is nothing like a const_cast. If it weren't const-correct, erase wouldn't turn its second parameter (a const_iterator) into an iterator.

It doesn't "turn its second parameter" into anything. It creates a new iterator, since after the erasure, the old iterator may be invalid. See the difference? It's not converting anything.

It's const-correct because the container itself must be non-const to do that. And that means that the container can generate whatever non-const iterator it wants.

[Maurice Bos]

2013/8/25 Nicol Bolas <jmck...@gmail.com>:

That doesn't make sense. If you give a function a const_iterator, the whole point of doing that is so that it can't modify the data referenced through that iterator. So if the calling function needs to modify an element, then the calling function will not be using const_iterators. It's really that simple.

So if a function has both a const pointer and a non-const pointer to an object, it can't modify it? The member function itself is non-const, so it has non-const access to the container, it may modify anything it wants. If i wanted to guarantee it doesn't modify anything, i would've made the member function itself const apart from making it take a const_iterator.
 

There's a reason std::upper_bound is templated on the iterator type.

Yes, that reason is that it can work on all containers. Not that it can give the finger to const-correctness and take a non-const iterator even though it doesn't modify anything. That's just a handy side effect.

Are you making a container, or a container adapter like std::stack and std::queue? Because those are completely different things with very different expectations.

There's a reason std::flat_set doesn't have a parameter for the internal container. That's because, if it uses an internal container at all, it's just an implementation detail.

I guess you could call it a container adapter. It just wraps another container, keeps some invariants true, and provides an interface almost equal to std::set. Let's not go too deep into detail of 'flat_set' or my implementation of a similar container. It is just one example of a context in which to_iterator could help.

std::flat_set doesn't exist.

Like Daniel already said, it is perfectly const-correct. It is nothing like a const_cast. If it weren't const-correct, erase wouldn't turn its second parameter (a const_iterator) into an iterator.

It doesn't "turn its second parameter" into anything. It creates a new iterator, since after the erasure, the old iterator may be invalid. See the difference? It's not converting anything.

It does for std::list.

It's const-correct because the container itself must be non-const to do that. And that means that the container can generate whatever non-const iterator it wants.

Exactly, the container can do that. Then why not the one who owns the (non-const) container?

[Maurice Bos]

2013/8/25 Nicol Bolas <jmck...@gmail.com>

vector::erase only does that as a side effect, not its intended purpose. Indeed, I'd rather that this was fixed in vector::erase, so that passing the same iterator will fail or something.

Really? You want to make perfectly valid code like this fail?

    std::vector<int> v = {1,2,3,5,6};
    auto p = std::equal_range(v.begin(), v.end(), 4);
    v.erase(p.first, p.second);