Solved

STL Container that won't invalidate pointers when altered

Posted on 2003-12-09
21
864 Views
Last Modified: 2013-12-14
You create a vector of 10 integers, create a pointer to integer 5 and then remove the 4th integer and suddenly your pointer will be pointing at the value which used to be 6 but is now 5. Not what I want.

std::vector<int> foo;

for(int i=0; i < 10; i++)
       foo.push_back(i);

int * bar = &(foo[5]);
std::cout << bar;
foo.remove(4);
std::cout << " " << bar;

I think STL List won't cause this trouble because it is a linked list?
0
Comment
Question by:Sandra-24
  • 6
  • 5
  • 4
  • +3
21 Comments
 
LVL 17

Expert Comment

by:rstaveley
Comment Utility
Correct.... up to a point. When you use list.remove, iterators to elements that are not removed remain valid, according to the SGI STL documentation (see http://www.sgi.com/tech/stl/List.html), and this seems to be true in Microsoft and GNU implementations. I notice, however, that the same guarantee doesn't appear in the INCITS ISO/IEC 14882:1998 standard (22.2.2.4.15), which I've only just got around to paying my $18 for... and am therefore still getting to grips with... and therefore can't be trusted to quote dependably from :-)
0
 
LVL 48

Assisted Solution

by:AlexFM
AlexFM earned 50 total points
Comment Utility
>> I think STL List won't cause this trouble because it is a linked list?

Possibly you are right, but I don't suggest to keep pointer to any STL container member by such way. You make assumption about internal implementation of STL container, and it may be wrong in various STL versions and implementations.
Every time you need STL container member you should access this member using STL functions. Any change in STL container may invalidate pointer to it's member.

0
 
LVL 17

Expert Comment

by:rstaveley
Comment Utility
.... You could splice the unwanted element into a junk list and other iterators should remain valid. Be warned that you would need to retain an iterator rather than a pointer, though.
0
 
LVL 12

Accepted Solution

by:
andrewjb earned 300 total points
Comment Utility
... or use some form of smart pointer or pointer wrapper class and store that in the list instead.
0
 
LVL 86

Expert Comment

by:jkr
Comment Utility
>>Not what I want.

If you have a pointer to an entry in a STL container and remove that entry from the container, all assumptions about where the pointer points to are moot anyway. It simply is invalid. That it happens to point to another vector element is just a coincidence. What would be the effect that you desired?
0
 
LVL 12

Expert Comment

by:andrewjb
Comment Utility
No - he's removing one of the other elements, and retaining a pointer to one that has not been deleted. But containers (other than list) screw up their iterators, so that's not allowed.
0
 
LVL 17

Expert Comment

by:rstaveley
Comment Utility
> But containers (other than list) screw up their iterators, so that's not allowed.

From what I can make out from the standard, there is no guaratee that list.remove won't screw up iterators. That's why I suggested splicing the element to a junk container, because splicing does have the guarantee.
0
 
LVL 12

Expert Comment

by:andrewjb
Comment Utility
Indeed - or a smart pointer of some form.
Though, I don't know where I've read, but I thought that the list _did_ guarantee that iterators (except for the removed one) were OK.

It depends really how you want to use it. If you're only using 1 compiler, and it guarantees, then you're OK.

Does the STL implementation guarantee they're ok?
0
 
LVL 12

Expert Comment

by:andrewjb
Comment Utility
We could do with Sandra's feedback, to see whether any of this has been useful!
0
 
LVL 17

Expert Comment

by:rstaveley
Comment Utility
This is obviously wrong looking vector code, which on VC7.1 and GCC3.2 gets "peas", where you might unthinkingly have expected to get "chips":
--------8<--------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
      std::vector<std::string> v;
      v.push_back("ham");
      v.push_back("eggs");
      v.push_back("chips");
      v.push_back("peas");

      // Get a reference to chips in the vector
      std::vector<std::string>::iterator i1 = find(v.begin(),v.end(),"chips");

      // Remove the reference to eggs in the list
      std::vector<std::string>::iterator i2 = find(v.begin(),v.end(),"eggs");
      std::vector<std::string>::iterator end = remove(v.begin(),v.end(),*i2);
      v.erase(end,end+1);

      // Use the reference to chips previously found in the list
      std::cout << *i1 << '\n';
}
--------8<--------

This list code works on VC7.1 and GCC3.2, with the iterator to "chips" continuing to get "chips", but I do not believe that it is guaranteed to work per the standard:
--------8<--------
#include <iostream>
#include <list>
#include <string>
#include <algorithm>

int main()
{
      std::list<std::string> l;
      l.push_back("ham");
      l.push_back("eggs");
      l.push_back("chips");
      l.push_back("peas");

      // Get a reference to chips in the list
      std::list<std::string>::iterator i1 = find(l.begin(),l.end(),"chips");

      // Remove the reference to eggs in the list
      std::list<std::string>::iterator i2 = find(l.begin(),l.end(),"eggs");
      l.remove(*i2);

      // Use the reference to chips previously found in the list
      std::cout << *i1 << '\n';
}
--------8<--------

I *think* you need to do the following, if you are to be standards-compliant, and retain an interator:
--------8<--------
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
#include <iterator>

