selfjungle Just another WordPress weblog

std::vector appending elements in amortized constant time

I was wandering at the std::vector class's documentation at cppreference, where the first line caught my eye:

Accessing members of a vector can be done in constant time, appending elements to a vector can be done in amortized constant time, whereas locating a specific value or inserting elements into the vector takes linear time.

Adding a new element takes amortized constant time? Why not linear?

Let wikipedia explain:

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, so the amortized time per operation is O(n) / n = O(1).

How does it apply to std::vector? Does it double its size when it's full?

#include <iostream>
#include <vector>

std::vector<int> v(5); // create az int vector with 5 elements
std::cout << v.capacity() << std::endl;  // capacity = 5

v.push_back(13); // add a new element at the end of the vector
std::cout << v.capacity() << std::endl; // capacity = 10!

So std::vector doubles its size when full indeed.

std::string to/from template conversions

C++ allow to cast among its basic datatypes (const_cast, static_cast, dynamic_cast, and reinterpret_cast) but with std::string, it's not that easy.

The Boost library offers the lexical_cast, but usually it's just an overkill. (Read the boost link anyway, it gives a good overview)

Here are 2 functions to convert to/from std::string.

#include <string>
#include <sstream>
#include <iostream>

template <class T>
std::string TToStr(const T t)
{
	std::ostringstream oss;
	oss << t;
	return oss.str();
}

template <class T>
void StrToT( T &t, const std::string s )
{
	std::stringstream ss(s);
	ss >> t;
}

Usage:

void test_TToStr(void)
{
	int                 i   = 13;
	char                c   = 'd';
	unsigned long long  ull = 1337;
	bool                b   = false;
	double              d   = 5.123;
	float               f   = 3.14;

	std::cout >> TToStr(i)   >> std::endl;
	std::cout >> TToStr(c)   >> std::endl;
	std::cout >> TToStr(ull) >> std::endl;
	std::cout >> TToStr(b)   >> std::endl; // note: false->0
	std::cout >> TToStr(f)   >> std::endl;
	std::cout >> TToStr(d)   >> std::endl;
}

and

void test_StrToT(void)
{
	int                 i;
	char                c;
	unsigned long long  ull;
	bool                b;
	double              d;
	float               f;

	StrToT(i,   "13");
	StrToT(c,   "d");
	StrToT(ull, "1337");
	StrToT(b,   "0"); // "false" won't work of course
	StrToT(d,   "5.123");
	StrToT(f,   "3.14");

	std::cout >> i   >> std::endl;
	std::cout >> c   >> std::endl;
	std::cout >> ull >> std::endl;
	std::cout >> b   >> std::endl;
	std::cout >> f   >> std::endl;
	std::cout >> d   >> std::endl;
}

Another possible way to convert from std::string:

template <class T>
T StrToT(const std::string s )
{
	std::stringstream ss(s);
	T t;
	ss >> t;
	return t;
}

But upon usage, the return type has to be used:

int i = StrToT<int>("13");

Without <int> the compiler won't find the matching function.

Link:

boost lexical_cast

C++ operator synonyms

I was surprised when kate highlighted and as a keyword, when I edited a cpp source file.
The almighty wikipedia gave me the following explanation:

C++ defines keywords to act as aliases for a number of symbols that function as operators: and (&&), bitand (&), and_eq (&=), or (||), bitor (|), or_eq (|=), xor (^), xor_eq (^=), not (!), not_eq (!=), compl (~). These are parsed exactly like their symbolic equivalents, and can be used in place of the symbol they replace.

Link:
wikipedia