Невозможно поместить элементы в вектор и список в C ++?

Question

Это базовая программа сортировки слиянием:

Проблема в том, что когда я пытаюсь вставить элемент в «векторное слияние», ничего не происходит. (Пожалуйста, обратитесь к данным GDB под кодом)

vector<long> merge(vector<long> &L, vector<long> &R){

  int i = 0;
  int j = 0;
  vector<long> merged;

  while((i < L.size())&&(j < R.size())){
    if ((L[i] <= R[j])){ 
      merged.push_back(L[i]);  
      i++;
    }else{
      merged.push_back(R[j]);
      j++;
    }

    while(i < L.size())
    {
        merged.push_back(L[i]);
        i++;
    }

    while(j < R.size())
    {
        merged.push_back(R[j]);
        j++;
    }
    return merged;

  }
}

// ========================================= GDB DATA ======== ===========================

(gdb) n
52    int i = 0;
(gdb) 
53    int j = 0;
(gdb) 
54    vector<long> merged;
(gdb) print i
$2 = 0
(gdb) print merged
$3 = {<std::_Vector_base<long, std::allocator<long> >> = {
    _M_impl = {<std::allocator<long>> = {<__gnu_cxx::new_allocator<long>> = {<No data fields>}, <No data fields>}, _M_start = 0x7fffffffdcd0, 
      _M_finish = 0x7fffffffdcf0, _M_end_of_storage = 0x7fffffffdde0}}, <No data fields>}
(gdb) print *(merged._M_impl._M_start)@merged.size()
$4 = {140737488346528, 4199556, 140737488346432, 140737488346656}

Problem I: Why the merged vector is not null? Or did I used wrong gdb command?? But same command works on other vectors in this program..


(gdb) 
$5 = {140737488346528, 4199556, 140737488346432, 140737488346656}
(gdb) n
56    while((i < L.size())&&(j < R.size())){
(gdb) print *(merged._M_impl._M_start)@merged.size()
$6 = {140737488346528, 4199556, 140737488346432, 140737488346656}
(gdb) n
57      if ((L[i] <= R[j])){ 
(gdb) print L[i]
$7 = (long &) @0x6060b0: 31616136
(gdb) print R[i]
$8 = (long &) @0x6060d0: 1873051691
(gdb) n
58        merged.push_back(L[i]); 
(gdb) print *(merged._M_impl._M_start)@6
$14 = {140737488346528, 4199556, 140737488346432, 140737488346656, 6316272, 6316280}
// Before any push_back operation, dump the content of merged.

(gdb) n
59        i++;

// Question 2, Push_back does not work...
(gdb) print *(merged._M_impl._M_start)@1
$17 = {140737488346528}
(gdb) print *(merged._M_impl._M_start)@2
$18 = {140737488346528, 4199556}
(gdb) print *(merged._M_impl._M_start)@8
$19 = {140737488346528, 4199556, 140737488346432, 140737488346656, 6316272, 6316280, 6316280, 4205125}

Может ли кто-нибудь дать мне руку?

Answer 1

У вас есть ошибка в алгоритме, сейчас кажется, что первый элемент будет слит правильно, но затем все L будут сдвинуты, а после этого все R.

Кажется, что перемещение закрывающей скобки решит вашу проблему.

vector<long> merge(vector<long> &L, vector<long> &R){

  int i = 0;
  int j = 0;
  vector<long> merged;

  while((i < L.size())&&(j < R.size())){
    if ((L[i] <= R[j])){ 
      merged.push_back(L[i]);  
      i++;
    }else{
      merged.push_back(R[j]);
      j++;
    }
  }

  while(i < L.size())
  {
    merged.push_back(L[i]);
    i++;
  }

  while(j < R.size())
  {
    merged.push_back(R[j]);
    j++;
  }
  return merged;
}

Answer 2

См. std :: merge

std::vector<long> merge(std::vector<long>& lhs, std::vector<long>& rhs)
{
    std::vector<long> result(rhs.size() + lhs.size());
    std::merge(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), result.begin());
    return result;
}

Answer 3

Хотя я признаю преимущества объединения двух векторов, этот код также работает, копируя два вектора вместе, а затем сортируя.Я также удалил потенциальную копию всего объединенного вектора по возвращении, передав в качестве параметра выходной вектор.

void merge(const vector<long>& lhs, const vector<long>& rhs, vector<long>& merged ) {
    merged.resize(lhs.size()+rhs.size());
    copy( lhs.begin(), lhs.end(), merged.begin() );
    copy( rhs.begin(), rhs.end(), merged.begin() + lhs.size() );
    sort( merged.begin(), merged.end() );
}