When using STL element containers, selecting the container type that suits the intended use is of major importance for the processing speed. If the amount of read operations significantly exceeds the amount of write operations, it is worth using std::set compared to std::vector.
Introduction
I use the STL containers library template class std::vector<IMAGMANIPULATION> for the UndoRedoAction class in my basic Icon Editor running on ReactOS (and consequently on Windows XP and newer versions) and have achieved unacceptably bad response times with it for a particular use case - scale image sections. Since the action type of IMAGMANIPULATION in combination with the pixel coordinate represents a unique, immutable and, above all, sortable key, I first searched for a sorted vector container and came across the balanced binary tree container std::set<...>.
For my specific test case, scaling 45 x 45 pixels up to 133%, this pushed the response time from more than 10 seconds to less than 1 second.
Background
If you add an undo/redo capability into your application, sooner or later, you will come to a point where you want to combine multiple atomic manipulations into one UndoRedoAction. Real examples from my basic Icon Editor running on ReactOS (and consequently on Windows XP and newer versions) are:
- I fill contiguous pixels of one color with another color.
- I scale up/down an image area.
In both cases, several pixels are manipulated (atomic manipulations) at once, which should be combined in a single UndoRedoAction. And thus these atomic manipulations must be stored in a container.
While the solution I chose in the first case (fill contiguous pixels) only performs write operations (because with the color and the mask of the pixel, the algorithm has a unique criterion available to unambiguously recognize whether the pixel is still waiting to be processed), the solution in the second case (scale up/down) mainly performs read operations (because the algorithm has no unique criterion available to unambiguously recognize whether the pixel is still waiting to be processed). These read operations are about checking whether a manipulated pixel is already registered in the UndoRedoAction.
And this is where the std::set<...> balanced binary tree container with a runtime behavior O(log(n)) plays its advantages against the std::vector<...> sequence container with a runtime behavior O(n). I admit I only had a quick look at the container classes of the STL and spontaneously decided on one container class. I found the resulting runtime improvement good enough to dispense with further tests - e.g. with std::map<...>.
Update: In the "Comments and Discussions" section (below the tip), there is a comment "You can do better..." by SeattleC++ (31-May-21 21:19) that discusses possible alternatives in more detail. I would like to mention it here with pleasure.
However, a switch to std::set<...> also has disadvantages - the original order of the atomic manipulations gets lost. And so I didn't have the courage to change my whole UndoRedoAction class to std::set<...> and currently support both std::set<...> and std::vector<...>.
Using the Code
Let's first take a look at the possible types of atomic manipulation and the structure I use for storing an atomic manipulation in my CPixelEditUndoRedoAction class.
class CPixelEditUndoRedoAction
{
public:
static const int PIXEL_MANIPULATION = 0;
static const int PALETTE_MANIPULATION = 1;
public:
typedef struct IMAGMANIPULATIONtag
{
public:
int ManipulationType;
LONG ColumnOrPalIdx;
LONG Row;
DWORD OldColIdxOrRef;
DWORD NewColIdxOrRef;
bool OldMask;
bool NewMask;
} IMAGMANIPULATION, * LPIMAGMANIPULATION;
...
Thus, an instance of IMAGMANIPULATION can represent an atomic manipulation of one pixel or of one entry in the color palette.
Since std::set<...> is a sorted container, a compare function is needed. The compare function must ensure that the elements can be sorted and that two elements are recognized as equal if !compare(a, b) && !compare(b, a) is valid.
...
private:
typedef struct IMAGMANIPULATION_COMPAREtag
{
bool operator()(const IMAGMANIPULATION& lhs, const IMAGMANIPULATION& rhs) const
{
if (lhs.ManipulationType < rhs.ManipulationType)
return true;
if (lhs.ManipulationType > rhs.ManipulationType)
return false;
if (lhs.ColumnOrPalIdx < rhs.ColumnOrPalIdx)
return true;
if (lhs.ColumnOrPalIdx > rhs.ColumnOrPalIdx)
return false;
if (lhs.Row < rhs.Row)
return true;
return false;
}
} IMAGMANIPULATION_COMPARE;
...
Now we can create element containers based on std::vector<...> (slow and preserving the original order of the elements) and std::set<...> (fast by sorting the elements).
...
private:
bool _bSorted = false;
std::vector<IMAGMANIPULATION> _aPixelActionsVec;
std::set<IMAGMANIPULATION, IMAGMANIPULATION_COMPARE> _aPixelActionsSet;
...
Two auxiliary functions simplify the initialization of the IMAGMANIPULATION structure.
...
private:
static inline void SetPixelManipulation(IMAGMANIPULATION& im, LONG lCol, LONG lRow,
DWORD dwOldColIdxOrRef, DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask)
{
im.ManipulationType = PIXEL_MANIPULATION;
im.ColumnOrPalIdx = lCol;
im.Row = lRow;
im.OldColIdxOrRef = dwOldColIdxOrRef;
im.NewColIdxOrRef = dwNewColIdxOrRef;
im.OldMask = bOldMask;
im.NewMask = bNewMask;
}
static inline void SetPaletteManipulation(IMAGMANIPULATION& im, BYTE byPaletteIndex,
DWORD dwOldColIdxOrRef, DWORD dwNewColIdxOrRef)
{
im.ManipulationType = PALETTE_MANIPULATION;
im.ColumnOrPalIdx = (LONG)byPaletteIndex;
im.Row = 0;
im.OldColIdxOrRef = dwOldColIdxOrRef;
im.NewColIdxOrRef = dwNewColIdxOrRef;
im.OldMask = false;
im.NewMask = false;
}
...
And now the constructors for my CPixelEditUndoRedoAction class. Since all class fields are auto variables, no explicit destructor is needed. The first constructor offers the possibility to use std::set<...> instead of std::vector<...> as element container via the argument bSorted.
...
private:
CPixelEditUndoRedoAction() { ; }
public:
inline CPixelEditUndoRedoAction(LONG lCol, LONG lRow, DWORD dwOldColIdxOrRef,
DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask, bool bSorted = false)
{
IMAGMANIPULATION im;
SetPixelManipulation(im, lCol, lRow, dwOldColIdxOrRef, dwNewColIdxOrRef,
bOldMask, bNewMask);
_bSorted = bSorted;
if (!_bSorted)
_aPixelActionsVec.push_back(im);
else
_aPixelActionsSet.insert(im);
}
inline CPixelEditUndoRedoAction(BYTE nPaletteIndex, DWORD dwOldColRef, DWORD dwNewColRef)
{
IMAGMANIPULATION im;
SetPaletteManipulation(im, nPaletteIndex, dwOldColRef, dwNewColRef);
_bSorted = false;
if (!_bSorted)
_aPixelActionsVec.push_back(im);
else
_aPixelActionsSet.insert(im);
}
...
Each UndoRedoAction can contain one or multiple atomic manipulations. The following two functions are used to add an atomic manipulation to an existing UndoRedoAction. At this point, the _bSorted field is already set and the new atomic manipulation is added to either std::set<...> or std::vector<...>.
...
inline IMAGMANIPULATION AddPixelManipulation(LONG nCol, LONG nRow, DWORD dwOldColIdxOrRef,
DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask)
{
IMAGMANIPULATION im;
SetPixelManipulation(im, nCol, nRow, dwOldColIdxOrRef, dwNewColIdxOrRef,
bOldMask, bNewMask);
if (!_bSorted)
_aPixelActionsVec.push_back(im);
else
_aPixelActionsSet.insert(im);
return im;
}
inline IMAGMANIPULATION AddPaletteManipulation(BYTE nPaletteIndex,
DWORD dwOldColRef, DWORD dwNewColRef)
{
IMAGMANIPULATION im;
SetPaletteManipulation(im, nPaletteIndex, dwOldColRef, dwNewColRef);
if (!_bSorted)
_aPixelActionsVec.push_back(im);
else
_aPixelActionsSet.insert(im);
return im;
}
...
The following function is used to override a registered atomic manipulation in an existing UndoRedoAction.
...
inline bool UpdatePixelManipulation(LONG lCol, LONG lRow, DWORD dwOldColIdxOrRef,
DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask)
{
if (!_bSorted)
{
for (auto it = _aPixelActionsVec.begin(); it != _aPixelActionsVec.end(); it++)
{
if (it->ManipulationType == PIXEL_MANIPULATION &&
it->ColumnOrPalIdx == lCol &&
it->Row == lRow)
{
it->NewColIdxOrRef = dwNewColIdxOrRef;
it->NewMask = bNewMask;
return true;
}
}
}
else
{
IMAGMANIPULATION im;
SetPixelManipulation(im, lCol, lRow, dwOldColIdxOrRef, dwNewColIdxOrRef,
bOldMask, bNewMask);
auto it = _aPixelActionsSet.find(im);
if (it != _aPixelActionsSet.end())
{
if (it->NewColIdxOrRef != dwNewColIdxOrRef ||
it->NewMask != bNewMask )
{
_aPixelActionsSet.erase(it);
_aPixelActionsSet.insert(im);
}
return true;
}
}
return false;
}
...
And finally the functions for Do (Redo) and Undo.
...
inline bool ExecuteAll(CPixelEdit* pEditor)
{
bool bResult = false;
if (!_bSorted)
{
std::vector<IMAGMANIPULATION>::const_iterator
cit = _aPixelActionsVec.cbegin();
for (; cit != _aPixelActionsVec.cend(); cit++)
{
bResult |= Execute(pEditor, *cit);
}
}
else
{
std::set< IMAGMANIPULATION, IMAGMANIPULATION_COMPARE>::const_iterator
cit = _aPixelActionsSet.cbegin();
for (; cit != _aPixelActionsSet.cend(); cit++)
{
bResult |= Execute(pEditor, *cit);
}
}
return bResult;
}
bool Execute(CPixelEdit* pEditor, IMAGMANIPULATION im);
inline bool RevertAll(CPixelEdit* pEditor)
{
bool bResult = false;
if (!_bSorted)
{
std::vector<IMAGMANIPULATION>::const_reverse_iterator
crit = _aPixelActionsVec.crbegin();
for (; crit != _aPixelActionsVec.crend(); crit++)
{
bResult |= Revert(pEditor, *crit);
}
}
else
{
std::set< IMAGMANIPULATION, IMAGMANIPULATION_COMPARE>::const_reverse_iterator
crit = _aPixelActionsSet.crbegin();
for (; crit != _aPixelActionsSet.crend(); crit++)
{
bResult |= Revert(pEditor, *crit);
}
}
return bResult;
}
bool Revert(CPixelEdit* pEditor, IMAGMANIPULATION im);
};
The Execute(...) and Revert(...) functions are very specific with respect to my CPixelEdit class, for which I introduced the CPixelEditUndoRedoAction class here.
Points of Interest
I have been using the STL containers library template class std::vector<...> for over 15 years in a commercial product built with Visual Studio. Two years ago, I upgraded the Platform Toolset for this product from v140 to v142 and noticed a significant improvement in runtime behavior. Until then, I was not completely convinced of the use of C++ template classes or STL, but this positive surprise changed my mind.
And also this time, when switching from std::vector<...> to std::set<...>, I was positively surprised by the STL and now completely convinced by the STL.
History
- 25th May, 2021: Initial version
- 2nd June, 2021: Added a reference to the comment "You can do better..." by SeattleC++ (31-May-21 21:19)
