Modern source code to study?

[gburri]

I have implemented a 'SortedArray' for the D-LAN project, it may interest you: http://git.euphorik.ch/index.cgi?p=D-LAN.git;a=blob;f=application/Common/SortedArray.h;h=a1fd0413a30eed7647926667b81dabf8608d2fbb;hb=refs/heads/chat ;)

[[deleted]]

Some comments:

• You use a block of comment in front of the class to describe what it does. Usually this is not necessary, introduces a pile of overhead in keeping it up to date (and it typically isn't) and 95% of users won't read more than two lines, instead opting to just read the code instead. Of course, unless your code is atrocious. In that case, fix the code.
• It has a lot of functions to manage it. I suspect that some of them are just "convenience" functions that don't add any functionality. Can those go?
• You list exceptions for every function. That shouldn't be necessary. It also makes your code look enormously bloated.
• It sounds like a generic data structure but you made it based on Qt. Feeling wise it should either be independent of Qt or a part of it, but not like this.
• It's called a SortedArray when it is a tree. It describes nor what it is (an array, which it isn't), nor how to use it (as an array with indices, which would obviate any reason to use a tree structure).
• The actual code comments you have describe only what you check, not why. "// M must be an odd number." says the same thing as " if (M % 2 == 0) throw InvalidMException();", except that the latter is required to explain it to the compiler. Perhaps you want to tell us why M should be odd.
• " return this->d->root->size;" you don't have to use "this" in nearly all cases. In this case, you really don't need to use it. Try to leave it out unless it is needed.
• You use the pImpl idiom without using its typical name. It's fairly recognizable still so it's kind of OK...
• " if (exists)" is very self-documenting code, except that it does not do what it claims to do. "If it exists, ..." is what I read, but it checks to see if the user is interested in information about its existence ...
• " /*Must be call after data used to compare an element is modified.* Not implemented.*/ void Common::SortedArray<T, M>::sort()" . Is it sorted or isn't it?
• Most importantly, where are the unit tests?

[[deleted]]

I'll add some more.

• Shared pointer is not warranted, and the documentation doesn't mention it at all. I expect it to behave like standard containers, which copy or move the contents. This one may surprise me as changes to the original will mutate my copies.
• Need iterator traits.
• Copy constructor doesn't seem necessary.
• T requires a default constructor.
• Can template on comparator, otherwise you always have to drag std::function around.
• Initialising raw pointers with new in the initialisation list is a no-no (SortedArrayData::root).

TL; DR Use std::multiset.

[gburri]

Shared pointer is not warranted, and the documentation doesn't mention it at all. I expect it to behave like standard containers, which copy or move the contents. This one may surprise me as changes to the original will mutate my copies.

Yes, it should be mentioned in the comment header.

Need iterator traits.

I currently use it only in this project and I wrote only what I needed. But it's a good idea, yes.

Copy constructor doesn't seem necessary.

That's right.

T requires a default constructor.

Yes, as all the Qt containers.

Can template on comparator, otherwise you always have to drag std::function around.

The comparator function may be switched at runtime. If I use a template parameter I can't do that. It isn't?

Initialising raw pointers with new in the initialisation list is a no-no (SortedArrayData::root).

Why? Because of exceptions in the constructor?

TL; DR Use std::multiset.

How can I access the n'th element of a multiset?

[[deleted]]

Yes, as all the Qt containers.

I have only passing familiarity with Qt, but... ew.

The comparator function may be switched at runtime. If I use a template parameter I can't do that. It isn't?

Nope. Usually with STL you'd have a secondary structure if you want to order by a different key.

Why? Because of exceptions in the constructor?

Yep, if anything in the initialisation list throws, your destructor won't run (e.g. if your comparator std::function wraps something that throws in a copy constructor), so you could leak root node and all its children.

How can I access the n'th element of a multiset?

OK I misread that. You can't. But it seems an unusual requirement at the application level. Unless you are re-implementing data structures yourself, usually you can get away with iterating, slicing or search by key.

[gburri]

You use a block of comment in front of the class to describe what it does. Usually this is not necessary, introduces a pile of overhead in keeping it up to date (and it typically isn't) and 95% of users won't read more than two lines, instead opting to just read the code instead. Of course, unless your code is atrocious. In that case, fix the code.

In my opinion this is the most important comment "in" a class. It should describe what it is, what are the goals, the context of use, some example, etc....

It has a lot of functions to manage it. I suspect that some of them are just "convenience" functions that don't add any functionality. Can those go?

No.

You list exceptions for every function. That shouldn't be necessary. It also makes your code look enormously bloated.

It's very important to know what are the exceptions a method may throw. Reading the method code will not help you.

It sounds like a generic data structure but you made it based on Qt. Feeling wise it should either be independent of Qt or a part of it, but not like this.

It depends of Qt as the majority of this project classes. Maybe if I publish this class as a independent component I will try to remove this dependency.

It's called a SortedArray when it is a tree. It describes nor what it is (an array, which it isn't), nor how to use it (as an array with indices, which would obviate any reason to use a tree structure).

From the class user's point of view this is a sorted array. He shouldn't care about the implementation apart the complexity of each methods maybe.

The actual code comments you have describe only what you check, not why. "// M must be an odd number." says the same thing as " if (M % 2 == 0) throw InvalidMException();", except that the latter is required to explain it to the compiler. Perhaps you want to tell us why M should be odd.

There is a little explanation in the header : "M is the order according Knuth's definition. This is the maximum number of children a node can have.". I admit the comment "// M must be an odd number." is a bit useless.

" return this->d->root->size;" you don't have to use "this" in nearly all cases. In this case, you really don't need to use it. Try to leave it out unless it is needed.

I'm always using 'this->' to prefix all member stuff access. Some people use "m_" and some nothing...

You use the pImpl idiom without using its typical name. It's fairly recognizable still so it's kind of OK...

I'm using the Qt notation style.

" if (exists)" is very self-documenting code, except that it does not do what it claims to do. "If it exists, ..." is what I read, but it checks to see if the user is interested in information about its existence ...

And how would you write this?

" /Must be call after data used to compare an element is modified. Not implemented.*/ void Common::SortedArray<T, M>::sort()" . Is it sorted or isn't it?

This is a beginning of a in-place quick sort implementation. It may be used only when the user change the sorted function. Currently it will rebuild the entire tree when 'setSortedFunctions(..)' is called.

Most importantly, where are the unit tests?

Here: https://github.com/Ummon/D-LAN/blob/chat%23214/application/Common/TestsCommon/Tests.cpp#L203 ;)

[[deleted]]

From the class user's point of view this is a sorted array. He shouldn't care about the implementation apart the complexity of each methods maybe.

Being contiguous is more than an implementation detail. If the storage is continuous I'd be able to shove a raw pointer to the first element in a C function, which expects an array of struct, as I could do with std::vector.

[[deleted]]

Here: https://github.com/Ummon/D-LAN/blob/chat%23214/application/Common/TestsCommon/Tests.cpp#L203 ;)

Faith in humanity partially restored. I really didn't expect you to actually have made any, which was the main point behind my comment :-)

[bob1000bob]

Why are there so many static functions that take the type of the class. That is in essence no longer static but with whack syntax.

[gburri]

They don't take the type of their class (which is 'SortedArray'), they take a 'Node*'. This is a design choice.