diff --git a/autotests/test_virtual_desktops.cpp b/autotests/test_virtual_desktops.cpp
--- a/autotests/test_virtual_desktops.cpp
+++ b/autotests/test_virtual_desktops.cpp
@@ -291,7 +291,7 @@
     QFETCH(bool, wrap);
     QFETCH(uint, result);
     T functor;
-    QCOMPARE(functor(0, wrap), result);
+    QCOMPARE(functor(nullptr, wrap)->x11DesktopNumber(), result);
 
     vds->setNavigationWrappingAround(wrap);
     vds->initShortcuts();
@@ -484,13 +484,14 @@
 
     QFETCH(QSize, size);
     QFETCH(Qt::Orientation, orientation);
-    grid.update(size, orientation);
+    QCOMPARE(vds->desktops().count(), int(initCount));
+    grid.update(size, orientation, vds->desktops());
     QCOMPARE(grid.size(), size);
     QCOMPARE(grid.width(), size.width());
     QCOMPARE(grid.height(), size.height());
     QFETCH(QPoint, coords);
     QFETCH(uint, desktop);
-    QCOMPARE(grid.at(coords), desktop);
+    QCOMPARE(grid.at(coords), vds->desktopForX11Id(desktop));
     if (desktop != 0) {
         QCOMPARE(grid.gridCoords(desktop), coords);
     }
diff --git a/effects.cpp b/effects.cpp
--- a/effects.cpp
+++ b/effects.cpp
@@ -936,7 +936,10 @@
 
 int EffectsHandlerImpl::desktopAtCoords(QPoint coords) const
 {
-    return VirtualDesktopManager::self()->grid().at(coords);
+    if (auto vd = VirtualDesktopManager::self()->grid().at(coords)) {
+        return vd->x11DesktopNumber();
+    }
+    return 0;
 }
 
 QPoint EffectsHandlerImpl::desktopGridCoords(int id) const
diff --git a/useractions.cpp b/useractions.cpp
--- a/useractions.cpp
+++ b/useractions.cpp
@@ -1450,7 +1450,7 @@
     Workspace *ws = Workspace::self();
     Direction functor;
     // TODO: why is options->isRollOverDesktops() not honored?
-    const int desktop = functor(0, true);
+    const auto desktop = functor(nullptr, true);
     if (c && !c->isDesktop()
             && !c->isDock()) {
         ws->setClientIsMoving(c);
diff --git a/virtualdesktops.h b/virtualdesktops.h
--- a/virtualdesktops.h
+++ b/virtualdesktops.h
@@ -83,22 +83,26 @@
 public:
     VirtualDesktopGrid();
     ~VirtualDesktopGrid();
-    void update(const QSize &size, Qt::Orientation orientation);
+    void update(const QSize &size, Qt::Orientation orientation, const QVector<VirtualDesktop*> &desktops);
     /**
      * @returns The coords of desktop @a id in grid units.
      */
     QPoint gridCoords(uint id) const;
     /**
-     * @returns The ID of the desktop at the point @a coords or 0 if no desktop exists at that
+     * @returns The coords of desktop @a vd in grid units.
+     */
+    QPoint gridCoords(VirtualDesktop *vd) const;
+    /**
+     * @returns The desktop at the point @a coords or 0 if no desktop exists at that
      * point. @a coords is to be in grid units.
      */
-    uint at(QPoint coords) const;
+    VirtualDesktop *at(const QPoint &coords) const;
     int width() const;
     int height() const;
     const QSize &size() const;
 private:
     QSize m_size;
-    uint *m_grid;
+    QVector<QVector<VirtualDesktop*>> m_grid;
 };
 
 /**
@@ -188,34 +192,66 @@
      */
     uint above(uint id = 0, bool wrap = true) const;
     /**
+     * @returns The desktop above desktop @a desktop. Wraps around to the bottom of
+     * the layout if @a wrap is set. If @a desktop is @c null use the current one.
+     */
+    VirtualDesktop *above(VirtualDesktop *desktop, bool wrap = true) const;
+    /**
      * @returns The ID of the desktop to the right of desktop @a id. Wraps around to the
      * left of the layout if @a wrap is set. If @a id is not set use the current one.
      */
     uint toRight(uint id = 0, bool wrap = true) const;
     /**
+     * @returns The desktop to the right of desktop @a desktop. Wraps around to the
+     * left of the layout if @a wrap is set. If @a desktop is @c null use the current one.
+     */
+    VirtualDesktop *toRight(VirtualDesktop *desktop, bool wrap = true) const;
+    /**
      * @returns The ID of the desktop below desktop @a id. Wraps around to the top of the
      * layout if @a wrap is set. If @a id is not set use the current one.
      */
     uint below(uint id = 0, bool wrap = true) const;
     /**
+     * @returns The desktop below desktop @a desktop. Wraps around to the top of the
+     * layout if @a wrap is set. If @a desktop is @c null use the current one.
+     */
+    VirtualDesktop *below(VirtualDesktop *desktop, bool wrap = true) const;
+    /**
      * @returns The ID of the desktop to the left of desktop @a id. Wraps around to the
      * right of the layout if @a wrap is set. If @a id is not set use the current one.
      */
     uint toLeft(uint id = 0, bool wrap = true) const;
     /**
-     * @returns The ID of the desktop after the desktop @a id. Wraps around to the first
-     * desktop if @a wrap is set. If @a id is not set use the current desktop.
+     * @returns The desktop to the left of desktop @a desktop. Wraps around to the
+     * right of the layout if @a wrap is set. If @a desktop is @c null use the current one.
+     */
+    VirtualDesktop *toLeft(VirtualDesktop *desktop, bool wrap = true) const;
+    /**
+     * @returns The desktop after the desktop @a desktop. Wraps around to the first
+     * desktop if @a wrap is set. If @a desktop is @c null use the current desktop.
      **/
