Roast me

[highwayman]

Lessthan func without mem leaks:

template <size_t nA,size_t nB>
bool lessthan(bitset<nA> leftArg,bitset<nB> rightArg){
  int * laSet;
  int * raSet;
  laSet = new int [leftArg.count()];
  raSet = new int [rightArg.count()];
  int x = 0;
  for(int i = 0;i < nA;i++){
    if(leftArg[i] == 1){
      laSet[x++] = i;
    }
  }
  x = 0;
  for(int i = 0;i < nB;i++){
    if(rightArg[i] == 1){
      raSet[x++] = i;
    }
  }
  for(int i = 0; i < (leftArg.count() < rightArg.count() ? leftArg.count() : rightArg.count());i++){
    if(laSet[i] < raSet[i]){
      delete[] raSet;
      delete[] laSet;
      return true;
    }
  }
  delete[] raSet;
  delete[] laSet;
  return false;
}

[Niccolo]

I know you just posted your correction, but have you considered:

std::unique_ptr<int[]> raSet (new int[ leftArg.count() ]);

Since C++11, this is supported, and that line is a slightly modified example straight out of the C++ documentation on cplusplus.com ( http://www.cplusplus.com/reference/memory/unique_ptr/operator[]/ ) on a related point.

This way, you don't have that "double delete" thing happening, AND it becomes a bit more exception safe.

[jonnin]

that just looks inefficient. can't you just find the most significant set bit (if equal, ignore and get next) until you know somehow? IF all equal, they are same number. ?? Three for loops with memory allocation … would take forever!

[highwayman]

@Niccolo I have no experience with unique_ptr so I don’t entirely understand why that would work out that way so I’m just going to look that over first..

[highwayman]

@jonnin True...(sry your post didn’t load for a bit) let’s see

[Niccolo]

Oh, sorry....

It stands in for the raw pointer and automatically deletes the memory upon exit from the function.

No memory leaks (which is the point behind all smart pointers).

Also, since you don't have to call delete yourself, no dual delete (or more) statements required.

The link points to the [] operator overload, so the pointer works like your array.

They are, quite simply, among the single most important things to know about modern C++.

(Important implication, if you switch to unique_ptr, remove the delete statements).

A simple subsitution of your current "new" declarations is all that is required to implement (other than removing the delete statements).

[highwayman]

Wait no that’s not true because they could be of different sizes and then I’m testing one against nothing.

[jonnin]

correct. but you can add a tiny bit of work to handle that, and still come out an order of magnitude or more faster. which ever one is bigger, you just check against (nonexistent) leading zeros and if you find a 1, the longer one is bigger. Once you get to the point the 2 are equal length, as I said from there...

so you do need 2 loops for that, but its overlapped, so its still a O(n) effort without any memory allocation or other mess. where n is the longest bitset.

I really wish they had added a compact to bitset to clear off leading zeros. I get why its not there, but it would have been nice.

[highwayman]

@Niccolo now that I think of it, unique_ptr sounds like something in java maybe?

@jonnin ok well let’s see I’m going to try this out (basically going to eventually post some code for that)..

[highwayman]

Literally just use vector bool and then I think there’s a shrink_to_fit function right?

[jonnin]

yes but that is also inefficient. Leave it be if you want speed. It should not grow too much out of control, if you are careful. Shrink to fit isn't about the data, its about used memory locations. You would have to make that work to do what you want. You can't resize things fast. Its usually best avoided unless something goes on an out of control growth, and better to fix that than to resize.

[highwayman]

Yeah, I was just saying it for kicks, basically we could do this, but were not necessarily going to do it. It’s just cool

[highwayman]

Jonnin idea for lessthan func:

template <size_t nA,size_t nB>
bool lessthan(bitset<nA> leftArg,bitset<nB> rightArg){
  if(nA > nB){
    for(int i = nA - 1;i > (nB - 1);i--){
      if(leftArg[i] == 1){
        return false;
      }
    }
    for(int i = nB - 1;i >= 0;i--){
      if(leftArg[i] < rightArg[i]){
        return true;
      }
    }
    return false;
  }
  if(NB > nA){
    for(int i = nB - 1;i > (nA - 1);i--){
      if(rightArg[i] == 1){
        return true;
      }
    }
    for(int i = nA - 1;i >= 0;i--){
      if(leftArg[i] < rightArg[i]){
        return true;
      }
    }
    return false;
  }
}

[Niccolo]

now that I think of it, unique_ptr sounds like something in java maybe?

Well, not exactly. Java and related languages ( C# ) use reference counted containment. They are automatic, so no deletion is required, but they more resemble std::shared_ptr (for the reference counting).

On the other hand, the effect of any smart pointer is loosely similar to the concepts behind references in C# and Java (which is their parlance for this).

std::unique_ptr does not implement reference counting. It works like a raw pointer in the sense that it is fast, simple an lightweight. The references in Java and C# are much heavier, larger and more imposing (though flexible).

The automatic release of resources (memory in this case) is key to modern C++.

[highwayman]

There we go ok thanks.

[dhayden]

If this is just for fun then you might want to consider something like the bignum library. It supports arbitrary length numbers.

Or if you want to code it yourself, consider using vector<char> to represent numbers where each char is a single digit. If you feel comfortable with the math concepts then you could have each char be a base 256 digit. Or you could use vector<int> or vector<long> and have each value be appropriately huge. Hint: use values that are half the maximum size supported by the processor. That way you can easily multiple single-digit values and get a 2-digit result.

But if your goal is to code it low-level with bits and not using built-in arithmetic, then what you're doing is good, but I'd consider vector<bool> instead of templates. That way your numbers can have arbitrary precision.

[highwayman]

@dhayden I’m not using a string of chars or ints because I’ve tried at least 5 times to write working, uncomplicated code using them and it just doesn’t work. the way I am currently doing it is vastly simpler and takes up much less space comparably. I would have used vector<bool>, but my numbers are each very specific sizes and bitset is better predisposed towards representation of a number. I probably will use it for my m and c though, which do have to be of variable length.

[Albatross]

So I have a few corrections to contribute wrt. memory management as discussed in this thread. Sorry! EDIT: Sorry @ beginners, this post was more @Niccolo.

The JVM and CLR environments don't use reference-counted garbage collection. They can't, unless their implementations were to do some black magic to take care of reference cycles. That's one of the bigger problems with naive reference counting: if there's a cycle in the reference graph (as in you can loop back to an object by following a chain of counted references), none of the objects in the cycle will get automatically freed once the cycle becomes unreachable from the rest of the program (i.e. the root). Congrats, you've leaked resources. And yes, this applies to std::shared_ptr too. Instead, both environments (EDIT: JVM and CLR) currently use multithreaded generational garbage collection (though the actual algorithms differ quite a bit). These are not simple algorithms, and they are still being refined to this day.

Also, std::unique_ptr is not a fundamental type in C++17. I'm pretty sure it's still a class template in <memory>. That said, the syntax for using it has gotten quite a bit more elegant with template argument deduction.

Side note, thanks to std::make_unique/make_shared, smart pointers can be used in a way that doesn't involve the new keyword either. Neat, no?

-Albatross

[highwayman]

@TheDaemoness Uh... Wah..? I didn’t understand 95% of your post sry, would you mind dumbing it down for me?

[Niccolo]

The JVM and CLR environments don't use reference-counted garbage collection

What you're saying here is a bit intrinsic, but C# and Java references are reference counted storage in C# and Java. What you're talking about is the garbage collection phase, which is an internal issue for C# and Java programmers. The only way there can be any realization that an instance has been released is for the reference count to reach zero, which is where garbage collection finally comes into play for release of memory. Prior to that, at most, the instance might be relocated, but not released.

The point you are making is that in std::shared_ptr there can be circular references which cause memory leaks (creating such a cycle means nothing ends up releasing).

For the students here, that means A refers to B, while B refers to A through smart pointers. When that can happen, user code might release both A and B, but since they "hold" references to each other, nothing will be deleted.

The std::shared_ptr relies upon std::weak_ptr to break this cyclic reference (Scott Meyers has other important recommendations), but that only occurs if the user happens to create the situation (for all languages). Fortunately it isn't all that typical. Unfortunately, naive developers hardly ever realize when it has happened.

C# and Java track this to break these cycles, but fundamentally the references ARE counted. The OP is not at a level where such differences actually matter. A debate on the subject is a little beyond the scope here, and garbage collection wasn't really part of the substance - automatic resource release using RAII (which wasn't brought up either) was the primary point.

By "both environments" one must clarify that you're referring to C# and Java, not C++. Garbage collection in C++ is either implemented through a library (rare), or in an forthcoming version of C++, when/if they get around to it.