15

Specifically, I have a class which currently uses a vector and push_back. There is an element inside the vector I want to keep track of. Pushing back on the vector may invalidate the iterator, so I keep its index around. It's cheap to find the iterator again using the index. I can't reserve the vector as I don't know how many items will be inserted.

I've considered making the data structure a template parameter, and perhaps list may be used instead. In that case, finding an iterator from the index is not a trivial operation. Since pushing back on a list doesn't invalidate iterators to existing elements, I could just store this iterator instead.

But how can I code a generic class which handles both cases easily?

If I can find out whether push_back will invalidate the iterator, I could store the iterator and update it after each push_back by storing the distance from the beginning before the operation.

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
  • 2
    Very nice question. I can't think of a way to do it reliably. You could use a heuristic of "is the container's iterator random-access or not?", but that's certainly not fool-proof. It would hold for all current `std` containers, though, I believe. – Angew is no longer proud of SO Sep 16 '13 at 11:39
  • If you need to store pointer to speicfic elements in container, wouldnt it be better to change container to one that supports it? for example list. - iterators are not invalidated after pushing back. – Aleksander Fular Sep 16 '13 at 11:41
  • @AleksanderFular I used vector initially as I wanted to decrease the number of memory allocations over time. It will be filled and cleared regularly. – Neil Kirk Sep 16 '13 at 11:43

3 Answers3

4

You should probably try to avoid this flexibility. Quote from Item 2 "Beware the illusion of container-independent code" from Effective STL by Scott Meyers:

Face the truth: it's not worth it. The different containers are different, and they have strengths and weaknesses that vary in significant ways. They're not designed to be interchangeable, and there's littel you can do to paper that over. If you try, you're merely tempting fate, and fate doesn't like to be tempted.

If you really, positively, definitely have to maintain valid iterators, use std::list. If you also need to have random access, try Boost.MultiIndex (although you'll lose contiguous memory access).

If you look at the standard container adapators (std::stack, std::queue) you see that they support the intersection of the adaptable containers interfaces, not their union.

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • 1
    Template specialization isn't really container independent though; It's exposing a concept taking into consideration each type. Don't get me wrong, I agree with the advice but this seems to be what specialization was designed to solve. – Andrew White Sep 16 '13 at 11:49
  • @AndrewWhite for things like iterators I would agree. You can specialize and expect algorithms to take advantage of that. But the standard container adapters support interface intersections, not unions, of the underlying containers. – TemplateRex Sep 16 '13 at 11:56
2

I'd create a second class, which responsibility would be to return the iterator you are interested in. It should also be parametrized with the same template parameter, and then you can specialize it for any type you want (vector/list etc). So inside your specializations you can use any method you want.

So it's some traits-based solution.

roalz
  • 2,699
  • 3
  • 25
  • 42
Michał Walenciak
  • 4,257
  • 4
  • 33
  • 61
1

If you really want to stick with the vector and have that functionality maybe take a look at
http://en.cppreference.com/w/cpp/container/vector/capacity function. wrap your push_backs in defined function or even better wrap whole std::vector in ur class and before push_backing compare capacity against size() to check if resize will happen.

Aleksander Fular
  • 803
  • 9
  • 18