By now everyone should know std::vector<T> beats std::list<T> at pretty much everything.
But splicing one container into another is std::list‘s specialty.
Here’s a rather long but complete framework to test the idea, copy-and-paste ready:
#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
#include <string>
#include <type_traits>
#include <vector>
static const std::size_t Trials = 100;
static const bool PreallocateVector = false;
template <typename T>
void use(const volatile T& x)
{
char c = reinterpret_cast<const volatile char&>(x);
(void)c;
}
template <typename Container>
void touch_up_container(Container&)
{
// do nothing
}
template <typename T, typename Alloc>
void touch_up_container(std::vector<T, Alloc>& vec)
{
if (PreallocateVector)
vec.reserve(vec.size() * 2);
}
template <typename T, typename Alloc>
std::list<T, Alloc>
combine(
std::list<T, Alloc>&& first,
std::list<T, Alloc>&& second
)
{
std::list<T, Alloc> result = std::move(first);
result.splice(result.end(), std::move(second));
return result;
}
template <typename T, typename Alloc>
std::vector<T, Alloc>
combine(
std::vector<T, Alloc>&& first,
std::vector<T, Alloc>&& second
)
{
std::vector<T, Alloc> result = std::move(first);
result.insert(
result.end(),
std::make_move_iterator(second.begin()),
std::make_move_iterator(second.end())
);
return result;
}
template <typename Container>
double test(Container first, Container second)
{
const auto startTime = std::chrono::high_resolution_clock::now();
// combine the two containers, use result
Container result = combine(std::move(first), std::move(second));
use(result);
const auto endTime = std::chrono::high_resolution_clock::now();
const auto duration = endTime - startTime;
const auto seconds = std::chrono::duration<double>(duration);
return seconds.count();
}
template <typename Container, typename Func>
Container generate_container(const std::size_t size, Func dataSource)
{
Container result;
std::generate_n(std::back_inserter(result), size, dataSource);
return result;
}
template <typename Container, typename Func>
double test_container(const std::size_t size, Func dataSource)
{
const auto generateContainer =
[&]{ return generate_container<Container>(size, dataSource); };
auto sourceA = generateContainer(), sourceB = generateContainer();
double sum = 0.0;
for (std::size_t trial = 0; trial < Trials; ++trial)
{
auto testSourceA = sourceA, testSourceB = sourceB;
// optionally preallocate vector (note: not timed)
touch_up_container(testSourceA);
touch_up_container(testSourceB);
sum += test(std::move(testSourceA), std::move(testSourceB));
}
return sum / static_cast<double>(Trials);
}
template <typename T, typename Func>
void test_containers(const std::size_t size, Func dataSource)
{
std::cout << "Testing containers of size " << size
<< " with " << (std::is_pod<T>::value ? "pod" : "non-pod")
<< " objects of size " << sizeof(T)
<< "..." << std::endl;
std::cout << "Testing std::vector<T>..." << std::endl;
const double vecTime = test_container<std::vector<T>>(size, dataSource);
std::cout << "Testing std::list<T>..." << std::endl;
const double listTime = test_container<std::list<T>>(size, dataSource);
const char* winner;
double winnerPercent;
if (vecTime < listTime)
{
winner = "std::vector<T> wins";
winnerPercent = 100 * (listTime / vecTime);
}
else if (listTime < vecTime)
{
winner = "std::list<T> wins";
winnerPercent = 100 * (vecTime / listTime);
}
else
{
winner = "tie";
winnerPercent = 0.0;
}
std::cout << "Times:\n"
<< "\tstd::vector<T>: " << vecTime << '\n'
<< "\tstd::list<T>: " << listTime << '\n'
<< "\t" << winner << " (" << winnerPercent << "% faster)\n"
<< std::endl;
}
template <typename T, typename Func>
void test_container_sizes(Func dataSource)
{
const std::size_t testSizes[] =
{
4, 256, 4096, 65536, 2097152,
};
for (const auto size : testSizes)
test_containers<T>(size, dataSource);
}
struct small_pod
{
char data[sizeof(std::string)];
static small_pod create()
{
small_pod result;
std::fill(std::begin(result.data), std::end(result.data), 0);
return result;
}
};
struct big_pod
{
int r, g, b, a;
double x, y, z, w;
static big_pod create()
{
big_pod result;
result.r = std::rand();
result.g = std::rand();
result.b = std::rand();
result.a = std::rand();
result.x = static_cast<double>(std::rand());
result.y = static_cast<double>(std::rand());
result.z = static_cast<double>(std::rand());
result.w = static_cast<double>(std::rand());
return result;
}
};
struct small_nonpod
{
std::string data;
static small_nonpod create()
{
small_nonpod result;
result.data = "abcdefghijklmnopqrstuvwxyz";
return result;
}
};
struct big_nonpod
{
big_pod data;
std::string otherdata;
static big_nonpod create()
{
big_nonpod result;
result.data = big_pod::create();
result.otherdata = "abcdefghijklmnopqrstuvwxyz";
return result;
}
};
int main()
{
test_container_sizes<char>(std::rand);
test_container_sizes<std::intmax_t>(std::rand);
test_container_sizes<small_pod>(small_pod::create);
test_container_sizes<small_nonpod>(small_nonpod::create);
test_container_sizes<big_pod>(big_pod::create);
test_container_sizes<big_nonpod>(big_nonpod::create);
std::cout << "\n\nDone" << std::endl;
}
And some example output. For reference, my machine is 12-core (note: the program is single-threaded) Intel Xeon E5-1650 3.20GHz, 16GB RAM:
Testing containers of size 4 with pod objects of size 1... Testing std::vector... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 256 with pod objects of size 1... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 4096 with pod objects of size 1... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 65536 with pod objects of size 1... Testing std::vector ... Testing std::list ... Times: std::vector : 2.002e-005 std::list : 0 std::list wins (inf% faster) Testing containers of size 2097152 with pod objects of size 1... Testing std::vector ... Testing std::list ... Times: std::vector : 0.0013114 std::list : 0 std::list wins (inf% faster) Testing containers of size 4 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 256 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 4096 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 65536 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0.00027024 std::list : 0 std::list wins (inf% faster) Testing containers of size 2097152 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0.0109292 std::list : 0 std::list wins (inf% faster) Testing containers of size 4 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 256 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 4096 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 65536 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0.00028018 std::list : 0 std::list wins (inf% faster) Testing containers of size 2097152 with pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0.0106587 std::list : 0 std::list wins (inf% faster) Testing containers of size 4 with non-pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 256 with non-pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 4.003e-005 std::list : 0 std::list wins (inf% faster) Testing containers of size 4096 with non-pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0.00059051 std::list : 0 std::list wins (inf% faster) Testing containers of size 65536 with non-pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0.0104887 std::list : 0 std::list wins (inf% faster) Testing containers of size 2097152 with non-pod objects of size 8... Testing std::vector ... Testing std::list ... Times: std::vector : 0.4064 std::list : 0 std::list wins (inf% faster) Testing containers of size 4 with pod objects of size 48... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 256 with pod objects of size 48... Testing std::vector ... Testing std::list ... Times: std::vector : 1.001e-005 std::list : 0 std::list wins (inf% faster) Testing containers of size 4096 with pod objects of size 48... Testing std::vector ... Testing std::list ... Times: std::vector : 5.006e-005 std::list : 0 std::list wins (inf% faster) Testing containers of size 65536 with pod objects of size 48... Testing std::vector ... Testing std::list ... Times: std::vector : 0.00211195 std::list : 0 std::list wins (inf% faster) Testing containers of size 2097152 with pod objects of size 48... Testing std::vector ... Testing std::list ... Times: std::vector : 0.066437 std::list : 0 std::list wins (inf% faster) Testing containers of size 4 with non-pod objects of size 56... Testing std::vector ... Testing std::list ... Times: std::vector : 0 std::list : 0 tie (0% faster) Testing containers of size 256 with non-pod objects of size 56... Testing std::vector ... Testing std::list ... Times: std::vector : 2.001e-005 std::list : 0 std::list wins (inf% faster) Testing containers of size 4096 with non-pod objects of size 56... Testing std::vector ... Testing std::list ... Times: std::vector : 0.00085074 std::list : 0 std::list wins (inf% faster) Testing containers of size 65536 with non-pod objects of size 56... Testing std::vector ... Testing std::list ... Times: std::vector : 0.0130311 std::list : 0 std::list wins (inf% faster) Testing containers of size 2097152 with non-pod objects of size 56... Testing std::vector ... Testing std::list ... Times: std::vector : 0.533389 std::list : 0 std::list wins (inf% faster) Done
std::list<T> never loses.
This isn’t surprising, but it should settle any small disputes. 😉 All std::list has to do is shuffle some pointers around, while std::vector has to allocate memory for both containers, then copy both to the new storage. (Even if the memory is preallocated, this second copying still takes a bit of time. Preallocating the destination buffer shaves off about 50%.)
This all said, unless you find:
- You can or need to populate both lists at separate times, and
- Need to combine them, and
- Aren’t going to lose against
std::vectorduring processing anyway
std::list<T> should stay out of sight. It is possible to mitigate the main issue (#3) with std::list<T>, cache coherency, with a custom allocator, but that’s even more work.
(As always, if you want to fix your performance issues: profile it.)