This example I hope illustrates the O(1) 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()
{
lib::segmented_array<int> sa1;
lib::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.0599 seconds
60000 calls to segmented_array<int>::push_front() takes 0.1259 seconds
30000 calls to std::vector<int>::insert(begin()) takes 4.8061 seconds
60000 calls to std::vector<int>::insert(begin()) takes 19.2947 seconds
As can be seen if the number of iterations is doubled the time is also doubled for the segmented_array case which implies O(1) but is quadrupled for the std::vector case which implies O(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.