Exponential growth policy of std::vector

Once std::vector is filled (size() equals to capacity()), a subsequent push_back(…) results in an exponential expansion of the vector capacity. The following table shows that the expansion happens when the index reaches a power of two:

index: 0, capacity: 1, address: 0x1fa6c20
index: 1, capacity: 2, address: 0x1fa6c40
index: 2, capacity: 4, address: 0x1fa6c20
index: 4, capacity: 8, address: 0x1fa6c60
index: 8, capacity: 16, address: 0x1fa6c90
index: 16, capacity: 32, address: 0x1fa6ce0
index: 32, capacity: 64, address: 0x1fa6d70
index: 64, capacity: 128, address: 0x1fa6e80
index: 128, capacity: 256, address: 0x1fa7090
index: 256, capacity: 512, address: 0x1fa74a0
index: 512, capacity: 1024, address: 0x1fa7cb0
index: 1024, capacity: 2048, address: 0x1fa8cc0
index: 2048, capacity: 4096, address: 0x1faacd0
index: 4096, capacity: 8192, address: 0x1faece0
index: 8192, capacity: 16384, address: 0x1fb6cf0
index: 16384, capacity: 32768, address: 0x1fc6d00
index: 32768, capacity: 65536, address: 0x1fe6d10
index: 65536, capacity: 131072, address: 0x2026d20
index: 131072, capacity: 262144, address: 0x20a6d30
index: 262144, capacity: 524288, address: 0x21a6d40
index: 524288, capacity: 1048576, address: 0x23a6d50
index: 1048576, capacity: 2097152, address: 0x27a6d60
index: 2097152, capacity: 4194304, address: 0x2fa6d70
index: 4194304, capacity: 8388608, address: 0x7f8e9225f010
index: 8388608, capacity: 16777216, address: 0x7f8e8e25e010
index: 16777216, capacity: 33554432, address: 0x7f8e8625d010
index: 33554432, capacity: 67108864, address: 0x7f8e7625c010
index: 67108864, capacity: 134217728, address: 0x7f8e5625b010
index: 134217728, capacity: 268435456, address: 0x7f8e1625a010
index: 268435456, capacity: 536870912, address: 0x7f8d96259010
index: 536870912, capacity: 1073741824, address: 0x7f8c96258010

(more…)

How to erase an element with a reverse iterator from C++ container

The following C++ code demonstrates how to erase an element a reverse iterator points to:

#include <iostream>
#include <set>
#include <vector>
#include <assert.h>

int main()
{
	std::set<int> set;

	set.insert(15);

	std::cout << set.size() << " ";

	auto ri = set.rbegin();

	auto i1 = --ri.base();

	auto i2 = --set.end();

	assert(i1 == i2);

	set.erase(i1);

	std::cout << set.size() << std::endl;
}

The output is ‘0 1’. The key point here is that the reverse iterator is an adaptor for reverse-order traversal that can be created from forward iterator with std::make_reverse_iterator.

An example of how GCC thread sanitizer works.

The following simple code C++ example can be used for investigation of how GCC thread sanitizer works:

#include <mutex>
#include <atomic>
#include <iostream>
#include <thread>

std::mutex mutex;
int a = 3;
const size_t size = 1000 * 1000;
std::atomic<int> b(1);

void testA()
{
	for (size_t counter = 0; counter < size; counter++)
	{
		++b;
		std::unique_lock<std::mutex> lock(mutex);
		++a;
	}
}

void testB()
{
	for (size_t counter = 0; counter < size; counter++)
	{
		--b;
		std::unique_lock<std::mutex> lock(mutex);
		--a;
	}
}

int main()
{
	std::thread t1(testA);
	std::thread t2(testB);
	t1.join();
	t2.join();
}

(more…)

Multiple views with OsgQtQuick

I wrote a sample application using OsgQtQuick that shows the Earth in two views:

with the following QML, that I copied from OsgQtQuick samples:

(more…)

A sample C++ code demonstrating why int is not atomic

The code below demonstrates why it is not guaranteed that 4-byte value being written by another thread is read either as original or final, but it can be read “partially written”:

static constexpr int offset=2;
alignas(64) char vars[64+4-offset];
static volatile unsigned * const p = reinterpret_cast<unsigned *>(&vars[64-offset]);

unsigned getVar()
{
    return *p;
}

void loop()
{
    while(true)
    {
        *p = -1;
        *p = 0;
    }
}

#include <thread>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <map>

int main()
{
    std::thread thread(loop);
    std::map<unsigned,int> xs;
    for(int i=0;i<10000000;++i)
    {
        const auto x=getVar();
        ++xs[x];
    }
    for(const auto& x : xs)
        std::cout << std::setfill('0') << std::setw(8) << std::hex << x.first << ": " << std::dec << x.second << " times\n";
    std::exit(0); // exit, killing the thread without abnormal termination via std::terminate
}

