Jump to content
  • Advertisement
Sign in to follow this  
Lode

std::list: iterator or const_iterator?

This topic is 3074 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I had a datastructure (a contour existing out of points and edges) implemented as std::vector, and some struct that represents indices of two edges. These indices were of course just integers, the index of something in an std::vector. However I decided that it's better to use std::list instead of std::vectors. So the indices would have to become iterators of the std::list. But... I was using these indices both for const Contours and non-const Contours. An integer index of an std::vector can be used both for const and non const ones. The const-ness of the std::vector determines what you can do. If I'd switch to std::list, what do I have to use in my struct, const_iterator or iterator? const_iterator will make my struct useless when working on a non-const list and wanting to change something. Non-const iterators can't be gotten from a const list (AFAIK). So nothing will work! Is there any equivalent as integers to std::vector, but then for std::lists?

Share this post


Link to post
Share on other sites
Advertisement
Even with a vector you cant modify the contents through a const_iterator. The fact that its really just an int is irrelevant, the whole point of an iterator is to hide that from you. Im not sure i understand the problem though, youre saying that you cant get an iterator to a const list, but thats the whole point. If youre saying you *need* to be able to modify a const list maybe theres a design flaw somewhere

Share this post


Link to post
Share on other sites
Quote:
However I decided that it's better to use std::list instead of std::vectors.
First of all, why? If it's because middle insertion/deletion is faster, there are potentially ways to use std::vector for that.

Quote:
If I'd switch to std::list, what do I have to use in my struct, const_iterator or iterator? const_iterator will make my struct useless when working on a non-const list and wanting to change something. Non-const iterators can't be gotten from a const list (AFAIK).


The following code converts a const iterator into a non-const iterator, given non-const access to its container.

template<typename ContainerType>
typename ContainerType::iterator unconstify(ContainerType & container, typename ContainerType::const_iterator iter)
{
std::iterator_traits<typename ContainerType::const_iterator>::difference_type index =
std::distance(const_cast<ContainerType const&>(container).begin(), iter);
typename ContainerType::iterator res = container.begin();
std::advance(res, index);
return res;
}

Oh, const correctness, you're totally worth O(n) conversions! [wink] (Incidentally, that code will work in O(1) on vectors.) You might consider doing that in debug mode, and this in release mode:

template<typename ContainerType>
typename ContainerType::iterator unconstify(ContainerType & container, typename ContainerType::const_iterator iter)
{
return reinterpret_cast<typename ContainerType::iterator &>(iter);
}

...which is, of course, utterly unsafe, but will probably work on your particular STL implementation. Maybe. (Anyone wanna weigh in on whether iterator checking and/or COW will screw it up?)

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
Even with a vector you cant modify the contents through a const_iterator.


But I used a simple integer index there, instead of the iterator type :)

Quote:
Original post by Sneftel
First of all, why? If it's because middle insertion/deletion is faster, there are potentially ways to use std::vector for that.


What kind of ways?

I thought indeed to do it with std::lists for those cases of insertions in the middle and such, but other than that I'd pick std::vectors for the convenience factor.

So any argument in favor of std::vectors for representing polygon contours is very good news to me! :)

Share this post


Link to post
Share on other sites
If the std::vector was more convenient, then that's what I would use until I determined that middle insertions and deletions were a bottleneck. It seems like you're making things more difficult on yourself, although admittedly indices into a vector need to be update if it's modified so perhaps that's an issue?

Alternatively, try to eliminate the indices altogether. If you're using them to index adjacent edges, then adjacency in the vector itself could tell you the same thing.

Share this post


Link to post
Share on other sites
Quote:
Original post by Lode
Quote:
Original post by cache_hit
Even with a vector you cant modify the contents through a const_iterator.


But I used a simple integer index there, instead of the iterator type :)

Quote:
Original post by Sneftel
First of all, why? If it's because middle insertion/deletion is faster, there are potentially ways to use std::vector for that.


What kind of ways?

I thought indeed to do it with std::lists for those cases of insertions in the middle and such, but other than that I'd pick std::vectors for the convenience factor.

So any argument in favor of std::vectors for representing polygon contours is very good news to me! :)


It's possible I'm just missing something, but I still dont' see the issue. When you had indices and vectors you said you were just fine and you were able to modify the vector. If that's the case, then obviously didn't have a const vector.

Well, if you don't have a const list, you can perfectly well use list::iterator and modify items with no problem.

