This example I hope illustrates the O(lg N) time complexity of segmented_array::push_front():
struct timer
{
timer(const char* message)
{
std::cout << message;
QueryPerformanceCounter(&iStartTime);
}
~timer()
{
LARGE_INTEGER endTime;
QueryPerformanceCounter(&endTime);
LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
std::cout.precision(4);
std::cout << std::fixed << (float)(endTime.QuadPart
- iStartTime.QuadPart)/(float)freq.QuadPart << " seconds" << std::endl;
}
LARGE_INTEGER iStartTime;
};
int main()
{
neolib::segmented_array<int> sa1;
neolib::segmented_array<int> sa2;
std::vector<int> v1;
std::vector<int> v2;
{
timer time("30000 calls to segmented_array<int>::push_front() takes ");
for (int i = 0; i < 30000; ++i)
sa1.push_front(i);
}
{
timer time("60000 calls to segmented_array<int>::push_front() takes ");
for (int i = 0; i < 60000; ++i)
sa2.push_front(i);
}
{
timer time("30000 calls to std::vector<int>::insert(begin()) takes ");
for (int i = 0; i < 30000; ++i)
v1.insert(v1.begin(), i);
}
{
timer time("60000 calls to std::vector<int>::insert(begin()) takes ");
for (int i = 0; i < 60000; ++i)
v2.insert(v2.begin(), i);
}
return 0;
}
The output of which is:
30000 calls to segmented_array<int>::push_front() takes 0.0088 seconds 60000 calls to segmented_array<int>::push_front() takes 0.0181 seconds 30000 calls to std::vector<int>::insert(begin()) takes 0.1838 seconds 60000 calls to std::vector<int>::insert(begin()) takes 0.7617 seconds
As can be seen if the number of iterations is doubled the time is also approximately doubled for the segmented_array case which would be expected given an complexity of O(lg N).
N.B. If the only insertion/removal operations being performed are the front operations push_front() and pop_front() then std::deque should be used instead of segmented_array as std::deque is the optimal choice for such operations.