(more…)

Compiling the latest version of CMake from sources on Ubuntu

I was unable to add QML resources to a QT Quick application with CMake 2.8 installed on my machine, so I built the latest version of CMake with the following commands:

cd ~/examples
mkdir tools
cd tools
mkdir install
tar -xf ~/Downloads/cmake-3.9.1.tar.gz
cd cmake-3.9.1/
./configure --prefix=/home/dmitry/examples/tools/install/
make -j4
make install

Now my QT application is compiled and run successfully:

~/examples/tools/install/bin/cmake ../../OsgQmlTest/ -DCMAKE_BUILD_TYPE=Debug -DCMAKE_MODULE_PATH=/home/user/3rdpart/osg/CMakeModules/ -DCMAKE_INSTALL_PREFIX=/home/dmitry/examples/install
make -j4
make install

(more…)

Building OsgQtQuick on Ubuntu 14.04

The following section in OsgQtQuick‘s CMakeLists.txt:

find_package(OpenSceneGraph 3.0 REQUIRED
  osg
  osgQt
  osgDB
  osgGA
  osgManipulator
  osgUtil
  osgViewer
  osgText)

results in CMake searching for FindOpenSceneGraph.cmake file:

strace cmake ../../osgqtquick/ -DCMAKE_BUILD_TYPE=Debug -DCMAKE_INSTALL_PREFIX=/home/dmitry/examples/install |& grep -i OpenSceneGraph
access("/home/dmitry/examples/osgqtquick/cmake/FindOpenSceneGraph.cmake", R_OK) = -1 ENOENT (No such file or directory)
access("/usr/share/cmake-2.8/Modules/FindOpenSceneGraph.cmake", R_OK) = 0
access("/usr/share/cmake-2.8/Modules/FindOpenSceneGraph.cmake", R_OK) = 0
stat("/usr/share/cmake-2.8/Modules/FindOpenSceneGraph.cmake", {st_mode=S_IFREG|0644, st_size=7438, ...}) = 0
open("/usr/share/cmake-2.8/Modules/FindOpenSceneGraph.cmake", O_RDONLY) = 3
read(3, "# - Find OpenSceneGraph\n# This m"..., 8192) = 7438
read(3, "/* -*-c++-*- OpenSceneGraph - Co"..., 4096) = 3495
read(3, "/* -*-c++-*- OpenSceneGraph - Co"..., 8191) = 3495
  Could NOT find OpenSceneGraph (missing: OPENSCENEGRAPH_LIBRARIES
  OPENSCENEGRAPH_INCLUDE_DIR OSG_FOUND OSGQT_FOUND OSGDB_FOUND OSGGA_FOUND
  /usr/share/cmake-2.8/Modules/FindOpenSceneGraph.cmake:187 (FIND_PACKAGE_HANDLE_STANDARD_ARGS)
access("/usr/share/cmake-2.8/Modules/FindOpenSceneGraph.cmake", R_OK) = 0

(more…)

Qt Quick Controls 2 does not support TableView

Qt Quick Controls 2 does not support TableView and looks like they are not going to support it, some notable missing features from Qt Quick Controls 1 also are Action, SplitView and TreeView, so the following QML code would not work:

TableView {

    TableViewColumn {
        role: "time"
        title: qsTr("date/time:")
        width: parent.width - 30
    }

    TableViewColumn {
        role: "score"
        title: qsTr("result:")
        width: 30
    }

    model: boardModel.list

    ScrollIndicator.vertical: ScrollIndicator { }
}

But there is a solution with ListView, so there can be something like this:

(more…)

Running Mac OS X with Virtual Box

I successfully installed Mac OS X Snow Leopard on Virtual Box using iBoot. iBoot requires “Enable EFI …” to be unchecked:

(more…)

Numeric promotions and conversions in C++

In the following C++ code the values of ‘z’ and ‘n’ are undefined, because they are the result of an operation with signed integer arithmetic overflow (‘x’ and ‘y’ are first implicitly converted to signed int). The value of ‘w’ is implementation defined, because it is the result of a conversion:

#include <iostream>
#include <bitset>

int main(int argc, char *argv[])
{
    unsigned short x = 65535, y = x;
    unsigned short z = x * y;
    unsigned int n = x * y;
    std::cerr << "z = " << std::bitset<16>(z) << ", n = " << std::bitset<32>(n) << ", sizeof(int) = " << sizeof(int) << std::endl;

    short w = 0x80000000;
    
    return 0;
}

see Numeric conversions section of Implicit conversions article.