int main()
{
        std::list<std::string> l;
        l.push_back("ham");
        l.push_back("eggs");
        l.push_back("chips");
        l.push_back("peas");

        // Get a reference to chips in the list
        std::list<std::string>::iterator i1 = find(l.begin(),l.end(),"chips");

        // Put the reference to eggs into another list using splicing
        std::list<std::string>::iterator i2 = find(l.begin(),l.end(),"eggs");
        std::list<std::string> junk;
        junk.splice(junk.begin(),l,i2);

        // Use the reference to chips previously found in the list
        std::cout << *i1 << '\n';

        std::cout << "\njunk contains: ";
        copy(junk.begin(),junk.end(),std::ostream_iterator<std::string>(std::cout," "));
        std::cout << "\nl contains: ";
        copy(l.begin(),l.end(),std::ostream_iterator<std::string>(std::cout," "));
        std::cout << std::endl;
}
--------8<--------
0
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 19

Expert Comment

by:Dexstar
Comment Utility
@Sandra-24:

> I think STL List won't cause this trouble because it is a linked list?

Right.  list<> and map<> and a few others will not invalidate iterators unless the element is removed.  vector<> can invalidate iterators whenever the vector<> is resized and moved to a new location in memory.

Hope That Helps,
Dex*
0
 
LVL 3

Author Comment

by:Sandra-24
Comment Utility
"We could do with Sandra's feedback, to see whether any of this has been useful!"

Sorry, I'm on the west coast, I just woke up now.

"... or use some form of smart pointer or pointer wrapper class and store that in the list instead. "

Actually that makes me wonder why I didn't think of this in the first place. Why not store only pointers in the vector? Using my previous example:

std::vector<int> foo;

int * temp;
for(int i=0; i < 10; i++)
{
       temp = new int;
       *temp = i;
       foo.push_back(temp);
}

int * bar = foo[5];
std::cout << bar;
foo.remove(4);
std::cout << " " << bar;

That should do the trick. I just need to remember to delete it in the destructor, and add a copy constructor and assignment operator.

That's the simplest solution I think, and simple is good in programming:)

Thanks for all your input guys.
-Sandra
0
 
LVL 19

Expert Comment

by:Dexstar
Comment Utility
If you're going to do that, I would derive a class from vector<> that automatically does all the clean up for you, otherwise you'll leak memory if you forget to delete the objects in the vector<> (or somehow are not able to do it because of an exception, or whatever).

Dex*
0
 
LVL 48

Expert Comment

by:AlexFM
Comment Utility
Keeping the pointers in STL containers is useful also for structs and classes.
0
 
LVL 19

Assisted Solution

by:Dexstar
Dexstar earned 150 total points
Comment Utility
Also remember, you can't use std::auto_ptr<> with the STL container classes.  However, I think the Boost library has a smart pointer class that you can use.  Then you wouldn't have to manually delete everything for clean up.  It would all be automagic!

D*
0
 
LVL 12

Expert Comment

by:andrewjb
Comment Utility
"Sorry, I'm on the west coast, I just woke up now."
Ooops - keep forgetting about things like that :-)

"I would derive a class from vector<> ....."
Or, possibly more generically, find a smart pointer template class that'll do it for you. (i.e. alter the pointer, not the container). But either would do.


0
 
LVL 19

Assisted Solution

by:Dexstar
Dexstar earned 150 total points
Comment Utility
@andrewjb:  Yeah, exactly.  You could do it like this if you used the smart pointer class found here http://www.boost.org/libs/smart_ptr/shared_ptr.htm:

     template<typename T, typename A= std:allocator<boost::shared_ptr<T> > >
     class AutoVector<T, A> : public std::list<boost::shared_ptr<T>, A>
     {
     };

(I haven't tried to compile that, so it may need some tweaking, but you get the general idea...)

D*
0
 
LVL 3

Author Comment

by:Sandra-24
Comment Utility
I didn't realize such things as smart pointers exist. I should go back and use that inplace of normal pointers whever I can in my code. It will really cut down on leaks.

Always something new to learn it seems:)

Dexstar, according to the gurus on here deriving from STL classes is a bad idea. Something to do with the destructors not being virtual. I don't fully understand why, but they did manage to convince me that it's better to contain an STL class than derive from it.

Thanks,
-Sandra
0
 
LVL 19

Expert Comment

by:Dexstar
Comment Utility
@Sandra:  Whoever told you not to derive from STL classes did you a grave disservice.  You should wipe that idea out of your head.

The fact that the destructors are not virtual doesn't mean ANYTHING unless you are dynamically allocating instances of your class (e.g., using new and delete to create them).  If you are just declaring them on the stack, then it doesn't make any difference at all.

You could implement this by containing an STL class, but it is 10x more work, and won't make any practical difference.

Peace,
D*
0
 
LVL 3

Author Comment

by:Sandra-24
Comment Utility
And what happens if you or another programmer using your class forgets that? Then you have a leak.

I can see a logic in both ways of doing things though. Perhaps if you called the STL container's destructor from within your own destructor it would solve this problem? I'm not certain.
0
 
LVL 19

Expert Comment

by:Dexstar
Comment Utility
@Sandra-24 : That's right.  You should keep both options under your belt.  Sometimes you'll need one thing, and other times, you'll need another.

I'm pretty sure explicitly calling the destructor will fix it, yes...  Oh, in your derived class, you can make the destructor virtual... That will take care of it also.

Dex*
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now