Invalidating iterators after insertion/removal


If I insert/remove an element in a set, will an iterator to this set automatically become invalid Does the position of the iterator before the insertion/removal matter How are vectors and lists affected...
Posted On: Monday 26th of November 2012 12:49:45 AM Total Views:  289
View Complete with Replies

RELATED TOPICS OF C Language PROGRAMMING LANGUAGE




std::map iterators

In an std::map, iterators do not become invalid if other elements are added erased. Just to make sure, does that mean that in the following code: map m; B *b = &(m["something"]); The address in 'b' will remain valid, and always point to that same object, as long as that data isn't erased from the map Similarily: map m; map::iterator i(m.find("something")); B *b = (i == m.end()) NULL : &((*i).second); Will b there also always remain valid as long as "something" remains in the map
VIEWS ON THIS POST

101

Posted on:

Wednesday 7th November 2012
View Replies!

mutexes and const_iterators

I am using a map which holds a list of client connections (to a server). When a client connects a client gets added to the map and also when a client disconnects. In various parts of the code the map gets updated - the key is an int and the value is a class. As the map may be accessed by multiple threads I use a mutex to control access - ie locking whenever an item is added or removed. I have these questions: 1. Do I also need to lock if I just update and item I access the item via an iterator. 2. Do I need to lock if I simply access the map via a const_iterator Angus
VIEWS ON THIS POST

115

Posted on:

Wednesday 7th November 2012
View Replies!

std::list::splice invalidation of iterators

The C++ standard says in 23.2.2.4 "list operations" that the various forms of splice invalidate iterators and references to the spliced elements. This makes the splice operation a lot less useful than it otherwise could be. It seems unnecessary to invalidate these iterators and references, and I am puzzled why the standard says that it happens. Furthermore, the "merge" operation that also moves elements from one list to another does not have any note saying that it invalidates any iterators or references. Can anyone enlighten me -- "While the Melissa license is a bit unclear, Melissa aggressively encourages free distribution of its source code." --Kevin Dalley
VIEWS ON THIS POST

105

Posted on:

Wednesday 7th November 2012
View Replies!

[Defect Report] equal_range on unordered containers should returna pair of local_iterators.

A major attribute of the unordered containers is that iterating though them inside a bucket is very fast while iterating between buckets can be much slower. If an unordered container has a low load factor, iterating between the last iterator in one bucket and the next iterator, which is in another bucket, is O(bucket_count()) which may be much larger than O(size()). If b is an non-const unordered container of type B and k is an object of it's key_type, then b.equal_range(k) currently returns pair. Consider the following code: B::iterator lb, ub; tie(lb, ub) = b.equal_range(k); for (B::iterator it = lb; it != ub; ++it) { // Do something with *it } If b.equal_range(k) returns a non-empty range (i.e. b contains at least on element whose key is equivalent to k), then every iterator in the half-open range [lb, ub) will be in the same bucket, but ub will likely either be in a different bucket or be equal to b.end(). In either case, iterating between ub - 1 and ub could take a much longer time than iterating through the rest of the range. If instead of returning pair, equal_range were to return pair, then ub (which, like lb, would now be a local_iterator) could be guaranteed to always be in the same bucket as lb. In the cases where currently ub is equal to b.end() or is in a different bucket, ub would be equal to b.end(b.bucket(key)). This would make iterating between lb and ub much faster, as every iteration would be constant time. Suggested Resolution: Change the entry for equal_range in Table 93 as follows: Return type: pair; pair for const b. assertion/note pre/post-condition: Returns a range contained completely in one bucket containing all elements with keys equivalent to k. Returns make_pair(b.end(b.bucket(key)), b.end(b.bucket(key))) if no such elements exist. Joe Gottman --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
VIEWS ON THIS POST

128

Posted on:

Wednesday 7th November 2012
View Replies!

Understanding how to design STL-compatible iterators

