Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[DragonDePlatino]

Vectors aren't as cache-friendly as C-style arrays, yes, but it feels like needless pre-optimization to worry about that for small problems...No use in reinventing the wheel when you could be using safer (and more standardized) ways of approaching problems. It's obnoxious to walk through someone's code and try to understand it after they've reimplemented features from the standard library.

vector<vector<...>> isn't too great, yeah. Back when I was using C++ I used 1D vectors indexed like 2D vectors.

[Reelya]

Idk, i use very small wrappers for c-style arrays and have no problems, they only work out at a few lines of code, most of which is boilerplate that's always the same. It would most certainly be dumb to use STL to code a transformation matrix for example.

Using STL means occasionally wrangling with the arcane way the whole thing is constructed. I'd agree that rolling out generic STL containers saves time sometimes, but then again, you're dealing with more arcane boilerplate in other ways if you try and do anything remotely complex with them.

Also, bounds checking and asserts. If you make your own vector, you can add debug code right into the class, spit out a log file, find errors. Not really any way to get under the hood and add that easily to STL code. You also don't really want to expose STL stuff in a module interface, because then people could use a wide range of STL functions that you didn't anticipate, potentially breaking the code. STL could thus pollute your interface in unpredictable ways.

[Rose]

There have been thousands of man-hours put into making the stl structs as efficient as possible. You're unlikely to make anything that works faster on your own that has the same functionality.

[Skyrunner]

A great use case for decorators and first class functions!

[alway]

It's better to write your own structure that has an interface similar to std:: stuff. It's tons more compact and efficient. It's good practice to make your own String class that is a replacement for std::string. It saves memory too.

Eh, string seems like one of the worse types to do this for. Strings have a *ton* of functionality and they're used a *lot*.

I'd much rather have the extremely reliable STL for something like that, even if it's a little slower. It's better than having bugs.

You would think so, but you would be wrong. And after you got tons of bugs from using std::string, you would realize it's actually not able to do a lot of what you need it to. Unicode for example, which will be a !!HUGE!! issue for any international support. UTF-8 is probably the most common solution, but several parts of the std library just plain do not support variable-length character encodings.

This means things work in many cases (because UTF-8 was designed in such a way to prevent problems with naive handling), but that really filthy things can be done which may screw you over. For example, incrementing a std::string iterator or otherwise by 1 will not always get you the next character. It will get you the next byte, but with the variable-length encoding, that may still be part of the first character. So if, for example, you wanted to send your strings in limitted size packets over some IO device like a network then print them out immediately on the far side, some of your characters would get mangled into garbage because they were missing the following bytes. (Source: been there, debugged that.) And believe me, an odd off by one in your custom string class is way easier to diagnose and fix than a bug that mysteriously appears only on a foreign language VM with your software that you otherwise wouldn't want to use for testing.

Additionally, you can use the structure of UTF-8 to actually help you recognize bugs elsewhere in your system by implementing a good string class! See, UTF-8 has a specific pattern to the encoding bits such that certain sequences are invalid. By throwing an assert in common use when it sees invalid UTF-8, you can detect memory stomps and other bad data getting into a string's memory in your program automatically whenever it is used, without any additional cost. This has alerted us to numerous subtle bugs in our code. It even detected an otherwise silent multithreaded stack corruption bug caused by a callback going rogue.

I personally spent about a month debugging various string issues in a project that (was required by interfaces to) use a mix of wide characters, UTF8 and typical strings, with a bunch more bugs of that nature in the pipeline. I then spent a month writing a new string class and replacing the old uses of strings, most of which was refactoring thousands of uses in the code base. After the rewrite, there were a grand total of 2 non-trivial bugs in the implementation, both of which were fixed in short order, the backlog of string related bugs magically disappeared, and it alerted us to a memory stomp bug by the end of the month.


In conclusion: I'm not saying std stuff is always bad. What I am saying is it is often missing some detail of context in which you want to use it that makes your life awful if you don't write your own. This could be international string support, this could be serializing data for a network, or it could simply be a lack of ability to easily modify the internal algorithm to optimizing for your particular use case. If you do it right, congratulations, you never need to do it again because you now have your string class or your array class, which has been tested by your projects and whose internals you can modify and are familiar with. The convenience and flexibility this affords you is far too often underestimated.

[Reelya]

Hey, I generally agree "don't reinvent the wheel" and that you're unlikely to come up with something as optimized as a library tweaked to the max that many people have worked on. But ... stl is different. It's a Swiss Army Knife that can kinda do all things "alright" but it's not really "great" any any one thing:

http://stackoverflow.com/questions/21946447/how-much-performance-difference-when-using-string-vs-char-array

Basically, using std::string vs c-string increases time by a factor of 1.5. If you're doing something string-heavy, for every 1 minute the program would normally take, you're not taking 90 seconds instead because you used the "perfectly well optimized" std::strings. So std::string is kinda a sucky implementation: takes a lot more space, and is a lot more slow.

std::vector is pretty good compared to arrays, that one is very close.