-    uint next(uint id = 0, bool wrap = true) const;
+    VirtualDesktop *next(VirtualDesktop *desktop = nullptr, bool wrap = true) const;
     /**
-     * @returns The ID of the desktop in front of the desktop @a id. Wraps around to the
-     * last desktop if @a wrap is set. If @a id is not set use the current desktop.
+     * @returns The desktop in front of the desktop @a desktop. Wraps around to the
+     * last desktop if @a wrap is set. If @a desktop is @c null use the current desktop.
      **/
-    uint previous(uint id = 0, bool wrap = true) const;
+    VirtualDesktop *previous(VirtualDesktop *desktop = nullptr, bool wrap = true) const;
 
     void initShortcuts();
 
     /**
+     * @returns all currently managed VirtualDesktops
+     **/
+    QVector<VirtualDesktop*> desktops() const {
+        return m_desktops;
+    }
+
+    /**
+     * @returns The VirtualDesktop for the x11 @p id, if no such VirtualDesktop @c null is returned
+     **/
+    VirtualDesktop *desktopForX11Id(uint id) const;
+
+    /**
      * @returns The maximum number of desktops that KWin supports.
      */
     static uint maximum();
@@ -248,6 +284,14 @@
      */
     bool setCurrent(uint current);
     /**
+     * Set the current desktop to @a current.
+     * @returns True on success, false otherwise.
+     * @see current
+     * @see currentChanged
+     * @see moveTo
+     **/
+    bool setCurrent(VirtualDesktop *current);
+    /**
      * Called from within setCount() to ensure the desktop layout is still valid.
      */
     void updateLayout();
@@ -412,6 +456,14 @@
      * @returns Id of the desktop above @p desktop
      **/
     uint operator() (uint desktop, bool wrap) {
+        return (*this)(VirtualDesktopManager::self()->desktopForX11Id(desktop), wrap)->x11DesktopNumber();
+    }
+    /**
+     * @param desktop The desktop from which the desktop above should be selected. If @c 0 the current desktop is used
+     * @param wrap Whether to wrap around if already topmost desktop
+     * @returns the desktop above @p desktop
+     **/
+    VirtualDesktop *operator() (VirtualDesktop *desktop, bool wrap) {
         return VirtualDesktopManager::self()->above(desktop, wrap);
     }
 };
