4

I earlier posted a question on the optimal way to concatenate two std::vectors, where one vector must first be transformed. While the obvious solution using std::transform may not be the theoretically optimal solution, the cost of the multiple capacity checks are unlikely to be significant.

But if we consider the more general problem of inserting one vector which must be transformed into another, then there is now a potential significant overhead involved.

What is the optimal method to do this?

Community
  • 1
  • 1
Daniel
  • 8,179
  • 6
  • 31
  • 56

3 Answers3

1

I see a few options here:

Method 1: temp transform

std::vector<T1> temp {};
temp.reserve(vec.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(temp), op);
vec1.insert(vec1.begin() + pos, std::make_move_iterator(temp.begin()),
               std::make_move_iterator(temp.end()));

But now the overhead is not a trivial capacity check, instead the additional costs is an allocation/deallocation of size_of(T1) * vec2.size() for temp. This could easily be a significant cost if vec2 is large.

Method 2: loop insert

vec1.reserve(vec1.size() + vec2.size());
std::size_t i {pos};
for (const auto& p : vec2) {
    vec1.insert(vec1.begin() + i, op);
    ++i;
}

This avoids the additional allocation/deallocation of method 1 but there is another serious problem with this solution: each of the n = vec1.size() - pos elements in vec1 have to be shifted n times, a O(n^2) operation.

Method 3: shift and copy

vec1.resize(vec1.size() + pair_vec.size());
std::move(vec1.begin() + pos, vec1.end(), vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);

This seems to be close to what we want, we only pay for an 'extra' n default constructors.

EDIT

My shift and copy method (3) was incorrect, it should be:

auto v1_size = vec1.size();
vec1.resize(vec1.size() + vec2.size());
std::move(vec1.begin() + pos, vec1.begin() + v1_size, vec1.begin() + pos + vec2.size());
std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);

TESTS ( updated with @VaughnCato's and @ViktorSehr's methods)

I tested methods 1 & 3 (method 2 is clearly not going to perform well - easy to verify), along with the methods suggested by @VaughnCato and @ViktorSehr. Here is the full code:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cstdint>
#include <chrono>
#include <numeric>
#include <random>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/adaptor/transformed.hpp>

using std::size_t;

std::vector<int> generate_random_ints(size_t n)
{
    std::default_random_engine generator;
    auto seed1 = std::chrono::system_clock::now().time_since_epoch().count();
    generator.seed((unsigned) seed1);
    std::uniform_int_distribution<int> uniform {};
    std::vector<int> v(n);
    std::generate_n(v.begin(), n, [&] () { return uniform(generator); });
    return v;
}

std::vector<std::string> generate_random_strings(size_t n)
{
    std::default_random_engine generator;
    auto seed1 = std::chrono::system_clock::now().time_since_epoch().count();
    generator.seed((unsigned) seed1);
    std::uniform_int_distribution<int> uniform {};
    std::vector<std::string> v(n);
    std::generate_n(v.begin(), n, [&] () { return std::to_string(uniform(generator)); });
    return v;
}

template <typename D=std::chrono::nanoseconds, typename F>
D benchmark(F f, unsigned num_tests)
{
    D total {0};
    for (unsigned i = 0; i < num_tests; ++i) {
        auto start = std::chrono::system_clock::now();
        f();
        auto end = std::chrono::system_clock::now();
        total += std::chrono::duration_cast<D>(end - start);
    }
    return D {total / num_tests};
}

template <typename T1, typename T2, typename UnaryOperation>
void temp_transform(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
    std::vector<T1> temp {};
    temp.reserve(vec2.size());
    std::transform(vec2.begin(), vec2.end(), std::back_inserter(temp), op);
    vec1.insert(vec1.begin() + pos, std::make_move_iterator(temp.begin()),
                std::make_move_iterator(temp.end()));
}

template <typename T1, typename T2, typename UnaryOperation>
void shift_copy(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
    auto v1_size = vec1.size();
    vec1.resize(vec1.size() + vec2.size());
    std::move(vec1.begin() + pos, vec1.begin() + v1_size, vec1.begin() + pos + vec2.size());
    std::transform(vec2.begin(), vec2.end(), vec1.begin() + pos, op);
}

template <typename T1, typename T2, typename UnaryOperation>
void boost_transform(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
    auto v2_begin = boost::make_transform_iterator(vec2.begin(), op);
    auto v2_end   = boost::make_transform_iterator(vec2.end(), op);
    vec1.insert(vec1.begin() + pos, v2_begin, v2_end);
}