For 2D arrays, I'd still go with a custom allocator inside a wrapper class. You have to make the wrapper class anyway whether you're using a vector or array to store the data. Since it's the same basic boilerplate code every time you make a class like this, there are few reasons to think that a vector gives any advantages. Basically you're not going to be using any of the things like push_back, add, standard iterator or anything, so why have them?

std::array is ok, but its size is a template parameter, therefore it's size is set at compile-time, not runtime. So you can't ask the user for a size then size the array, like you could with either a vector or a c-array. It's therefore of limited use.

[Spehss _]

So I'm learning about exceptions and exception handling in C++. Implementation question. Say I have a stack, and I'm using exceptions for handling the issue where peek() is called on a stack that is empty. How would I exit the function? It's a non-void function so I can't use return without passing a value. In the program I've written I use a dummy catch block that doesn't address the exception that's thrown, so the program takes the thrown exception and returns to the function that first called peek() to look for how it should handle the exception.

With this implementation then, if the client does not call peek() in a try block with an included catch statement for that thrown exception, and the stack is empty when peek() is called, then the program could terminate abruptly.

Is there a better way to handle error checking a situation like this? Or is this how exception handling works, with the duty of how to handle the exception falling on the client rather than the function that first threw the exception?

Spoiler: example code (click to show/hide)

Code: [Select]

//NODE DATA TYPE
template<class Item>
class Node
{
private:
Item data;
Node* next; //pointer to next node in list

public:
Node();
Node(Item);
void setData(Item newData){data=newData;}
void setLink(Node* link){next=link;}
void setLink(Node &link){next=&link;}

Item getData(){return data;}
Node* getNext(){return next;}
};
template<class Item>
Node<Item>::Node():next(nullptr)
{
}

template<class Item>
Node<Item>::Node(Item newData):data(newData), next(nullptr)
{
}

//STACK DATA TYPE
template<class Item>
class Stack
{
private:
Node<Item>* tos; //points to top of stack

public:
Stack();
~Stack();
void push(Item);
Item peek();
void pop();
bool isEmpty();
};
template<class Item>
Stack<Item>::Stack():tos(nullptr)
{
}

template<class Item>
Stack<Item>::~Stack()
{
while(tos!=nullptr)
{
Node<Item>* temp=tos->getNext();
delete tos;
tos=temp;
}
}

template<class Item>
void Stack<Item>::push(Item data)
{
//this code adds the new node at the front of the list
//so tos serves as both the header of the list and the pointer
//to the newest item
if(tos!=nullptr)
{
Node<Item>* temp=tos;
tos=new Node<Item>(data);
tos->setLink(temp);
}
else
tos=new Node<Item>(data);
}

template<class Item>
Item Stack<Item>::peek()
{
try
{
if(tos!=nullptr)
{
return tos->getData();
}
else
throw out_of_range("Error: Attempted to access an element in an empty stack.");
//if this occurs, the program will probably terminate unless the client has the peek call in a try block
//and includes an appropriate catch statement for out_of_range exceptions
}
catch(runtime_error) //dummy catch block
{

}
}

template<class Item>
void Stack<Item>::pop()
{
if(tos!=nullptr)
{
Node<Item>* temp=nullptr;
if(tos->getNext()!=nullptr)
temp=tos->getNext();
delete tos;
tos=temp;
}
}

template<class Item>
bool Stack<Item>::isEmpty()
{
return (tos==nullptr);
}

//STACK CODE ENDS


[RulerOfNothing]

With this implementation then, if the client does not call peek() in a try block with an included catch statement for that thrown exception, and the stack is empty when peek() is called, then the program could terminate abruptly.

Is there a better way to handle error checking a situation like this? Or is this how exception handling works, with the duty of how to handle the exception falling on the client rather than the function that first threw the exception?

That is how exception handling is supposed to work, in that the exception is supposed to be dealt with as close to the source as possible (since the stack doesn't know what it's being used for that responsibility belongs to the calling function). Obviously if none of the functions in the call stack know how to deal with the exception then the program should close.

[RoguelikeRazuka]

Hello everyone, here I come again to ask for help. Some time ago I made a simple program in python for visualizing operations on a binary tree (I'm using tkinter's canvas for drawing things). Everything was alright but the problem was that depending on the structure of a tree it was going end up wasting space on the screen, for the distance between the two child nodes on a given level was always fixed, depending on the depth of the root (for example, on the last level it was some dist_min, on the level upper it was 2 * dist_min etc).

Here is an example where everything is nice and you can see all the tree at once:




But here, the tree takes up too much space so that you have to scroll the canvas or resize the window in order to see all the nodes:




Now I want to fix this. How can I display binary trees more tightly? What algorithm could you suggest for this?

[Reelya]

One way would be to store all the node screen positions in a left-right list, then cycle through them, and if there's more than a certain distance, then shunt that node left. Do a single pass of that before displaying it.

For a more satisfying way, you could make a recursive function "space needed", that returns how much space is needed on the left and right of a node for all it's child nodes. Then you space the parent node relative to it's own parent, based on it's needed left/right spacing.