@@ -430,6 +482,14 @@
      * @returns Id of the desktop below @p desktop
      **/
     uint operator() (uint desktop, bool wrap) {
+        return (*this)(VirtualDesktopManager::self()->desktopForX11Id(desktop), wrap)->x11DesktopNumber();
+    }
+    /**
+     * @param desktop The desktop from which the desktop below should be selected. If @c 0 the current desktop is used
+     * @param wrap Whether to wrap around if already lowest desktop
+     * @returns the desktop below @p desktop
+     **/
+    VirtualDesktop *operator() (VirtualDesktop *desktop, bool wrap) {
         return VirtualDesktopManager::self()->below(desktop, wrap);
     }
 };
@@ -448,6 +508,14 @@
      * @returns Id of the desktop left of @p desktop
      **/
     uint operator() (uint desktop, bool wrap) {
+        return (*this)(VirtualDesktopManager::self()->desktopForX11Id(desktop), wrap)->x11DesktopNumber();
+    }
+    /**
+     * @param desktop The desktop from which the desktop on the left should be selected. If @c 0 the current desktop is used
+     * @param wrap Whether to wrap around if already leftmost desktop
+     * @returns the desktop left of @p desktop
+     **/
+    VirtualDesktop *operator() (VirtualDesktop *desktop, bool wrap) {
         return VirtualDesktopManager::self()->toLeft(desktop, wrap);
     }
 };
@@ -466,6 +534,14 @@
      * @returns Id of the desktop right of @p desktop
      **/
     uint operator() (uint desktop, bool wrap) {
+        return (*this)(VirtualDesktopManager::self()->desktopForX11Id(desktop), wrap)->x11DesktopNumber();
+    }
+    /**
+     * @param desktop The desktop from which the desktop on the right should be selected. If @c 0 the current desktop is used
+     * @param wrap Whether to wrap around if already rightmost desktop
+     * @returns the desktop right of @p desktop
+     **/
+    VirtualDesktop *operator() (VirtualDesktop *desktop, bool wrap) {
         return VirtualDesktopManager::self()->toRight(desktop, wrap);
     }
 };
@@ -484,6 +560,14 @@
      * @returns Id of the next desktop
      **/
     uint operator() (uint desktop, bool wrap) {
+        return (*this)(VirtualDesktopManager::self()->desktopForX11Id(desktop), wrap)->x11DesktopNumber();
+    }
+    /**
+     * @param desktop The desktop from which the next desktop should be selected. If @c 0 the current desktop is used
+     * @param wrap Whether to wrap around if already last desktop
+     * @returns the next desktop
+     **/
+    VirtualDesktop *operator() (VirtualDesktop *desktop, bool wrap) {
         return VirtualDesktopManager::self()->next(desktop, wrap);
     }
 };
@@ -502,6 +586,14 @@
      * @returns Id of the previous desktop
      **/
     uint operator() (uint desktop, bool wrap) {
+        return (*this)(VirtualDesktopManager::self()->desktopForX11Id(desktop), wrap)->x11DesktopNumber();
+    }
+    /**
+     * @param desktop The desktop from which the previous desktop should be selected. If @c 0 the current desktop is used
+     * @param wrap Whether to wrap around if already first desktop
+     * @returns the previous desktop
+     **/
+    VirtualDesktop *operator() (VirtualDesktop *desktop, bool wrap) {
         return VirtualDesktopManager::self()->previous(desktop, wrap);
     }
 };
@@ -542,16 +634,6 @@
 }
 
 inline
-uint VirtualDesktopGrid::at(QPoint coords) const
-{
-    const int index = coords.y() * m_size.width() + coords.x();
-    if (index > m_size.width() * m_size.height() || coords.x() >= width() || coords.y() >= height()) {
-        return 0;
-    }
-    return m_grid[index];
-}
-
-inline
 uint VirtualDesktopManager::maximum()
 {
     return 20;
@@ -591,7 +673,7 @@
 void VirtualDesktopManager::moveTo(bool wrap)
 {
     Direction functor;
-    setCurrent(functor(0, wrap));
+    setCurrent(functor(nullptr, wrap));
 }
 
 } // namespace KWin
