selfjungle Just another WordPress weblog

22Aug/090

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.

Tagged as: No Comments
18Aug/090

qdict new release r20

New features:

  • Search strategies
  • Links to external links (google, wordreference) if no match found
  • Copy the text from clipboard to the entry-combobox on startup

Download:
Source code: qdict_r20.tar.bz2

Link:
Check the "project page" for screenshots and more info: qdict

Tagged as: , No Comments
14Aug/090

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

Tagged as: No Comments
12Aug/090

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

Tagged as: No Comments
12Aug/090

String templates with Perl

Here is a nice thing with perl.

  1. You have a string template, like an e-mail, with fields to change.
  2. This fields are stored in a CVS file.
  3. Perl changes this fields with hashes and regular expressions in no time.

Note: the field names are the keys in the hash, lines of the CVS are an array with hash refs.

#!/usr/bin/perl

use warnings;
use strict;

my @data = ();

# data.csv:
# bela,fired
# julcsi,killed
# jani,promoted

my $string_template = <<EOF;
Dear <name>,
   You have been <action>.
Br: Someone.
EOF

# CSV to hash
open FILE, "data.csv" or die $!;
while (my $line = ) {
    my %temp_hash = ();
    ($temp_hash{"name"}, $temp_hash{"action"}) = split (",", $line);
    chomp $temp_hash{"action"};
    push @data, \%temp_hash;
}
close FILE;

# replace & print
foreach (@data) {
    my $s = $string_template;
    $s=~s/<(.*?)>/$$_{$1}/g;
    print "$s\n";
}
Tagged as: No Comments
12Aug/090

qdict new release r19

New release of qdict, (r19 - as it's the 19th commit in SVN)

Changes:

  • Completer-aided input combobox (for gcide)
  • Better parsing (for gcide)

Download:
Source code: qdict_r19.tar.bz2

Link:
Check the "project page" for screenshots and more info: qdict

Tagged as: , No Comments