e.g. for nodes on the right branch, start with a node, traverse it's left children, then work out how much space that needs based on the division you're using (e.g. half each time). For nodes on a left branch, you'd need to worry about their "right spacing", when positioning them relative to a parent.

[MagmaMcFry]

Another way to get the same result, without additional data, is to make the horizontal distance between a node and its right child equal to 1 + the size of the right child's left subtree and vice versa.

[TheBiggerFish]

So I'm learning about exceptions and exception handling in C++. Implementation question. Say I have a stack, and I'm using exceptions for handling the issue where peek() is called on a stack that is empty. How would I exit the function? It's a non-void function so I can't use return without passing a value. In the program I've written I use a dummy catch block that doesn't address the exception that's thrown, so the program takes the thrown exception and returns to the function that first called peek() to look for how it should handle the exception.

With this implementation then, if the client does not call peek() in a try block with an included catch statement for that thrown exception, and the stack is empty when peek() is called, then the program could terminate abruptly.

Is there a better way to handle error checking a situation like this? Or is this how exception handling works, with the duty of how to handle the exception falling on the client rather than the function that first threw the exception?

Spoiler: example code (click to show/hide)

Code: [Select]

//NODE DATA TYPE
template<class Item>
class Node
{
private:
Item data;
Node* next; //pointer to next node in list

public:
Node();
Node(Item);
void setData(Item newData){data=newData;}
void setLink(Node* link){next=link;}
void setLink(Node &link){next=&link;}

Item getData(){return data;}
Node* getNext(){return next;}
};
template<class Item>
Node<Item>::Node():next(nullptr)
{
}

template<class Item>
Node<Item>::Node(Item newData):data(newData), next(nullptr)
{
}

//STACK DATA TYPE
template<class Item>
class Stack
{
private:
Node<Item>* tos; //points to top of stack

public:
Stack();
~Stack();
void push(Item);
Item peek();
void pop();
bool isEmpty();
};
template<class Item>
Stack<Item>::Stack():tos(nullptr)
{
}

template<class Item>
Stack<Item>::~Stack()
{
while(tos!=nullptr)
{
Node<Item>* temp=tos->getNext();
delete tos;
tos=temp;
}
}

template<class Item>
void Stack<Item>::push(Item data)
{
//this code adds the new node at the front of the list
//so tos serves as both the header of the list and the pointer
//to the newest item
if(tos!=nullptr)
{
Node<Item>* temp=tos;
tos=new Node<Item>(data);
tos->setLink(temp);
}
else
tos=new Node<Item>(data);
}

template<class Item>
Item Stack<Item>::peek()
{
try
{
if(tos!=nullptr)
{
return tos->getData();
}
else
throw out_of_range("Error: Attempted to access an element in an empty stack.");
//if this occurs, the program will probably terminate unless the client has the peek call in a try block
//and includes an appropriate catch statement for out_of_range exceptions
}
catch(runtime_error) //dummy catch block
{

}
}

template<class Item>
void Stack<Item>::pop()
{
if(tos!=nullptr)
{
Node<Item>* temp=nullptr;
if(tos->getNext()!=nullptr)
temp=tos->getNext();
delete tos;
tos=temp;
}
}

template<class Item>
bool Stack<Item>::isEmpty()
{
return (tos==nullptr);
}

//STACK CODE ENDS


If you can't handle the exception, don't catch it.

So yes, it is the client's job to handle that exception where it can actually do something intelligible, or make sure it doesn't get thrown in the first place.

I don't think that try-catch even belongs in your program...

Throwing an exception is a valid way to exit a method.

[Reelya]

I'd steer clear of writing your own exception-based systems.

You can use try/catch to pick up exceptions thrown by libraries, that's the place to start. Exceptions are really meant to catch abnormal run-time events rather than bugs. Also, using exception handling can create complex program-flow paths that are hard to debug.

You could use "assert" instead. You basically put an assert statement that says the pointer is not null. assert is for checking for erroneous coding conditions, and it doesn't create the problem of the additional program-control-path needing to return a value.

Assert is also a macro. So you can use asserts in literally every function that could even remotely receive erroneous parameters, e.g. do bounds-checking with it on all your arrays. This of course will be slow. But the cool thing is, you just need to add this:

#define NDEBUG

And all the asserts get turned off for your production build.

[Spehss _]

I don't think that try-catch even belongs in your program...

Yeah, I realize that now. When learning about try-catch and exceptions, all the example code I saw had some conditions in a try statement, which would throw an exception if the condition was false, and then immediately after that there'd be the catch statement for the thrown exception.


New question, writing a program demonstrating use stl containers like std::array or std::vector or std::list or std::forward_list.

With forward_list, it looks like the only element that can be accessed of the list is the first item in the list. So to access anything beyond that first "front" element I'd need to pop the front element, right? This doesn't sound any different from a stack, except the list can insert new elements elsewhere than the front of the list.

[Spehss _]

Not quite. The first element in a list is the only one that can be accessed immediately; that first element has a pointer to the second, the second to the third, and so on. So you can only iterate in one direction.

How would I access anything past that front element? Pointer arithmetic?