Hello,vector<int>::const_iterator ci = a.cbegin();
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>::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.
Hello,vector<int>::const_iterator ci = a.cbegin();
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>::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)
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.
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.
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.
Well, actually, erase(ci, ci) will return an iterator that'll point to ci+1, so an additional operator-- is needed.
--
---
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/.
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.
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.
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.)
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.
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.
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.
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.
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.
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);