• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Ryan_001

hash container

8 posts in this topic

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:
[quote]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. [b]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[/b]. 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 [b]Throws: Nothing unless an exception is thrown by the copy constructor, move constructor, assignment
operator, or move assignment operator of T[/b].[/quote]

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
0

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
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:
[CODE]typedef typename allocator_type::value_type value_type;[/CODE]
of perhaps something like:
[CODE]typedef typename allocator_traits<allocator_type>::value_type value_type;[/CODE]
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
0

Share this post


Link to post
Share on other sites
[quote name='Ryan_001' timestamp='1351186997' post='4993869']
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?[/quote]
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.
1

Share this post


Link to post
Share on other sites
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:
[CODE]typedef typename allocator_type::value_type value_type;[/CODE]
or
[CODE]typedef T value_type;[/CODE]
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0