Jump to content

  • Log In with Google      Sign In   
  • Create Account


hash container


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 Ryan_001   Prime Members   -  Reputation: 1343

Like
0Likes
Like

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/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.

Edited by Ryan_001, 22 October 2012 - 08:13 PM.


Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9554

Like
1Likes
Like

Posted 22 October 2012 - 08:20 PM

An example of an exception that might be thrown that's not due to one of the T's constructors or assignment operators is std::bad_alloc. If the vector can't allocate room to grow then you've got the strong guarantee. This is the kind of thing that the first bolded section is referring to. If your move constructor can throw then you're basically screwed when it comes to writing exception safe code, so don't do that and don't worry about your clients doing that.

#3 Ryan_001   Prime Members   -  Reputation: 1343

Like
0Likes
Like

Posted 22 October 2012 - 09:04 PM

Ahh ok thanks.

#4 Ryan_001   Prime Members   -  Reputation: 1343

Like
0Likes
Like

Posted 25 October 2012 - 11:43 AM

Another quick question. Any time I've seen the typedefs of a container listed (value_type, key_type, ect...) online they've always been defined in terms of the allocator like:
typedef typename allocator_type::value_type value_type;
of perhaps something like:
typedef typename allocator_traits<allocator_type>::value_type value_type;
I always assumed this was to allow proxy types to be used instead of T or perhaps allow other things to go on under the hood. Yet in the standard (in particular N3337 on p703) the container requirements seem to straight up state that value_type (along with reference_type, pointer_type, ect...) is just T. No mess, fuss, or anything. Is this the way its always been or is this something in the newer standard revisions? Or am I reading this incorrectly? Similarly with size_type, difference_type, do I need to define these in terms of the allocator size_type and allocator difference_type, or can I simply set them to size_t and ptrdiff_t?

Edited by Ryan_001, 25 October 2012 - 11:50 AM.


#5 SiCrane   Moderators   -  Reputation: 9554

Like
1Likes
Like

Posted 25 October 2012 - 03:40 PM

Yet in the standard (in particular N3337 on p703) the container requirements seem to straight up state that value_type (along with reference_type, pointer_type, ect...) is just T. No mess, fuss, or anything. Is this the way its always been or is this something in the newer standard revisions? Or am I reading this incorrectly?

You're reading it incorrectly. pointer_type isn't even on that table. value_type needs to be T, but allocators are also required to have value_type be T. reference_type is not specified as T, but "lvalue of T" without saying how it should form an lvalue. In fact, implementing reference_type as just T would be a violation of the standard since it isn't an lvalue in all contexts.

#6 Ryan_001   Prime Members   -  Reputation: 1343

Like
0Likes
Like

Posted 25 October 2012 - 08:10 PM

Sorry was unclear due to being a bit too terse. I understand that reference_type would need to be T& and not T. What I was wondering if containers were required to forward the allocator defined types, or if the containers should define their own. For example, which would be preferred:
typedef typename allocator_type::value_type value_type;
or
typedef T value_type;
The reason I was asking was that while the standard seemed to say that the latter was valid, I regularly see online references use the former. I was wondering if there was some discrepancy I was unaware of.

That was all, thanks.

#7 SiCrane   Moderators   -  Reputation: 9554

Like
0Likes
Like

Posted 26 October 2012 - 10:50 AM

value_type is required to be T for both the container and the allocator, so it doesn't matter if you forward it or not. The other typedefs are a little more complicated. In standard C++, there's only one way to form a pointer to a (non-const, non-volatile) T, T *. However, there are platforms that have more difficult to deal with memory models. For example, rather than a flat memory model like modern PC OSs use, MS-DOS used segment:offset pointers, with compilers generally having three kinds of pointers: T * __near, T * __far and T * __huge. This change propagates to other types that relate to memory addresses. While I've never had the misfortune of using one, there are modern embedded processor systems that also have this kind of pointer usage.

In any case, it's possible to assign a near pointer to a far pointer, but not vice versa, and which pointer a T * meant depended on what memory model the program was compiled to. So if your container used regular T * pointers when compiled with in a memory model where T * was actually near pointers, but the allocator was returning far pointers, you'd have all sorts of unhappy compiler error getting pointers from the allocator. Similarly, if compiled in a mode where T * pointers were far, but the allocator used near pointers, you'd have all sorts of unhappy compiler errors passing pointers to the allocator.

That's the basic case for why you would want to use the allocator typedefs. It's (hopefully) not really a scenario that is likely to come up, but supporting it really takes almost no effort on your part when you can use the allocator typedefs.

#8 Ryan_001   Prime Members   -  Reputation: 1343

Like
0Likes
Like

Posted 26 October 2012 - 07:21 PM

Now do I forward Allocator types or allocator_traits<Allocator> types? Is there any difference or are those defined to be the same thing?

#9 SiCrane   Moderators   -  Reputation: 9554

Like
0Likes
Like

Posted 27 October 2012 - 09:04 AM

Allocators are not required to define all the typedefs. If they don't define the optional typedefs you can assume the defaults in the allocator requirements table. std::allocator_traits will perform the logic for checking and substituting the defaults for you, so using std::allocator_traits is easier.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS