Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualRyan_001

Posted 22 October 2012 - 08:13 PM

Both for my own uses and as an academic exercise I'm writing a hash container that stores memory like a vector. So its an open addressing/closed hashing container with linear probing stored in contiguous memory. I wanted to write it as if it were a proper stl container with all the bells and whistles, keeping it as similar as possible to unordered_set, and so I printed out chapter 23 of N3337 and went to town.

I've made good progress and I'm almost done (I think). But I've come across an issue. I have 2 options and each is a trade-off.

If I don't allow move constructors to throw (in the cases where a move constructor would throw the container would use a copy constructor instead, failing to compile if none existed), I can ensure that all operations are 'recoverable'. So an insert, erase, rehash, ect... that caused an exception, wouldn't lose any data in the container, and the container could be re-built back to a usable state. Not a true 'strong exception guarantee', but pretty close.

If I allow move constructors to throw, then I can't guarantee that move ops leave the container in a recoverable state if they throw. No resources would be leaked if a move failed (it'd still have a 'weak exception guarantee'), but there's no way to ensure the data that was there, prior to the function that was called that triggered the exception, is still there and is valid/recoverable.

Obviously this case isn't covered directly in the standard, but even what I've found in reference to vectors don't seem to be clear:

iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
template <class... Args> void emplace_back(Args&&... args);
template <class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_back(const T& x);
void push_back(T&& x);
1 Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens,
all the iterators and references before the insertion point remain valid. If an exception is thrown other
than by the copy constructor, move constructor, assignment operator, or move assignment operator
of T or by any InputIterator operation there are no effects
. If an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified.
2 Complexity: The complexity is linear in the number of elements inserted plus the distance to the end
of the vector.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
3 Effects: Invalidates iterators and references at or after the point of the erase.
4 Complexity: The destructor of T is called the number of times equal to the number of the elements
erased, but the move assignment operator of T is called the number of times equal to the number of
elements in the vector after the erased elements.
5 Throws: Nothing unless an exception is thrown by the copy constructor, move constructor, assignment
operator, or move assignment operator of T
.


I've bolded the parts that I'm unsure of. it doesn't seem to cover the situation where move or copy constructors/assignment operators do throw. There's also the general container requirements on page 705/706 (item 10, starts at bottom of page 705), specifically state that insert()/erase() (amongst other functions) have a strong exception guarantee. I'm not sure how this is possible in a vector if T's move constructor can throw. So at this point I'm guessing either it can't be done (strong exception guarantee on a vector) and I'm not sure where its stated in the standard as such, or it can be done and I just don't know how. They do state, "If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified." which seems to imply it can't be done, but given the sentence preceding it, I'm simply left more confused.

That said, if it can't be done, of the two options above I'm partial to the 1st. The option to recover data in the event of an exception seems pretty handy. On the other hand the requirement that move constructors not throw could make some types that are only movable (and not copyable) unusable in the container.

Any thoughts, comments, ideas are appreciated.

#3Ryan_001

Posted 22 October 2012 - 08:12 PM

Both for my own uses and as an academic exercise I'm writing a hash container that stores memory like a vector. So its an open addressing/closed hashing container with linear probing stored in contiguous memory. I wanted to write it as if it were a proper stl container with all the bells and whistles, keeping it as similar as possible to unordered_set, and so I printed out chapter 23 of N3337 and went to town.

I've made good progress and I'm almost done (I think). But I've come across an issue. I have 2 options and each is a trade-off.

If I don't allow move constructors to throw (in the cases where a move constructor would throw the container would use a copy constructor instead, failing to compile if none existed), I can ensure that all operations are 'recoverable'. So an insert, erase, rehash, ect... that caused an exception, wouldn't lose any data in the container, and the container could be re-built back to a usable state. Not a true 'strong exception guarantee', but pretty close.

If I allow move constructors to throw, then I can't guarantee that move ops leave the container in a recoverable state if they throw. No resources would be leaked if a move failed (it'd still have a 'weak exception guarantee'), but there's no way to ensure the data that was there, prior to the function that was called that triggered the exception, is still there and is valid/recoverable.

