Lecture Notes for CS 509, Advanced Programming II

16 March 2004 - Vectors vs. Maps

Outline

• Container characteristics.

• Choosing containers.

• An experiment.

  • Interleaved Inserts and Lookups

  • Sequenced Inserts and Lookups

• Results

Container Characteristics

• Advantage to vectors:

  • No storage overhead.

  • Fast element access.

• Advantage to maps:

  • Fast insertion.

  • Fast finding.

Choosing Containers

• Given vectors and maps, which is better?

• Container choice should be based on expected operations and operator patterns.

  • Consider insertions and lookups.

• Interleaved insertions and lookups.

  • Vectors should lose badly.

    • O(log n) lookup requires ordered insertion.

    • Ordered insertion is O(n) in the worst case.

• Sequenced insertions and lookups.

  • Maps should lose.

    • Each insertion is ordered, a potentially expensive O(log n).

An Experiment

• Let's insert and lookup random numbers in a vector and a map.

  • Generate 2n random numbers and insert half of them, look up the other half.

  • Interleaving alternates between insertions and lookups.

  • Sequencing does all insertions, then all lookups.

• The idea is to use each container to its advantage.

Interleaved Inserts and Lookups

• Interleaved vector operations.

  std::vector<int> v
  v.reserve(vals.size())
  
  for i = 0; i < vals.size(); i += 2
    v.insert(
      std::lower_bound(
        v.begin(), v.end(), vals[i]), 
      vals[i])
    std::binary_search(
      v.begin(), v.end(), vals[i + 1])
  

• Interleaved map operations.

  std::map<int, int> m
  
  for i = 0; i < vals.size(); i += 2
    m.insert(std::make_pair(vals[i], vals[i]))
    m.find(vals[i + 1])
  

Sequenced Inserts and Lookups

• Sequenced vector operations.

  std::vector<int> v
  v.reserve(vals.size())
  
  for i = 0; i < vals.size(); i += 2
    v.push_back(vals[i])
  
  std::sort(v.begin(), v.end())
  
  for i = 1; i < vals.size(); i += 2
    std::binary_search(
      v.begin(), v.end(), vals[i])
  

• Sequenced map operations.

  std::map<int, int> m
  
  for i = 0; i < vals.size(); i += 2
    m.insert(std::make_pair(vals[i], vals[i]))
  
  for i = 1; i < vals.size(); i += 2
    m.find(vals[i])
  

Test Environment

• Run on rockhopper

  ro dmesg
  Linux version 2.4.20-30.9smp
  gcc version 3.2.2 
  Red Hat Linux 3.2.2-5
  Memory: 1,310,712k available
  Processors: 2
  Detected 728.493 MHz processor.
  CPU: L1 I cache: 16K, L1 D cache: 16K
  CPU: L2 cache: 256K
  

• Compiled with -O optimization.

• Run on a lightly-loaded system.

  • w reports around 14 users, most idle for hours or editing text.

• See the code.

Interleaved Insert+Find Results

• The map wins.

Sequenced Insert+Find Results

• The vector wins.

Points to Remember

• Choose your containers wisely.

  • "Wisely" means, in this case, according to expected operations.

• Predictability is better than unpredictability.

  • Find predictability and exploit it.

• Sometimes you can guess wrong, other times you can't.

  • Wise developers know when they can be wrong.

• Good developers know how much things cost.

  • And the factors that influence those costs.

This page last modified on 23 March 2004.