-1

To find all sequences of fixed length which contain only 0 and 1 I use this code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void print_array(vector<string> arr) {
  cout << '[';
  int n = arr.size();
  for (size_t i = 0; i < n; i++) {
    cout << arr[i];
    if (i < (n - 1)) {
      cout << ", ";
    }
  }
  cout << ']' << endl;
}

vector<string> get_variants(int n) {
  vector<string> result = {"0", "1"};
  vector<string> temp;
  temp.reserve(2);
  result.reserve(2);
  for (int i=0; i < (n - 1); ++i) {
    copy(result.begin(), result.end(), temp.end()); // [1]
    for (int j=0; j < result.size(); ++j) {
      temp[j] += "0";
      result[j] += "1";
    }
    copy(temp.begin(),temp.end(), result.end());
    temp.clear();
  }
  return result;
}

int main(int argc, char const *argv[]) {
  int n;
  cin >> n;
  vector<string> maybe = get_variants(n);
  print_array(maybe);
  return 0;
}

But vector temp is empty, before copying in line which I marked [1] and after. So, my program's output was [0111, 1111]. What I'm doing wrong?

Vad Sim
  • 266
  • 8
  • 21
  • 6
    Your code bear all the signs of so-called "competition" and "online judge" sites. Such sites are not any kind of teaching or learning resource, and using them can be direct harmful to your learning process, as all taught by such sites seems to be really bad habits and often also direct invalid code. Invest in [some good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282), take classes, and stay away from such sites until you have learned away the bad habits and replaced them with good. – Some programmer dude Dec 09 '21 at 13:46
  • 1
    You are writing to `temp.end()` and `result.end()`. These are iterators to placeholder elements, and [attempting to write to them results in Undefined Behavior](https://en.cppreference.com/w/cpp/container/vector/end). – Drew Dormann Dec 09 '21 at 13:49
  • @DrewDormann, post it as answer, and I will mark it as a solution – Vad Sim Dec 09 '21 at 13:50
  • 2
    There appears to be rather more wrong with your code than just attempting to write to the vectors' `.end()` iterators. – Adrian Mole Dec 09 '21 at 13:59

3 Answers3

2

A more straightforward way than using std::copy is the use of .insert():

temp.insert(temp.end(), result.begin(), result.end()); //1
...
result.insert(result.end(), temp.begin(), temp.end()); // 2nd copy
Christian Halaszovich
  • 447
  • 1
  • 2
  • 7
1

You are writing to temp.end() and result.end(). These iterators represent "one past the end", and therefore writing to these iterators is Undefined Behavior.

You seem to be looking for std::back_inserter. This will create an iterator that will insert a new element to your container when it is written through.

std::copy(result.begin(), result.end(), std::back_inserter(temp));

While this answers the posted question, there remain other errors in your code leading to Undefined Behavior.

Drew Dormann
  • 59,987
  • 13
  • 123
  • 180
  • 1
    `std::back_inserter` is not an iterator. `std::back_insert_iterator` is. `std::back_inserter` is just a convenience function to handle template argument deduction, like `std::make_pair`. – Armen Tsirunyan Dec 09 '21 at 14:06
1

Trying to compile your program with a C++ compiler will not work, because you include #include <bits/stdc++.h>which is a non tC++ standard compliant header.

You should never include this file.

You are using typical competitive programming stuff, but including all C++ headers and not use them will eat up Compile time for no good reason.

Then, you typedef the typical competitive programming abbreviations. 2 of them, you do not use. Then there is no reason to define them.

I recommend to not do this any longer. And in C++, please use the using statement.

Then, although you want to be fast, you pass arr by value to your print function. This will copy the whole vector.

You assign/compare a lot of int with unsigned int values. This you should not do.

Additionally: Please use meaningful variable names and write comments. The more the better.

Regarding your specific bug. Both std::copy statements use end iterator as target. End is end. It is past the end of the vector. Please use std::back_inserter instead.

Regarding the algorithm. I took a while for me to realize that you basically want to create binary numbers. Nothing else. Unfortunately you translated that in a very complicated way.

Normally, you just would count from 0 to 2^n-1 and then show the data. Thats all. Becuase the numbers may be of arbitraty length, we will use manual addition of digits like in scholl on a peice of paper. Very simple.

Everthing then biols down to some lines of code.

Please see:

#include <iostream>
#include <vector>

int main() {
    // Read length of binary number to create and validate input
    if (int numberOfDigits{}; (std::cin >> numberOfDigits and numberOfDigits > 0)) {

        // Here we will store the binary digits, so 0s or 1s
        std::vector<int> digits(numberOfDigits,0);

        // Som printing helper
        std::cout << '[';
        bool printComma{};

        // We need to print 2^n possible combinations
        for (int i = 0; i < (1 << numberOfDigits); ++i) {

            // Print comma, if need
            if (printComma) std::cout << ','; printComma = true;

            // Print all digits of the binary number
            for (const int d : digits) std::cout << d;
           
            // Calculate next binary number
           int carry = 0;
           for (int index=numberOfDigits -1; index >=0; --index)  {
                
                const int sum = digits[index] + ((index == (numberOfDigits - 1)?1:0)) + carry;
                carry = sum / 2;
                digits[index] = sum % 2;
            } 
        }
        std::cout << ']';
    }
}

If there should be questions, then I am happy to answer.

A M
  • 14,694
  • 5
  • 19
  • 44