Obviously this case isn't covered directly in the standard, but even what I've found in reference to vectors don't seem to be clear:

iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
template <class... Args> void emplace_back(Args&&... args);
template <class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_back(const T& x);
void push_back(T&& x);
1 Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens,
all the iterators and references before the insertion point remain valid. If an exception is thrown other
than by the copy constructor, move constructor, assignment operator, or move assignment operator
of T or by any InputIterator operation there are no effects
. If an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified.
2 Complexity: The complexity is linear in the number of elements inserted plus the distance to the end
of the vector.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
3 Effects: Invalidates iterators and references at or after the point of the erase.
4 Complexity: The destructor of T is called the number of times equal to the number of the elements
erased, but the move assignment operator of T is called the number of times equal to the number of
elements in the vector after the erased elements.
5 Throws: Nothing unless an exception is thrown by the copy constructor, move constructor, assignment
operator, or move assignment operator of T
.


I've bolded the parts that I'm unsure of. it doesn't seem to cover the situation where move or copy constructors/assignment operators do throw. There's also the general container requirements on page 705/706 (item 10, starts at bottom of page 705), specifically state that insert()/erase() (amongst other functions) have a strong exception guarantee. I'm not sure how this is possible in a vector if T's move constructor can throw. So at this point I'm guessing either it can't be done (strong exception guarantee on a vector) and I'm not sure where its stated in the standard as such, or it can be done and I just don't know how. They do state, "If an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified." which seems to imply it can't be done, but given the sentence preceding it, I'm simply left more confused.

That said, if it can't be done, of the two options above I'm partial to the 1st. The option to recover data in the event of an exception seems pretty handy. On the other hand the requirement that move constructors not throw could make some types that are only movable (and not copyable) unusable in the container.

Any thoughts, comments, ideas are appreciated.

#2Ryan_001

Posted 22 October 2012 - 08:12 PM

Both for my own uses and as an academic exercise I'm writing a hash container that stores memory like a vector. So its an open addressing/closed hashing container with linear probing stored in contiguous memory. I wanted to write it as if it were a proper stl container with all the bells and whistles, keeping it as similar as possible to unordered_set, and so I printed out chapter 23 of N3337 and went to town.

I've made good progress and I'm almost done (I think). But I've come across an issue. I have 2 options and each is a trade-off.

If I don't allow move constructors to throw (in the cases where a move constructor would throw the container would use a copy constructor instead, failing to compile if none existed), I can ensure that all operations are 'recoverable'. So an insert, erase, rehash, ect... that caused an exception, wouldn't lose any data in the container, and the container could be re-built back to a usable state. Not a true 'strong exception guarantee', but pretty close.

If I allow move constructors to throw, then I can't guarantee that move ops leave the container in a recoverable state if they throw. No resources would be leaked if a move failed (it'd still have a 'weak exception guarantee'), but there's no way to ensure the data that was there, prior to the function that was called that triggered the exception, is still there and is valid/recoverable.

Obviously this case isn't covered directly in the standard, but even what I've found in reference to vectors don't seem to be clear:

iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
template <class... Args> void emplace_back(Args&&... args);
template <class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_back(const T& x);
void push_back(T&& x);
1 Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens,
all the iterators and references before the insertion point remain valid. If an exception is thrown other
than by the copy constructor, move constructor, assignment operator, or move assignment operator
of T or by any InputIterator operation there are no effects
. If an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified.
2 Complexity: The complexity is linear in the number of elements inserted plus the distance to the end
of the vector.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
3 Effects: Invalidates iterators and references at or after the point of the erase.
4 Complexity: The destructor of T is called the number of times equal to the number of the elements
erased, but the move assignment operator of T is called the number of times equal to the number of
elements in the vector after the erased elements.
5 Throws: Nothing unless an exception is thrown by the copy constructor, move constructor, assignment
operator, or move assignment operator of T
.


