The Beauty of Sorted Arrays

Warning! Some information on this page is older than 3 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

Mar 2010

The Beauty of Sorted Arrays

A one-dimmensional array (also called vector) is very simple data structure. We were taught that inserting or deleting elements in the middle of the array is slow because we have to move (by rewriting) all following elements. That's why books about C++ teach that for sorted collections - those who provide fast search operation - it's better to use containers like std::set or std::map.

But those who code games in C++ and care about performance know that today's processors (CPU) are very fast in terms of doing calculations and processing lots of data, while access to the RAM memory becomes more and more kind of a bottleneck. According to great presentation Pitfalls of Object Oriented Programming by Tony Albrecht from Sony, a cachce miss (access to some data from the memory which are not currently in CPU cache) costs about 400 cycles! Dynamic memory allocation (like operator new in C++) is also a slow operation. That's why data structures that use separate nodes linked with pointers (like std::list, std::set, std::map) are slower than std::vector and it's often better to keep a sorted collection of elements in a vector, even if you have hundreds or thousands of elements and must sometimes insert or delete them from the middle.

Unfortunately, C++ STL doesn't provide a "std::ordered_vector" container that whould keep items sorted while allocating single chunk of continuous memory. We have to do it by ourselves, like this:

First, we have to choose a way to compare elements. There are multiple solutions (read about comparators in C++), but the simplest one is to just overload operator < in your element structure.

#include <vector>
#include <string>
#include <algorithm>

struct Item
  int Id;
  DWORD Color;
  std::string Name;

  Item() { }
  Item(int id, DWORD color, const std::string name)
    : Id(id), Color(color), Name(name) { }

  bool operator < (const Item &rhs) const { return Id < rhs.Id; }

typedef std::vector<Item> ItemVector;

ItemVector vec;
Item item;

Here is how we insert an item into sorted vector:

item = Item(1, 0xFF0000, "Red");
ItemVector::iterator itToInsert = std::lower_bound(
  vec.begin(), vec.end(), item);
vec.insert(itToInsert, item);

Unfortunately we have to deal with iterators instead of simple indices.

To check if the vector contains element with particular Id:

item = Item(1, 0, std::string());
bool contains = std::binary_search(vec.begin(), vec.end(), item);

Here come another nuisances. We have to create full Item object just to use its Id field for comparison purpose. I'll show tomorrow how to overcome this problem.

It's also annoying that binary_search algorithm returns bool instead of iterator that would show us where the found item is. To find an item and determine its iterator (and from this its index) we have to use lower_bound algorithm. This algorithm is very universal but also hard to understand. It quickly searches a sorted collection and returns the position of the first element that has a value greater than or equivalent to a specified value. It was perfect for determining a place to insert new item into, but to find existing element, we have to use it with this if:

item = Item(1, 0, std::string());
ItemVector::iterator findIt = std::lower_bound(vec.begin(), vec.end(), item);
if (findIt != vec.end() && findIt->Id == item.Id)
  size_t foundIndex = std::distance(vec.begin(), findIt);
  // Not found.

And finally, to remove an item from the vector while having index, we do this trick:

size_t indexToDelete = 0;
vec.erase(vec.begin() + indexToDelete);

Well, C++ STL is very general, universal, powerful and... very complicated, while standard libraries of other programming languages also have some curiosities in their array classes.

For example, ActionScript 3 have single method to insert and remove items:

function splice(startIndex:int, deleteCount:uint, ...  values):Array

To delete some items, you pass non-zero deleteCount. To insert some items, you pass them as values parameter.

In .NET, the System.Collections.Generic.List<T> class (which is actually an array, the name is misnomer) has very smart BinarySearch method. It returns the "zero-based index of item (...), if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.". It can be used to both find existing item in the array or determine an index for a new item, like:

int index = myList->BinarySearch("abc");
if (index < 0)
  myList->Insert(~index, "abc");

See also: My Algorithms for Sorted Arrays

Comments (3) | Tags: algorithms c++ stl .net flash | Author: Adam Sawicki | Share