diff --git a/virtualdesktops.cpp b/virtualdesktops.cpp
--- a/virtualdesktops.cpp
+++ b/virtualdesktops.cpp
@@ -28,6 +28,8 @@
 // Qt
 #include <QAction>
 
+#include <algorithm>
+
 namespace KWin {
 
 extern int screen_number;
@@ -62,58 +64,75 @@
 
 VirtualDesktopGrid::VirtualDesktopGrid()
     : m_size(1, 2) // Default to tow rows
-    , m_grid(new uint[2])
+    , m_grid(QVector<QVector<VirtualDesktop*>>{QVector<VirtualDesktop*>{}, QVector<VirtualDesktop*>{}})
 {
-    // Initializing grid array
-    m_grid[0] = 0;
-    m_grid[1] = 0;
 }
 
-VirtualDesktopGrid::~VirtualDesktopGrid()
-{
-    delete[] m_grid;
-}
+VirtualDesktopGrid::~VirtualDesktopGrid() = default;
 
-void VirtualDesktopGrid::update(const QSize &size, Qt::Orientation orientation)
+void VirtualDesktopGrid::update(const QSize &size, Qt::Orientation orientation, const QVector<VirtualDesktop*> &desktops)
 {
     // Set private variables
-    delete[] m_grid;
     m_size = size;
     const uint width = size.width();
     const uint height = size.height();
-    const uint length = width * height;
-    const uint desktopCount = VirtualDesktopManager::self()->count();
-    m_grid = new uint[length];
 
-    // Populate grid
-    uint desktop = 1;
+    m_grid.clear();
+    auto it = desktops.begin();
+    auto end = desktops.end();
     if (orientation == Qt::Horizontal) {
         for (uint y = 0; y < height; ++y) {
-            for (uint x = 0; x < width; ++x) {
-                m_grid[y * width + x] = (desktop <= desktopCount ? desktop++ : 0);
+            QVector<VirtualDesktop*> row;
+            for (uint x = 0; x < width && it != end; ++x) {
+                row << *it;
+                it++;
             }
+            m_grid << row;
         }
     } else {
+        for (uint y = 0; y < height; ++y) {
+            m_grid << QVector<VirtualDesktop*>();
+        }
         for (uint x = 0; x < width; ++x) {
-            for (uint y = 0; y < height; ++y) {
-                m_grid[y * width + x] = (desktop <= desktopCount ? desktop++ : 0);
+            for (uint y = 0; y < height && it != end; ++y) {
+                auto &row = m_grid[y];
+                row << *it;
+                it++;
             }
         }
     }
 }
 
 QPoint VirtualDesktopGrid::gridCoords(uint id) const
 {
-    for (int y = 0; y < m_size.height(); ++y) {
-        for (int x = 0; x < m_size.width(); ++x) {
-            if (m_grid[y * m_size.width() + x] == id) {
+    return gridCoords(VirtualDesktopManager::self()->desktopForX11Id(id));
+}
+
+QPoint VirtualDesktopGrid::gridCoords(VirtualDesktop *vd) const
+{
+    for (int y = 0; y < m_grid.count(); ++y) {
+        const auto &row = m_grid.at(y);
+        for (int x = 0; x < row.count(); ++x) {
+            if (row.at(x) == vd) {
                 return QPoint(x, y);
             }
         }
     }
     return QPoint(-1, -1);
 }
 
+VirtualDesktop *VirtualDesktopGrid::at(const QPoint &coords) const
+{
+    if (coords.y() >= m_grid.count()) {
+        return nullptr;
+    }
+    const auto &row = m_grid.at(coords.y());
+    if (coords.x() >= row.count()) {
+        return nullptr;
+    }
+    return row.at(coords.x());
+}
+
 KWIN_SINGLETON_FACTORY_VARIABLE(VirtualDesktopManager, s_manager)
 
 VirtualDesktopManager::VirtualDesktopManager(QObject *parent)
@@ -138,129 +157,169 @@
 
 uint VirtualDesktopManager::above(uint id, bool wrap) const
 {
-    if (id == 0) {
-        id = current();
+    auto vd = above(desktopForX11Id(id), wrap);
+    return vd ? vd->x11DesktopNumber() : 0;
+}
+
+VirtualDesktop *VirtualDesktopManager::above(VirtualDesktop *desktop, bool wrap) const
+{
+    Q_ASSERT(m_current);
+    if (!desktop) {
+        desktop = m_current;
     }
-    QPoint coords = m_grid.gridCoords(id);
+    QPoint coords = m_grid.gridCoords(desktop);
     Q_ASSERT(coords.x() >= 0);
     while (true) {
         coords.ry()--;
         if (coords.y() < 0) {
             if (wrap) {
                 coords.setY(m_grid.height() - 1);
             } else {
-                return id; // Already at the top-most desktop
+                return desktop; // Already at the top-most desktop
             }
         }
-        const uint desktop = m_grid.at(coords);
-        if (desktop > 0) {
-            return desktop;
+        if (VirtualDesktop *vd = m_grid.at(coords)) {
+            return vd;
         }
     }
+    return nullptr;
 }
 
 uint VirtualDesktopManager::toRight(uint id, bool wrap) const
 {
-    if (id == 0) {
-        id = current();
+    auto vd = toRight(desktopForX11Id(id), wrap);
+    return vd ? vd->x11DesktopNumber() : 0;
+}
+
+VirtualDesktop *VirtualDesktopManager::toRight(VirtualDesktop *desktop, bool wrap) const
+{
+    Q_ASSERT(m_current);
+    if (!desktop) {
+        desktop = m_current;
     }
-    QPoint coords = m_grid.gridCoords(id);
+    QPoint coords = m_grid.gridCoords(desktop);
     Q_ASSERT(coords.x() >= 0);
     while (true) {
         coords.rx()++;
         if (coords.x() >= m_grid.width()) {
             if (wrap) {
                 coords.setX(0);
             } else {
-                return id; // Already at the right-most desktop
+                return desktop; // Already at the right-most desktop
             }
         }
-        const uint desktop = m_grid.at(coords);
-        if (desktop > 0) {
-            return desktop;
+        if (VirtualDesktop *vd = m_grid.at(coords)) {
+            return vd;
         }
     }
+    return nullptr;
 }
 
 uint VirtualDesktopManager::below(uint id, bool wrap) const
 {
-    if (id == 0) {
-        id = current();
+    auto vd = below(desktopForX11Id(id), wrap);
+    return vd ? vd->x11DesktopNumber() : 0;
+}
+
+VirtualDesktop *VirtualDesktopManager::below(VirtualDesktop *desktop, bool wrap) const
+{
+    Q_ASSERT(m_current);
+    if (!desktop) {
+        desktop = m_current;
     }
-    QPoint coords = m_grid.gridCoords(id);
+    QPoint coords = m_grid.gridCoords(desktop);
     Q_ASSERT(coords.x() >= 0);
     while (true) {
         coords.ry()++;
         if (coords.y() >= m_grid.height()) {
             if (wrap) {
                 coords.setY(0);
             } else {
                 // Already at the bottom-most desktop
-                return id;
+                return desktop;
             }
         }
-        const uint desktop = m_grid.at(coords);
-        if (desktop > 0) {
-            return desktop;
+        if (VirtualDesktop *vd = m_grid.at(coords)) {
+            return vd;
         }
     }
+    return nullptr;
 }
 
 uint VirtualDesktopManager::toLeft(uint id, bool wrap) const
 {
-    if (id == 0) {
-        id = current();
+    auto vd = toLeft(desktopForX11Id(id), wrap);
+    return vd ? vd->x11DesktopNumber() : 0;
+}
+
+VirtualDesktop *VirtualDesktopManager::toLeft(VirtualDesktop *desktop, bool wrap) const
+{
+    Q_ASSERT(m_current);
+    if (!desktop) {
+        desktop = m_current;
     }
-    QPoint coords = m_grid.gridCoords(id);
+    QPoint coords = m_grid.gridCoords(desktop);
     Q_ASSERT(coords.x() >= 0);
     while (true) {
         coords.rx()--;
         if (coords.x() < 0) {
             if (wrap) {
                 coords.setX(m_grid.width() - 1);
             } else {
-                return id; // Already at the left-most desktop
+                return desktop; // Already at the left-most desktop
             }
         }
-        const uint desktop = m_grid.at(coords);
-        if (desktop > 0) {
-            return desktop;
+        if (VirtualDesktop *vd = m_grid.at(coords)) {
+            return vd;
         }
     }
+    return nullptr;
 }
 
-uint VirtualDesktopManager::next(uint id, bool wrap) const
+VirtualDesktop *VirtualDesktopManager::next(VirtualDesktop *desktop, bool wrap) const
 {
-    if (id == 0) {
-        id = current();
+    Q_ASSERT(m_current);
+    if (!desktop) {
+        desktop = m_current;
     }
-    const uint desktop = id + 1;
-    if (desktop > count()) {
+    auto it = std::find(m_desktops.begin(), m_desktops.end(), desktop);
+    Q_ASSERT(it != m_desktops.end());
+    it++;
+    if (it == m_desktops.end()) {
         if (wrap) {
-            return 1;
+            return m_desktops.first();
         } else {
-            // are at the last desktop, without wrap return current
-            return id;
+            return desktop;
         }
     }
-    return desktop;
+    return *it;
 }
 
-uint VirtualDesktopManager::previous(uint id, bool wrap) const
+VirtualDesktop *VirtualDesktopManager::previous(VirtualDesktop *desktop, bool wrap) const
 {
-    if (id == 0) {
-        id = current();
+    Q_ASSERT(m_current);
+    if (!desktop) {
+        desktop = m_current;
     }
-    const uint desktop = id - 1;
-    if (desktop == 0) {
+    auto it = std::find(m_desktops.begin(), m_desktops.end(), desktop);
+    Q_ASSERT(it != m_desktops.end());
+    if (it == m_desktops.begin()) {
         if (wrap) {
-            return count();
+            return m_desktops.last();
         } else {
-            // are at the first desktop, without wrap return current
-            return id;
+            return desktop;
         }
     }
-    return desktop;
+    it--;
+    return *it;
+}
+
+VirtualDesktop *VirtualDesktopManager::desktopForX11Id(uint id) const
+{
+    if (id == 0 || id > count()) {
+        return nullptr;
+    }
+    return m_desktops.at(id - 1);
 }
 
 uint VirtualDesktopManager::current() const
@@ -273,17 +332,20 @@
     if (newDesktop < 1 || newDesktop > count() || newDesktop == current()) {
         return false;
     }
-    auto it = std::find_if(m_desktops.constBegin(), m_desktops.constEnd(),
-        [newDesktop] (VirtualDesktop *d) {
-            return d->x11DesktopNumber() == newDesktop;
-        }
-    );
-    Q_ASSERT(it != m_desktops.constEnd());
-    const uint oldDesktop = current();
+    auto d = desktopForX11Id(newDesktop);
+    Q_ASSERT(d);
+    return setCurrent(d);
+}
 
-    // change the desktop
-    m_current = *it;
-    emit currentChanged(oldDesktop, newDesktop);
+bool VirtualDesktopManager::setCurrent(VirtualDesktop *newDesktop)
+{
+    Q_ASSERT(newDesktop);
+    if (m_current == newDesktop) {
+        return false;
+    }
+    const uint oldDesktop = current();
+    m_current = newDesktop;
+    emit currentChanged(oldDesktop, newDesktop->x11DesktopNumber());
     return true;
 }
 
@@ -463,7 +525,7 @@
         }
     }
 
-    m_grid.update(QSize(width, height), orientation);
+    m_grid.update(QSize(width, height), orientation, m_desktops);
     // TODO: why is there no call to m_rootInfo->setDesktopLayout?
     emit layoutChanged(width, height);
 }