I've bolded the parts that I'm unsure of. it doesn't seem to cover the situation where move or copy constructors/assignment operators do throw. There's also the general container requirements on page 705/706 (item 10, starts at bottom of page 705), the specifically state that insert()/erase() (amongst other functions) have a strong exception guarantee. I'm not sure how this is possible in a vector if T's move constructor can throw. So at this point I'm guessing either it can't be done (strong exception guarantee on a vector) and I'm not sure where its stated in the standard as such, or it can be done and I just don't know how. They do state, "If an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified." which seems to imply it can't be done, but given the sentence preceding it, I'm simply left more confused.

That said, if it can't be done, of the two options above I'm partial to the 1st. The option to recover data in the event of an exception seems pretty handy. On the other hand the requirement that move constructors not throw could make some types that are only movable (and not copyable) unusable in the container.

Any thoughts, comments, ideas are appreciated.

#1Ryan_001

Posted 22 October 2012 - 08:07 PM

Both for my own uses and as an academic exercise I'm writing a hash container that stores memory like a vector. So its an open addressing/closed hashing container with linear probing stored in contiguous memory. I wanted to write it as if it were a proper stl container with all the bells and whistles, keeping it as similar as possible to unordered_set, and so I printed out chapter 23 of N3337 and went to town.

I've made good progress and I'm almost done (I think). But I've come across an issue. I have 2 options and each is a trade-off.

If I don't allow move constructors to throw (in the cases where a move constructor would throw the container would use a copy constructor instead, failing to compile if none existed), I can ensure that all operations are 'recoverable'. So an insert, erase, rehash, ect... that caused an exception, wouldn't lose any data in the container, and the container could be re-built back to a usable state. Not a true 'strong exception guarantee', but pretty close.

If I allow move constructors to throw, then I can't guarantee that move ops leave the container in a recoverable state if they throw. No resources would be leaked if a move failed (it'd still have a 'weak exception guarantee'), but there's no way to ensure the data that was there, prior to the function that was called that triggered the exception, is still there and is valid/recoverable.

Obviously this case isn't covered directly in the standard, but even what I've found in reference to vectors don't seem to be clear:

iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
template <class... Args> void emplace_back(Args&&... args);
template <class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_back(const T& x);
void push_back(T&& x);
1 Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens,
all the iterators and references before the insertion point remain valid. If an exception is thrown other
than by the copy constructor, move constructor, assignment operator, or move assignment operator
of T or by any InputIterator operation there are no effects
. If an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified.
2 Complexity: The complexity is linear in the number of elements inserted plus the distance to the end
of the vector.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
3 Effects: Invalidates iterators and references at or after the point of the erase.
4 Complexity: The destructor of T is called the number of times equal to the number of the elements
erased, but the move assignment operator of T is called the number of times equal to the number of
elements in the vector after the erased elements.
5 Throws: Nothing unless an exception is thrown by the copy constructor, move constructor, assignment
operator, or move assignment operator of T
.


I've bolded the parts that I'm unsure of. it doesn't seem to cover the situation where move or copy constructors/assignment operators do throw. There's also the general container requirements on page 705/760 (item 10, starts at bottom of page 705), the specifically state that insert()/erase() (amongst other functions) have a strong exception guarantee. I'm not sure how this is possible in a vector if T's move constructor can throw. So at this point I'm guessing either it can't be done (strong exception guarantee on a vector) and I'm not sure where its stated in the standard as such, or it can be done and I just don't know how. They do state, "If an exception is thrown by the move
constructor of a non-CopyInsertable T, the effects are unspecified." which seems to imply it can't be done, but given the sentence preceding it, I'm simply left more confused.

That said, if it can't be done, of the two options above I'm partial to the 1st. The option to recover data in the event of an exception seems pretty handy. On the other hand the requirement that move constructors not throw could make some types that are only movable (and not copyable) unusable in the container.

Any thoughts, comments, ideas are appreciated.

PARTNERS