template <typename T1, typename T2, typename UnaryOperation>
void boost_adapter(std::vector<T1> vec1, const std::vector<T2> &vec2, size_t pos, UnaryOperation op)
{
   auto transformed_range = vec2 | boost::adaptors::transformed(op);
   vec1.insert(vec1.begin() + pos, transformed_range.begin(), transformed_range.end());
}

int main(int argc, char **argv)
{
    unsigned num_tests {1000};
    size_t vec1_size {1000000};
    size_t vec2_size {1000000};
    size_t insert_pos {vec1_size / 2};

    // Switch the variable names to inverse test
    auto vec2 = generate_random_ints(vec1_size);
    auto vec1 = generate_random_strings(vec2_size);

    //auto op = [] (const std::string& str) { return std::stoi(str); };
    auto op = [] (int i) { return std::to_string(i); };

    auto f_temp_transform_insert = [&vec1, &vec2, &insert_pos, &op] () {
        temp_transform(vec1, vec2, insert_pos, op);
    };
    auto f_shift_copy_insert = [&vec1, &vec2, &insert_pos, &op] () {
        shift_copy(vec1, vec2, insert_pos, op);
    };
    auto f_boost_transform_insert = [&vec1, &vec2, &insert_pos, &op] () {
        boost_transform(vec1, vec2, insert_pos, op);
    };
   auto f_boost_adapter_insert = [&vec1, &vec2, &insert_pos, &op] () {
       boost_adapter(vec1, vec2, insert_pos, op);
   };

    auto temp_transform_insert_time  = benchmark<std::chrono::milliseconds>(f_temp_transform_insert, num_tests).count();
    auto shift_copy_insert_time      = benchmark<std::chrono::milliseconds>(f_shift_copy_insert, num_tests).count();
    auto boost_transform_insert_time = benchmark<std::chrono::milliseconds>(f_boost_transform_insert, num_tests).count();
    auto boost_adapter_insert_time   = benchmark<std::chrono::milliseconds>(f_boost_adapter_insert, num_tests).count();

    std::cout << "temp_transform: " << temp_transform_insert_time << "ms" << std::endl;
    std::cout << "shift_copy: " << shift_copy_insert_time << "ms" << std::endl;
    std::cout << "boost_transform: " << boost_transform_insert_time << "ms" << std::endl;
    std::cout << "boost_adapter: " << boost_adapter_insert_time << "ms" << std::endl;

    return 0;
}

RESULTS

Compiled with:

g++ vector_insert.cpp -std=c++11 -O3 -o vector_insert_test

The mean user-runtimes are:

|    Method   | std::string -> int (ms) | int -> std::string (ms) |
|:-----------:|:-----------------------:|:-----------------------:|
| 1           |            68           |           220           |
| 3           |            67           |           222           |
| @VaughnCato |            71           |           239           |
| @ViktorSehr |            72           |           236           |

TLDR

  • The boost methods are not as fast as the std::transform methods.
  • The std::transform methods are almost equally good - although there is a difficult to interpret discrepancy between int -> std::string and std::string -> int performance.
Community
  • 1
  • 1
Daniel
  • 8,179
  • 6
  • 31
  • 56
1

@VaughnCato's approach of using boost::transform_iterator for your other question should work well for this one also:

auto vec1begin = boost::make_transform_iterator(vec1.begin(), f);
auto vec1end = boost::make_transform_iterator(vec1.end(), f);
vec2.insert(middle, vec1begin, vec1end);
Community
  • 1
  • 1
Chris Drew
  • 14,926
  • 3
  • 34
  • 54
0

How about using boost::range::adaptors::transformed ? 

std::vector<...> first_vector;
auto transform_functor = [](...){...};
auto transformed_range = first_vector | boost::adaptors::transformed(transform_functor):
some_vector.insert(some_vector.end(), transformed_range.begin(), transformed_range.end());

Given that boost::transform and the vector::insert function is implemented as clever as possible, this ought to be able to ignore any unnessesary capacity checks.

Viktor Sehr
  • 12,825
  • 5
  • 58
  • 90
  • I can't seem to get this method to work (see the edit in my answer), if you can point out where I'm going wrong I'll update the results to include your method. – Daniel Feb 17 '15 at 14:20
  • your method is working now... it doesn't perform as well as the STL methods. – Daniel Feb 17 '15 at 18:14
  • Well in a perfect world it should be the optimal way, but I guess unnessesary cycles are added somewhere in the transform operation with a transform range. – Viktor Sehr Feb 17 '15 at 23:21