смерджение векторов

[Bart]

Есть код.
Объединяющий в один упорядоченный вектор

Код: (C++)

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;


int main(int argc, char** argv)
{
  vector<int> v1, v2, vMerged;
  v1.push_back(100);
  v1.push_back(300);
  v1.push_back(140);

  v2.push_back(2);
  v2.push_back(3);
  v2.push_back(4);


  vMerged.resize(v1.size() + v2.size());
  merge(v1.begin(), v1.end(), v2.begin(),v2.end(), vMerged.begin());

  cout << "Merged vector: \n";
  for(int i=0;i<vMerged.size();++i){
      cout << vMerged[i] << "\n";
  }

  return (0);
}

два Вопроса:
1. Возможно ли обойтись без буферного вектора, т.е. например расширить v1 или v2
2. Есть ли рациональные пути обойтись без merge().

СПАСИБО!

[Finch]

А кто мешает добавить значения v2 в v1?

[Bart]

Спасибо за внимание. Я вроде решил. Но не понимаю насколько правильно. Буду признателен если поправите/подскажите как улучшить

Код:

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

void print(int elem)
{
  cout << elem << " \n";
}
void mkmerge(const std::vector< int > &v1, std::vector< int > &v2)
{
    if(v1[v1.size()-1]<v2[0]){
        v2.insert( v2.begin(), v1.begin(), v1.end() );

    }
    else if(v2[v2.size()-1]<v1[0]){
        v2.insert( v2.end(), v1.begin(), v1.end() );

    } else {

    int i = 0, j = 0;
 
    while (i<v1.size() && j <v2.size())
    {
        if (v1[i] < v2[j]){
              v2.insert( v2.begin()+j, v1[i++] );
        }
	j++;
    }
    }
}

int main(int argc, char** argv)
{
  vector<int> v1, v2,v3;
  v1.push_back(100);
  v1.push_back(140);
  v1.push_back(200);
  v1.push_back(200);
 v1.push_back(800);


  v2.push_back(200);
  v2.push_back(500);
  v2.push_back(300);
  v2.push_back(900);

  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());

  mkmerge(v1,v2);

  
  cout << "Merged vector: \n";
  for_each(v2.begin(), v2.end(), &print);
  return (0);
}

[Bart]

Т.е. слияние двух отсортированных векторов в один засчет расширения одного из них

[RXL]

Слияние в уже отсортированный массив потребует перемещения данных расширяемого массива.Выигрыша по CPU нет, есть выигрыш по памяти на размер расширяемого массива. При этом расширяемый вектор вероятно потребует переалокации, а значит больше памяти (выигрыш полностью пропал), плюс копирование данных (дополнительные расходы CPU). В итоге проще выделить результирующий массив, за исключением особых ситуаций.

[Finch]

А что мешает сначало слить два вектора в один а затем отсортировать

Код: (C++)

typedef std::vector<int> ListInt;
typedef ListInt::iterator ItrListInt;

ListInt v1, v2;
// Some action with vector

for(ItrListInt itr = v2.begin(); itr != v2.end(); ++itr) v1.push_back(*itr);
sort(v1.begin(), v1.end());

//C++11 notation
// for(auto x : v2) v1.push_back(x);

[RXL]

Сортировка слиянием более дешевая операция, однопроходная.
N против NlogN

И, Вить, push_back это очень медленно и очень неэффективно. Возможно неоднократное выделение памяти, возможно излишнее выделение памяти. Быстрее будет insert range: если место есть, только копирование, если нет, то одна переалокация с возможным перемещением данных.

[Finch]

Ром, насколько я разбирался с вектором. Если не вмешмватся в механизм работы. Сначало автоматически выделяется под 8 элементов место. Если происходит запрос на 9 место. То этот объем автоматически умножается на 2. Т.е. 16 мест. И так далее. Все время происходит умножение на два объема.

Добавлено через 11 минут:
В принципе в начале слияния можно сделать, что то типа

Код: (C++)

if (v1.size()+v2.size() > v1.capacity()) v1.resize(v1.size()+v2.size());

[Алексей++]

И, Вить, push_back это очень медленно и очень неэффективно.

reserve в помощь

[Алексей++]

А что мешает сначало слить два вектора в один а затем отсортировать

Код: (C++)

ListInt v1, v2;
// Some action with vector

for(ItrListInt itr = v2.begin(); itr != v2.end(); ++itr) v1.push_back(*itr);

а я бы вот так "слил"

Код: (C++)

v1.insert(v1.end(),v2.begin(),v2.end());

[Bart]

Спасибо за ответы. Использование 2х векторов - это условие задачи.
Так в итоге, у меня получилось найти самый быстрый путь:)?  Или есть лучше варианты, или можно как-то улучшить?

Добавлено через 9 минут и 50 секунд:
Я наверно плохо сформулировал.
Есть два упорядоченных вектора. Нужно за минимальное время объединить их в один отсортированный вектор, причем это должен быть один из них(т.е. не создавая третий).

[RXL]

Ром, насколько я разбирался с вектором. Если не вмешмватся в механизм работы. Сначало автоматически выделяется под 8 элементов место. Если происходит запрос на 9 место. То этот объем автоматически умножается на 2. Т.е. 16 мест. И так далее. Все время происходит умножение на два объема.

Зависит от реализации. Тесты на gcc/libstdc++ показывают, что нет изначального избыточного выделения. При нехватке емкость вектора удваивается с релокацией. По этому один push_back при отсутствии резерва даст почти двухкратный перерасход памяти. Если еще есть оптимизация с алокаторами, это просто ад и потеря памяти.
И да, ручное задание нужного размера — лучшая тут оптимизация. А по сумме совершенных микродействий оказывается, что все это было лишним, можно было прочто выделить новый вектор и слить в него. Исключение, если место уже было.

[RXL]

Нужно за минимальное время

По тому, что я писал выше, быстрее именно с третьим вектором. Merge ищет разницу и копирует сериями, это быстрее, чем поштучное копирование при сортировке.

[Aether]

Есть два упорядоченных вектора.

Код: (C++)

  v1.push_back(100);
  v1.push_back(300);
  v1.push_back(140);

  v2.push_back(2);
  v2.push_back(3);
  v2.push_back(4);

Что-то не похожи они на упорядоченные массивы, или я не прав?

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

[RXL]

Полагаю это опечатка.

Увеличение вектора веротянее всего даст реалокацию и копирование в новое место. Уже устал повторять. Читать не надо, я еще раз повторю

[Aether]

Увеличение вектора веротянее всего даст реалокацию и копирование в новое место. Уже устал повторять. Читать не надо, я еще раз повторю

Я то это понимаю, но что поделаешь, если его, наверное, преподаватель хочет:

Есть два упорядоченных вектора. Нужно за минимальное время объединить их в один отсортированный вектор, причем это должен быть один из них(т.е. не создавая третий).

То есть, создание третьего вектора будет в неявном виде, хотя может быть и резерв у менеджера памяти. Он не всегда плотно компонует выделяемые блоки.

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

[RXL]

Алгоритм писать не нужно, все давно написано до нас. Нужно лишь правильно применить. Библиотеки существуют именно для этого.

С заданием он, вроде, справился (я не учитель, не не проверял). Главное не задание, а самостоятельность, умение думать и использовать инструменты. И еще понимание, что велосипеды не стоит тащить на работу.