-3

I've got a task which mainly consist in adding or removing elements from an array in C++. Since arrays ain't dynamic but operations on them are very fast, I've been looking for a dynamic data structure which is nearly as fast to operate. I've been thinking about std::vector but since it is predefined and quite massive construct I'm afraid about time of the operations which is crucial for me. Could Anybody provide me with some information about Your point of view? I'd be very glad for any help from You!


edited:

I'm really sorry I haven't included all important point in my question; below I'd try to add more info:

  • I'll be traversing elements of the structure many times and access them in a random manner so operation on elements on every possible positions are possible
  • I think that there will be (depending on tests provided) many operations on elements in the middle of the data structure as well as near its "brims".

I believe that will help my post to be more clear, specific and, thus, more useful for others.

Thank You for all the answers!

musztard2000
  • 127
  • 2
  • 14
  • 1
    Vectors are typically about just as fast, but the question is, where are you inserting/removing these elements? – chris Mar 26 '14 at 18:42
  • Adding or removing from anywhere but the end of the array is really slow, and a vector just uses an array as underlying structure. – Bernhard Barker Mar 26 '14 at 18:43
  • +1 @chris, and you need to give more information. Also, benchmarking might be the option to go for. – Jonas Schäfer Mar 26 '14 at 18:43
  • More details are needed here. Maybe the [Big-O Algorithm Complexity Cheat Sheet](http://bigocheatsheet.com/) will help. – CPlusPlus OOA and D Mar 26 '14 at 18:45
  • @chris I'll be adding and removing elements from the middle of the structure. That's why I'm a little concerned about `vector` since it's quite similar to list in which these sort of actions are really slow... – musztard2000 Mar 26 '14 at 18:46
  • 1
    A vector is really nothing like a list :o – jrok Mar 26 '14 at 18:47
  • @CPlusPlusOOAandD thank You, but in terms of Big-O notation I'm not pretty sure if it will be 100% accurate because on my program several test are going to be carried out - some of them might comprise relatively small amount of numbers, do you think that simple dynamic array will be good then? – musztard2000 Mar 26 '14 at 18:51
  • `I've been thinking about std::vector but since it is predefined and quite massive construct I'm afraid about time of the operations which is crucial for me.` 100% FUD here. – Lightness Races in Orbit Mar 26 '14 at 18:59
  • Also, vectors are more like arrays and nothing like lists. – Lightness Races in Orbit Mar 26 '14 at 19:00
  • You need to determine the requirements of various operations on the data structure. Unless you do that first, you will most likely pick the wrong solution. Do you need random access? Do you need forward iteration? Backward iteration? How will you want to insert and remove data, and how often will you be adding/removing versus searching? Ia the data immutable? If not, should it's position relative to others change as a result of the mutation? These are only a few of the questions you must answer before writing a solution. It's called design. – Jody Hagins Mar 26 '14 at 19:05
  • @vladimir1923 Check out the Boost::MultiIndex container for logarithmic complexity. A SO post that presents it in the first answer: [Efficiently count number of entries between two std::multimap iterators](http://stackoverflow.com/questions/22645449/efficiently-count-number-of-entries-between-two-stdmultimap-iterators/22645833#22645833). A site that discusses all of the Boost library is: [The Boost C++ Libraries](http://en.highscore.de/cpp/boost/index.html) and directly to MultiIndex: [13.4 Boost.MultiIndex](http://en.highscore.de/cpp/boost/containers.html#containers_multiindex) – CPlusPlus OOA and D Mar 26 '14 at 19:25
  • @vladimir1923 Unless the number of elements are in the hundreds of thousands or higher, it may not matter much which container is used. If this is a time critical application on older hardware, then of course the quantity of elements to see a noticeable time hit will be smaller. The data operations (e.g. insertion and deletion not at the front and/or back) will give a huge indication on which container is best suited. – CPlusPlus OOA and D Mar 26 '14 at 19:33

4 Answers4

3

Refer to Mikael Persson's "container choice" diagram:

http://www.cim.mcgill.ca/~mpersson/pics/STLcontainerChoices.png

Community
  • 1
  • 1
Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
0

The different data structures were implemented in the STL to be used for different reasons. Therefore the structures differ when it comes to insertion/deletion speeds at the start, the middle or the end of the structures or even when it comes to the random access of the structure elements.

Veritas
  • 2,150
  • 3
  • 16
  • 40
0

A nice short comparison of STL containers:

http://john-ahlgren.blogspot.com/2013/10/stl-container-performance.html

If it's possible for you to use an associative array, maps at least guarantee an insertion/look-up time of O(log n) which is a good bit faster for large amounts of data/lots of insertions and deletes than vector's guarantee of O(n) for non-back insertions.

Not sure if they will work here or not, this link also shows some graphs of benchmarks using random insert/removes/searches/fills/sorts, etc. on several different containers:

http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/

Lastly, a flow chart from SO that could help you decide on a container:

In which scenario do I use a particular STL container?

While not perfect, it still might turn out that a vector is your best bet.

Community
  • 1
  • 1
Instinct
  • 349
  • 1
  • 3
  • 10
0

Will a linked list implemented using an array meet your needs?

class AList
{
   public:

      AList()
      {
         for (int = 0; i != 256; ++i )
         {
            nodes[i].prev = (i-1+256)%256;
            nodes[i].next = (i+1)%256;
         }
      }

      int const& operator[](int index)
      {
         // Deal with the case where nodes[index].isSet == false
         return nodes[index].data;
      }

      // Not sure what the requirements are for adding
      // and removing items from the list.
      //
      // add();
      // remove();

   private:

      struct Node
      {
         Node() : data(0), prev(0), next(0), isSet(false) {}

         int data;
         unsigned char prev;
         unsigned char next;
         bool isSet;
      };

      Node nodes[256];
};
R Sahu
  • 204,454
  • 14
  • 159
  • 270