2015-06-29 07:25:14
soccer shoes,
softball bats,
supra shoes,
swarovski outlet,
swarovski outlet,
north face outlet online,
the north face outlet,
north face uk,
the north face outlet,
calvin kleins outlet,
celine bags,
cheap nfl jerseys,
air jordan retro,
michael kors outlet,
nike sneakers,
oakley vault,
oakley vault,
cheap oakley,
ray ban sunglasses,
discount shoes,
ugg boots clearance,
flat iron,
air max 2015,
nike outlet,
nike running shoes,
nike free,
nike running,
nike air max,
nike mercurial,
roshe run,
cheap nike shoes,
north face jackets,
north face jackets women,
oakley sunglasses outlet,
oakley outlet,
oakley vault,
cheap oakley sunglasses,
omega watches,
pandora sale,
pandora charms,
ralph lauren outlet,
prada outlet,
prada outlet,
prada shoes for men,
polo ralph lauren outlet online,
ralph lauren outlet,
ralph lauren outlet,
ralph lauren shirts,
ralph lauren outlet online,
ralph lauren outlet online,
ray-ban sunglasses,
ray ban sunglasses,
ray ban sunglasses outlet,
cheap ray ban,
burberry outlet,
red bottoms,
tory burch handbags,
abercrombie and fitch kids,
abercrombie fitch,,
air huarache,
jordan shoes,
jordan retro,
nike air max 2014,
nike air max 2015,
babyliss pro,
basketball shoes,
beats by dre outlet,
beats headphones,
beats by dre outlet,
beats by dr dre,
burberry outlet,
burberry outlet,
burberry outlet,
christian louboutin shoes,
christian louboutin,
christian louboutin shoes,,,
coach handbags outlet,
coach factory outlet online,,
coach bags outlet,
chanel outlet,
converse shoes,
hermes handbags,
cheap glasses,
sunglasses for women,
hollister clothes,
chanel bags,
softball bats,
christian louboutin,
ferragamo outlet,
salvatore ferragamo outlet,
hair straightener,
gucci sale,
gucci belt,
gucci handbags,
gucci belt,
gucci shoes outlet,
gucci outlet,
hermes birkin bag,
hermes birkin,
hermes bags,
hollister kids,
insanity workout calendar,
iphone 4s cases,
jimmy choo shoes,
air jordan,
air jordan shoes,
juicy couture,
juicy couture outlet,
kate spade,
kate spade bags,
longchamp bags,
longchamp outlet,
louis vuitton canada,
louis vuitton outlet stores,
louis vuitton outlet,
louis vuitton outlet,
louis vuitton outlet online,
louis vuitton outlet,
louis vuitton handbags,
marc jacobs bags sale,
mcm bags,
mcm handbags,
michael kors outlet store,
michael kors outlet online,
michael kors outlet,
michael kors uk,
michael kors,
michael kors outlet online sale,
michael kors purses,
michael kors handbags,
michael kors,
michael kors outlet online sale,
michael kors bags,
mont blanc,
new balance,
ray ban sunglasses outlet,
knock off designer handbags,
rolex watches,
jordan 6,
omega watches,
roshe run,
roshe runs,
salvatore ferragamo shoes,
north face jackets outlet,
thomas sabo,
tiffany jewelry,
tiffany co,
timberland boots,
timberland outlet,
tommy hilfiger polos,
tommy hilfiger coupons,
toms shoes,
toms outlet,
toms shoes,
tory burch handbags,
tory burch handbags,
true religion jeans outlet,
true religion outlet,
true religion jeans women,
ugg boots,
uggs outlet,
ugg australia,
ugg boots clearance,
coach outlet online,
vans shoes,
dresses for weddings,
yoga pants,
uggs outlet,
polo ralph lauren outlet online,
burberry outlet online,
toms shoes outlet,
cheap michael kors,
tory burch shoes,
prada outlet,
longchamp outlet,
chanel bags,
true religion jeans outlet,
abercrombie fitch,
hollister co,
new balance store,
converse sneakers,
lululemon outlet,
cheap jerseys,
nfl jerseys,
rolex watches,
omega watches,
giuseppe zanotti,
mac cosmetics,
mizuno running,
handbags outlet,
hilfiger outlet,
ed hardy,
levi's jeans,
bcbg max azria,
bebe outlet,
gucci outlet,
polo ralph lauren outlet,
2015-07-12 10:16:33
Packers and movers @
Packers and Movers Chennai@
Packers and Movers Bangalore@
Packers and Movers delhi@
Packers and Movers Gurgaon@
Packers and Movers Hyderabad@
Packers and Movers Noida@
Packers and Movers Pune@
Packers and Movers Mumbai @
2016-03-29 10:10:38
beautiful things to read more, look for a long time, I felt closer to reality very far away, life is short, if put too much time is spent on practical things, really is a waste of life, but some things, but if the raw flavor, leisure goods for gossip, so I love romantic dreamer, but I love real life.Day in a hurry, took all the joy and sadness, a lot of things, not enough time to recall, Chaoyang July, early June already covered confused. Season removed, landscape transformation, the so-called forever always far-fetched, time, not to be squandered, the true meaning of life is to enjoy the good in the flat, I Dimei fireworks, also read the leisure, with a touch of ink, painting a thin clear Huan, look lush green, covered with mottled wall. This July, I kept the book's swoosh; this July, I dream in Lijiang; this July, and has been well, not made sad.If you can do if a light breeze right woman, placed in the text soul, written imprint of life, write thin cool and clear Huan, occasionally write love, but never give love, keep a clear gel Bay, look for a parts of the peace, the joy and sorrow of all his writings, and text only affair has nothing to do with the other.Morning time, with a tranquil and contented Zen cloud water, eyes closed, the heart distant exile, Wind and Smoke curl in the mountains, such as Dai, ups and downs, indeed, like a thread, the ups and downs of life, with long Qingyuan . Flowers followed the road, facing the sun slowly forward, then the mind is calm, quiet as the lake, the water peach, flower with water, just like the fate of this world, do not ask why, regardless of come and go, only flowers need to remember Lu Qing, Yue possessor of the green heart, cool count. Sunlight penetration mist, alluding on the lake, the water green, clear, sparkling, on the beach, there are birds flying over from time to time, the sky blue and empty, with a quiet life after ups and downs, this time the heart is close to nature, without the slightest ripples, content with this quiet and peaceful. An end, wins the snow lotus, world clarity, years of silence, the heart is also safe.Time, very long. I know, I can stay in my mind there are limitations, not the majority, can only rely on these words to memory.Time, is very short. I understand, you can never forget so little, so I was in such a manner so as to leave some more.Youth, is very long. In life, shiny people, in fact, that a figure, how the passage of time, or the whole dazzling Love.Youth, is very short. In life, flickering days

Post comment

Nick *
Your name or nickname
Your contact information (optional, will not be shown)
Text *
Content of your comment
Calculate *
(* - required field)
STAT NO AD [Stat] [Admin] [STAT NO AD] [pub] [Mirror] Copyright © 2004-2017 Adam Sawicki
Copyright © 2004-2017 Adam Sawicki