Hi! I'm having some troubles trying to teach myself how to design my own iterator classes for use in STL algorithms. The concrete case is a self-written, rather primitive HTML parser class, which I want to be able to use like a real STL container, for example like this: HtmlParser parser("...code..."); typedef std::vector StringVector; typedef std::insert_iterator InsertIterator; StringVector tags; std::copy(parser.begin(), parser.end(), InsertIterator(tags, tags.begin())); The solution I've conceived works, but I don't completely understand why Behind the scenes, there's a self-written iterator class (which is also the return type of the parser's begin() and end() member functions), defined like this to make sure it supports all operations required by the STL algorithms: class HtmlParserIterator { public: HtmlTag const *operator->() const; HtmlTag operator*() const; bool operator==(HtmlParserIterator const &other) const; bool operator!=(HtmlParserIterator const &other) const; HtmlParserIterator &operator++(); HtmlParserIterator const operator++(int); HtmlParserIterator &operator=(HtmlParserIterator const &other); private: friend class HtmlParser; HtmlParserIterator(HtmlParser &parser, size_t current_pos); HtmlParser &parser_; size_t current_pos_; }; In the same header file, I also had to define some traits for my class using std::iterator_traits: template struct std::iterator_traits { typedef std::forward_iterator_tag iterator_category; typedef HtmlTag value_type; typedef size_t difference_type; typedef HtmlParserIterator * pointer; typedef HtmlParserIterator & reference; }; Here's my first question: What exactly does difference_type mean I think I understand the others, but this one I'm not sure about. The iterator has a size_t data member "current_pos_", which represents the parser's current position in the string being parsed, so size_t seemed a logical choice for difference_type. However, what is difference_type *used* for by the STL algorithms When do you need the "distance" between two iterators, anyway My second question is about std::iterator. From what I've gathered from online sources, you are supposed to derive your own iterator classes from std::iterator to make sure they work properly with std::iterator_traits. I've seen examples of iterator adapters using std::iterator like that. I, however, haven't used std::iterator at all and yet my class works like a charm. So what's the use of std::iterator As for a more a general questions, do you spot anything else in my sample code that can be considered dangerous or evil For example, defining HtmlParserIterator's constructor private so that only its friend class HtmlParser can construct new iterators Or keeping a reference to the parser class as a member of the iterator Is that OK
VIEWS ON THIS POST

155

Posted on:

Wednesday 7th November 2012
View Replies!

erase overload for reverse_iterators

For the STL containers that support reverse iterators, why aren't there overloads for erase() [or probably other functions that take a (forward) iterator] that take them as an argument Atleast for consistency in the interface When designing such classes is it considered that these overloads would make the class interface bulkier and probably redundant (going by the fact that generic algorithms can be written as non-member, non- friends) But then, what is the purpose of reverse iterators if functionalities like that are not supported on them Reverse iteration can surely be implemented in terms of forward iterators. Isn't it -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
VIEWS ON THIS POST

97

Posted on:

Wednesday 7th November 2012
View Replies!

iterators

I was reading about iterators and how they are used with containers provided by the STL. They seem like aliases for pointer types. Is this the case What's the benefit of doing it this way, if so I'm making a transition from C to C++. So far, I very much like the idea of the STL. Any insight appreciated. -- conrad
VIEWS ON THIS POST

103

Posted on:

Wednesday 7th November 2012
View Replies!

help understanding iterators with vector::insert

Hi , I am trying to get my head around iterators used on vectors. Let's take the code below: ------------- std::vector v1; std::vector v2; v1.push_back( 1 ); v1.push_back( 2 ); v1.push_back( 3 ); v2.push_back( 10 ); v2.push_back( 20 ); v2.push_back( 30 ); v1.insert(v1.end(), v2.begin(), v2.begin()); for(int j = 0; j < v1.size(); j++) std::cout
VIEWS ON THIS POST

114

Posted on:

Wednesday 7th November 2012
View Replies!

Incrementing temporary iterators

In general you can increment and decrement temporary iterators. However, for vectors and strings you typically can't but I'm not sure why. std::vector coll; .... if (coll.size() > 1) { sort(++coll.begin(), coll.end()); } Typically the compilation of sort above fails. The reason is vector iterators are implemented as ordinary pointers. Can someone explain why you are not allowed to modify temporary iterators
VIEWS ON THIS POST

93

Posted on:

Wednesday 7th November 2012
View Replies!

Is pushing into reserved space invalidating iterators?

Is the following code legal I'm asking since the iterator debugging facility of VC++2005's stl gives an assertion failed at runtime. #include int main(int argc, char** argv) { std::vector x; x.reserve(1); std::vector::iterator i = x.end(); x.push_back(1); // No reallocation if ( i != x.end()) // Debug Assertion failed: iterators incompatible return *i; // Debug Assertion failed: vector iterator not dereferencable } I had understood that iterators only become invalid when vector operations cause reallocation. Maarten Hilferink -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
VIEWS ON THIS POST

91

Posted on:

Saturday 10th November 2012
View Replies!

converting to cb2007 from b5: iterators are const?

It seems iterator are const in 2007 and not only const_iterator This worked in builder 5 #include #pragma hdrstop #include using namespace std; struct MyClass { int id; int data; MyClass() : id(0), data(0) {} MyClass(int _id) : ...
VIEWS ON THIS POST

163

Posted on:

Saturday 10th November 2012
View Replies!

std::distance for random access iterators and LWG issue #204

The latest draft of the C++0x standard describes the effects and requirements of std::distance as follows: "Effects: Returns the number of increments or decrements needed to get from first to last. Requires: last shall be reachable from first." In 2000 ...
VIEWS ON THIS POST

113

Posted on:

Saturday 10th November 2012
View Replies!

NIL pointers and invalid iterators

Hi all. I am playing with the idea to implement binary trees as lists, as outlined in Cormen & al, "Introduction to Algorithms", 2nd ed., chapter 10.3. The "obvious" way to do this is to use the std::vector container and ...
VIEWS ON THIS POST

98

Posted on:

Saturday 10th November 2012
View Replies!

getting vector iterators incompatible

Currently I am working in visual Studio 2008. Previously I was working in VS 2003 but I migrated the code VS2008. I am getting below error in VS 2008 which was NOT in vS2003. Error: _DEBUG_ERROR("vector iterators incompatible"); When ...
VIEWS ON THIS POST

103

Posted on:

Saturday 10th November 2012
View Replies!

template syntax for nested classes - custom iterators

I am trying to implement a generic tree class, as I had mentioned in a previous post. I want it to be STL like, so I went and researched how to implement an iterator and copied an example from a ...
VIEWS ON THIS POST

92

Posted on:

Sunday 11th November 2012
View Replies!

problem storing different iterators in a container

I'm trying to write a functor-class, which supports the de- multiplexing of data from one input-container to two or multiple output containers (de- interleaving). For example: vec1 = [1 5 2 6 3 7] #demultiplex vec1 -> result1,result2 ...
VIEWS ON THIS POST

167

Posted on:

Sunday 11th November 2012
View Replies!

Containers of iterators vs. containers of references

Relatively new to STL use. I coded up a bunch of container code with lots of iterators. Now I question whether I want to have so much nested iterator syntax. For example, if you are coding a compiler and you ...
VIEWS ON THIS POST

105

Posted on:

Sunday 11th November 2012
View Replies!

Query regarding iterators and vector

I am new STL programming. I have a query regarding vectors. If I am iterating over a vector using a iterator, but do some operations that modify the size of the vector. Will the iterator recognize this I wrote the ...
VIEWS ON THIS POST

106

Posted on:

Sunday 25th November 2012
View Replies!

Strange error with iterators

I've wrote this function which should add a comma for every 3 digits in a number (so that it looks something like 5,000). This is my function: std::string formatNumber(int number) { // Convert the int to a string. std::string ...
VIEWS ON THIS POST

306

Posted on:

Sunday 25th November 2012
View Replies!