[ptr_container] How to shift part of a ptr_vector ?
Dear Experts, I have some code which currently uses a std::vector of pointers, and I'm investigating whether I can make it more concise, exception-safe, or otherwise better using a ptr_vector. But I can't see a good way to replace the following code, which shifts part of the vector by one place, deleting one pointee and creating a new one at the other end: struct LargeThing { .... }; std::vector<LargeThing*> v; void shift(int start, int end) { delete v[start]; for (int i=start; i<end; ++i) { // or use a std::algorithm v[i]=v[i+1]; } v[end] = new LargeThing; } With a ptr_vector, I think that I could do something like struct LargeThing { .... }; boost::ptr_vector<LargeThing> v; void shift(int start, int end) { v.release(v.begin()+start); // or should that be erase() ? v.insert(v.begin()+end-1, new LargeThing); } But this has complexity O(v.length()), because v.release() has to move all elements beyond start, while my current code has complexity O(end-start), because it doesn't touch the elements beyond end. Is there some better way to accomplish this? Maybe transfer() can be used? Or something involving swap()? Thanks for any suggestions. Phil.
Phil: Pardon my ignorance about ptr_vector, but you may be thinking about the wrong STL algorithm: try rotate instead of copy: void shift(int start, int end) { std::rotate(start, start+1, end+1); // brings v[start] to v[end] and shifts everyone else by one position down LargeThing *tmp = v[end]; pop_back(); // vector is now in a stable state, if delete throws (gasp! hope not!) or if new throws, it only contains valid pointers delete tmp; v.push_back(new LargeThing); } Assuming constructor does not throw, your vector will have one less element in the presence of exception thrown by the ctor, and otherwise the extra cost is simply decrementing and re-incrementing the vector size member, no big deal compared to a LargeThing ctor. Small note about the interface: I would have made end be one-past- the-position, in STL fashion. HTH, --HB On Dec 29, 2007, at 10:38 AM, Phil Endecott wrote:
Dear Experts,
I have some code which currently uses a std::vector of pointers, and I'm investigating whether I can make it more concise, exception-safe, or otherwise better using a ptr_vector. But I can't see a good way to replace the following code, which shifts part of the vector by one place, deleting one pointee and creating a new one at the other end:
struct LargeThing { .... }; std::vector<LargeThing*> v;
void shift(int start, int end) { delete v[start]; for (int i=start; i<end; ++i) { // or use a std::algorithm v[i]=v[i+1]; } v[end] = new LargeThing; }
Herve Bronnimann wrote:
Phil: Pardon my ignorance about ptr_vector, but you may be thinking about the wrong STL algorithm: try rotate instead of copy:
Yes, rotate would do something similar to the for loop in my example. The point is that ptr_containers can't use mutating std::algorithms; instead, they provide their own implementations of some of them as members. rotate isn't one of them, so I need some other way of doing it. Phil.
Phil Endecott skrev:
Herve Bronnimann wrote:
Phil: Pardon my ignorance about ptr_vector, but you may be thinking about the wrong STL algorithm: try rotate instead of copy:
Yes, rotate would do something similar to the for loop in my example.
The point is that ptr_containers can't use mutating std::algorithms; instead, they provide their own implementations of some of them as members. rotate isn't one of them, so I need some other way of doing it.
You can access mutating iterators over the original containers by calling .base() no the iterators. They are hen iterators over void*&, so you need to cast or use e.g. void_ptr_indirect_fun: http://www.boost.org/libs/ptr_container/doc/indirect_fun.html -Thorsten
Thorsten Ottosen wrote:
Phil Endecott skrev:
Herve Bronnimann wrote:
Phil: Pardon my ignorance about ptr_vector, but you may be thinking about the wrong STL algorithm: try rotate instead of copy:
Yes, rotate would do something similar to the for loop in my example.
The point is that ptr_containers can't use mutating std::algorithms; instead, they provide their own implementations of some of them as members. rotate isn't one of them, so I need some other way of doing it.
You can access mutating iterators over the original containers by calling .base() no the iterators.
They are hen iterators over void*&, so you need to cast or use e.g. void_ptr_indirect_fun:
http://www.boost.org/libs/ptr_container/doc/indirect_fun.html
Thanks Thorsten. But I fear that's a worse solution for me, in terms of e.g. readability and lines of code, than simply using a std::container of pointers. What's ideally needed is for the missing std::algorithms to be added to the ptr_containers, but that could be quite a lot of work. I think that just a swap function would be sufficient for my current needs: void ptr_vector::swap(size_type a, size_type b); Thinking aloud: this is the first time that I've tried to use Boost.ptr_containers; the last time that I wanted something like this I didn't need the ownership that ptr_containers provides, but only the hidden pointer dereferencing. I ended up writing something of my own [*]. At the time I wondered if ptr_containers could have been factored into two independent units, i.e. the ownership feature, so that ~container deletes the pointees, and the hidden dereferencing, so that vec[n] is a T& not a T*. I now wonder whether the layering of the ptr_container over the std::container<pointer> could be explicit, so that the user can get at the underlying container-of-pointers when they want to. E.g.: std::vector<LargeThing*> vec_ptrs; ptr_vector_adaptor<LargeThing> vec_largethings(vec_ptrs); // ctor takes a reference // I can now use vec_largethings for read access; if I want to manipulate the // underlying pointers I can use vec_ptrs directly. [*] The code that I wrote was a "const string facade", i.e. a class that has the same interface as a const string but which doesn't own its data; instead, the constructor takes pointers to the start and end of the data. I use this with files that are read in in their entirety or mmap()ed; with e.g. a CSV or XML file you can quite efficiently build a std::map<string,string>-like data structure, without ever copying the data. If anyone is interested in this code, I could probably share it. Regards, Phil.
Phil Endecott skrev:
Thorsten Ottosen wrote:
Phil Endecott skrev:
Herve Bronnimann wrote:
Phil: Pardon my ignorance about ptr_vector, but you may be thinking about the wrong STL algorithm: try rotate instead of copy: Yes, rotate would do something similar to the for loop in my example.
The point is that ptr_containers can't use mutating std::algorithms; instead, they provide their own implementations of some of them as members. rotate isn't one of them, so I need some other way of doing it. You can access mutating iterators over the original containers by calling .base() no the iterators.
They are hen iterators over void*&, so you need to cast or use e.g. void_ptr_indirect_fun:
http://www.boost.org/libs/ptr_container/doc/indirect_fun.html
Thanks Thorsten. But I fear that's a worse solution for me, in terms of e.g. readability and lines of code, than simply using a std::container of pointers. What's ideally needed is for the missing std::algorithms to be added to the ptr_containers, but that could be quite a lot of work.
I'm definitely not going down that path. The addition of the algorithms is partly a sign that the containers are overencapsulated, and partly a sign that some algorithms are harder because of the potential presense of nulls.
I think that just a swap function would be sufficient for my current needs:
void ptr_vector::swap(size_type a, size_type b);
Thinking aloud: this is the first time that I've tried to use Boost.ptr_containers; the last time that I wanted something like this I didn't need the ownership that ptr_containers provides, but only the hidden pointer dereferencing. I ended up writing something of my own [*]. At the time I wondered if ptr_containers could have been factored into two independent units, i.e. the ownership feature, so that ~container deletes the pointees, and the hidden dereferencing, so that vec[n] is a T& not a T*.
You can avoid overship with a view_clone_allocator. http://www.boost.org/libs/ptr_container/doc/reference.html#class-view-clone-... I guess another contender for that could be vector<boost::reference_wrapper<T>>, albeit a bit inconvenient without operator.() overloading in the language.
I now wonder whether the layering of the ptr_container over the std::container<pointer> could be explicit, so that the user can get at the underlying container-of-pointers when they want to. E.g.:
std::vector<LargeThing*> vec_ptrs; ptr_vector_adaptor<LargeThing> vec_largethings(vec_ptrs); // ctor takes a reference // I can now use vec_largethings for read access; if I want to manipulate the // underlying pointers I can use vec_ptrs directly.
1.35 introduces a .base() member function in pointer containers s.t. you can access the underlying container directly. I expect to move away from the void* based implementation to allow better integration with algorithms, as you and others would like. -Thorsten
participants (3)
-
Hervé Brönnimann -
Phil Endecott -
Thorsten Ottosen