If you do have a const list, then use list::const_iterator. It seems like you feel like you have to make a global decision between *either* iterator *or* const_iterator. You can use both, if the list is const use const_iterator always. If the list is not const, use iterator if you're writing to the list, and const_iterator if you're reading from the list.


Even if you do end up deciding that vector is more appropriate than list for what you're doing, just make sure it's for the right reason - because I'm not sure that the issue you originally asked about with list is even an issue at all.

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
It's possible I'm just missing something, but I still dont' see the issue.

The issue is that there is a need to refer to connectivity in a constness-independent form. A non-const iterator or pointer guarantees access with no further qualifications; a const iterator or pointer restricts access utterly, even to users that should be able to acquire it. An integer index does neither of these thing: It allows read-only access to the element given const access to the referenced container, and read-write access to the element given non-const access to the referenced container.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by cache_hit
It's possible I'm just missing something, but I still dont' see the issue.

The issue is that there is a need to refer to connectivity in a constness-independent form. A non-const iterator or pointer guarantees access with no further qualifications; a const iterator or pointer restricts access utterly, even to users that should be able to acquire it. An integer index does neither of these thing: It allows read-only access to the element given const access to the referenced container, and read-write access to the element given non-const access to the referenced container.


Sure, but certainly you *know* whether or not you have a const container right? If you have a const container, perhaps because you're in a const member function of the containing class, or because you have a const reference / pointer to containing class, then you declare an iterator of type const_iterator. If you aren't under that restriction, you make an iterator.

The only difference is that with an index you don't actually have to spell out whether you want read/write access or read-only access. But it's still explicit in the code, because you're either writing to the collection or you're not. If you're about to do something that writes to the list, declare an iterator of type list<T>::iterator. Otherwise declare an iterator of type list<T>::const_iterator.

I seem to be the only person in this thread that doesn't get it, could you post a short code sample illustrating the problem?

Share this post


Link to post
Share on other sites
After thinking about it some more, the only example I can think of where I can understand a possible issue is if you have some const function which is supposed to do some preliminary work, searching or whatever, and then cache the location of some value (i.e an iterator) that is of interest. Then later you go through and need to modify the value. If that's the case then I would argue that the search function shouldn't have been const in the first place. If it's an issue though, I would suggest considering whether or not the use of 'mutable' would be warranted

Upon re-reading the original post, it seems like the OP is trying to use the same data structure to operate on both const contours and contours. In this case, it's hard to say whether it's an issue or not unless I know what "const contour" means. Is this some template class that is sometimes parameterized as either SomeClass<contour>, and sometimes as SomeClass<const contour>? If so, the problem is as simple as using an is_const metafunction and typedefing the appropriate iterator as a private member of the class.

Maybe I'm still not getting it though. /shrug

Share this post


Link to post
Share on other sites
It's difficult to give a straightforward code sample-- I just tried for about ten minutes and man was that a confusing example. I'll try to give a simple illustration of a related problem, and see if any lightbulbs go on.

Consider this binary tree node, and the evil things we can do with it.


class Node
{
public:
Node* GetParent() const;
Node* GetLeftChild() const;
Node* GetRightChild() const;
};

Node* evilly_subvert_constness(Node const* node)
{
return node->GetLeftChild()->GetParent();
}


Ew, right? We might be tempted to do this:

class Node
{
public:
Node* GetParent();
Node const* GetParent() const;
Node* GetLeftChild();
Node const* GetLeftChild() const;
Node* GetRightChild();
Node const* GetRightChild() const;
};


But that's not quite right either. Pointing const-ly to a Node says we're not gonna change it, but it doesn't -- and shouldn't -- say we can't change the things it knows about. It kinda feels right to restrict the interface in this way, but the fact that these are restrictions we're adding suggests that C++ doesn't think of constness as being quite this strong.

Also consider this:

Node const* find_closest_male_descendant_named_Frances(Node const* node);


Which is fine if we just want to inspect that relative. But what if we want to change it? We could make a non-const version of the code (requiring, BTW, the wholesale copy and paste and s/const//g of 18 auxiliary functions, representing 1300 lines of code, YIKES) but that doesn't feel right either, because all this searching in the family tree really SHOULD be guaranteed not to change anything.

What we really want is a way to talk about const-ness context for the family tree as a whole. Either we are a piece of code which is allowed to make babies and give them to people, or we are not. If we are, fine, all the code we need operates on const*s and returns const*s. If we are, however, all the constness in the world should not keep us from controlling Nodes that are under our control.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!